Wednesday, 22 July 2009

Uncoordinated settlers

My FreeCiv client-side AI (not related to [1]) is sending settlers off to found new cities, but they are still a bit uncoordinated. It may be as obvious as in this composite screenshot where two contemporaneously-existing settlers are on paths crossing each other. I've fudged the image a bit to show one settler's path info in purple and the other's in yellow.

My little Turkish empire could save a couple of turns by letting the yellow and the purple settlers switch targets. Time is money! I don't think I'm too far off from being able to do these exchanges. I expect that optimising the routing might be NP-complete (just has that Travelling Salesman "feel"), but I could probably brute-force it as there are unlikely to be more than a handful of settlers active at any one moment.



  1. I'm bogged down. Some horrible memory corruption, and bisecting with git doesn't yield any sensible answers.

  2. Figured it out after losing some hair and having some more turn grey: