One of the things I love about this community is the great minds and great ideas of the people that make it. Thats why, when faced with a problem like this I can think of no better solution than to ask you guys!
As part of my AI I would like to be able to build a single road that connects all stations together in a loop. This ofcourse represents the travelling salesman problem. I have done some reading and implemented a simple solver based on stochastic optimisation, but I think my efforts could be vastly improved.
The solver works well for a small number of points. The shortest tour for 20 points can be adequately "solved" with 2,000 iterations taking 2 game days, but for a larger number of points the deficiencies in the approach become more apparent. To run for 200,000 iterations over 200 points takes about 4.5 game years, and you can clearly see it still isn't optimal!
The code can be used like this...
Code: Select all
local numPoints = 20;
local points = [];
for(local i = 0; i < numPoints; i++) {
local p = AIMap.GetTileIndex(AIBase.RandRange(255), AIBase.RandRange(255));
points.append(p);
}
local tour = ShortestTour(points);
tour.Run();
local prev = tour.GetPoints()[numPoints - 1];
for(local i = 0; i < numPoints; i++) {
local p = tour.GetPoints()[i];
// Do something between prev & p
prev = p;
}
However there must be a better way. Perhaps a similar algorithm with a better heuristic? Simulated annealing or a genetic algorithm maybe? I'm sure one of you bright people has already thought about this, or already come up with a better solution. Thoughts?
Thanks very much