I started with the strategy map AI and decided to make a basic game AI which just produces colony ships and sends them to new planets. That sounds quite simple: just take a colony ship and order it to the closest free planet. But what if there happens to be multiple colony ships available, some of which would go to the same closest planet? What if a new colony ship is produced and is closer to some habitable planet than an existing colony ship en route to that planet? What if some of the colony ships can colonize only certain types of planets? What if some of the colony ships have a huge jump range and would be better to be spent on planets farther away?
I decided to solve this optimization problem by implementing Hungarian algorithm. Now the ships are assigned to free planets optimally in a way that the overall time spent on flying is minimized. It also takes different jump ranges and colonizing restrictions into account. It is also run every turn so if the situation changes, the ships will adapt accordingly.
In the first video there are four civilizations expanding to the stars. In the second video there is one civilization which starts with a huge amount of colony ships. Turn counter can be seen at the top right corner of the screen.