Posts: 3822
Joined: 16 Sep 2007, 22:00
KaM Skill Level: Skilled
ICQ: 269127056
Website: http://lewin.hodgman.id.au
Yahoo Messenger: lewinlewinhodgman
Location: Australia
Walk distance algorithm
The red tile is the starting location, the roads are tiles that are generated by the algorithm, all of them are within 14 tiles by walking distance from the starting location, rather than by direct distance as we previously used. So in the woodcutter example he would only plant trees on the road tiles.
For comparison, here's what it did in the past:
See the improvement?
Note: The first image is slightly less round (compare the bottom left of the road areas) due to an approximation made to speed up the new algorithm by avoiding floating point numbers. (I assume sqrt(2) = 1.5 instead of 1.41 which is what it should be)
Performance wise, it takes about 1010ms (1.01 seconds) to run 1000 times (with radius 14, the largest mining radius) on my 1st generation i7 running at full speed, (around 2.5GHz) and it takes about 1620ms (1.62 seconds) with my i7 slowed down to 1.6GHz. So for 1 run that's about 1.01ms on a powerful CPU or 1.62ms on an older CPU. We process one game tick every 100ms so that's only 1% of our allowance per time it is used, and it won't be run on most ticks anyway (units pause between checking for work to do) This is about the same as our main floodfill algorithm (needed for calculating whether you can walk from A to B) that is updated every time the terrain changes.
So performance should be no problem at all
If anyone is interested in how it works, basically it floodfills out from the starting point, marking each tile with the distance it took to walk there and each step of the floodfill the distance is increased so we know how far we've come on this particular path. When a tile we've already been to is reached by a shorter route it processes that tile again in case we reach some more tiles we missed last time. So I guess it's a blend of Dijkstra's algorithm and a flood fill It seemed like the most logical way to do it. The whole thing is around 75 lines of code.
So now I'll do some cleaning up of the code and then make the woodcutter, fisherman, farmer and stonemason use it
On a side note, this means that farmers will not farm fields as far above their house as they used to, (because the distance is calculated around their house) so we might need to increase all of the mining radii a bit. (it will effect all units, but farmers will probably be the most noticeable)