GatlingGun
Warlord
I've been hacking up a python script (using a C-based backend for speed) to take a an unimproved city site and show the best possible uses for those 20 tiles, given some food, production and tree constraints...
Essentially I wind up creating a multi-dimensional list of the valid possible tile improvements, and then generate combinations of those 20 improved tiles... I feed those combinations into a scoring algorithm and pop out the top seven combinations for my constraints...
The problem with this method is that 20 tiles with three improvements (assume the simplest case of all grass... so Farm, Cottage, Workshop) gives you 3**20 combinations to iterate through! Just generating this many combinations takes in excess of 1 minute and exponentiates when you consider something like 20 tiles where you have to chop trees... there are literally 1.1 trillion combinations with 20 flat tree tiles... this takes a long time, no matter what home computer you are using...
I'm assuming that the AI isn't choosing improvements like that... I'm not familiar with the Civ4 source, but is there anyone who can comment on how the AI does it? I'd be interested in comparing this algorithm against the "long way"... I realize the AI improvements are criticized for being silly at times, but I wonder whether I could reuse this and improve it somehow.
Even if someone could point me to the routine in the source, that could get me started...
Thoughts?
[Edit: as Refar alluded to below, 3**20 is the number of permutations, not combinations... so I need a better algorithm]
Essentially I wind up creating a multi-dimensional list of the valid possible tile improvements, and then generate combinations of those 20 improved tiles... I feed those combinations into a scoring algorithm and pop out the top seven combinations for my constraints...
The problem with this method is that 20 tiles with three improvements (assume the simplest case of all grass... so Farm, Cottage, Workshop) gives you 3**20 combinations to iterate through! Just generating this many combinations takes in excess of 1 minute and exponentiates when you consider something like 20 tiles where you have to chop trees... there are literally 1.1 trillion combinations with 20 flat tree tiles... this takes a long time, no matter what home computer you are using...
I'm assuming that the AI isn't choosing improvements like that... I'm not familiar with the Civ4 source, but is there anyone who can comment on how the AI does it? I'd be interested in comparing this algorithm against the "long way"... I realize the AI improvements are criticized for being silly at times, but I wonder whether I could reuse this and improve it somehow.
Even if someone could point me to the routine in the source, that could get me started...
Thoughts?
[Edit: as Refar alluded to below, 3**20 is the number of permutations, not combinations... so I need a better algorithm]