Walk distance algorithm

[Lewin]

I've been working on an algorithm to solve the problem of, for example, the woodcutter walking ALL the way around the mountain/river to plant a tree, because it is within the correct radius of his house, (across the mountain/river) even though it takes him 10 minutes to walk there and back. Here's the result with an example "river" and "mountain":

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)

[Krom]

Several points need to be clarified:
First of all - what is performance compared to old algo? Without it it is hard to say how much slower it has become.
Secondly - out of the 100ms timeframe 30 or so is taken by the GPU, some for terrain updates and overall that means that it's not as light as it seems.

FloodFill+Dijkstra is the best choice, no arguing )
On a side note, to make circle more round the distances from center could be multiplied by 10 )

All-in-all it looks much better than before and I like how it fits in )

[Piko]

This algorithm looks very good. I have also an idea for other (it maybe will be faster) - firstly mark all tiles in radius 14 tiles from starting location, and while AI want to go to an marked tile - it check is way to this tile shorter than 14 sqares, if not - it don't go here and shearch for another tile. What do You think about it?

[Krom]

Thats basically the same thing, but the other way round.

Your algorithm is more optimistic (most of the time it will pick a spot from first try), but if there are more obstacles (fisherman near narrow river or woodcutter in town) it will be much slower because it will need to repeat several times before finding suitable location, each time invoking Dijkstra to check the distance.

Where FloodFill+Dijkstra needs more time for 1 search, it will fill all the distance values in one pass, this means its time is always near-constant. Thats its advantage.

[godest]

Looks like a good improvement ! nice work

[The Dark Lord]

Ah... Now I don't have to worry about annoying bastards anymore.

[Lewin]

@Krom:
Good suggestion on multiplying by 10, I was multiplying by 2 which is less accurate although allows larger radius sizes. However 10 still allows a radius up to 24 tiles so that shouldn't be a problem. I've implemented it.

I did some rudimentary measurements using a 192x192 blank map: (measured 1000 runs and divided by 1000, except UpdatePassability where I only measured 100 runs because it's slow)

GetTilesWithinDistance with new walking distance algo: 1.26ms
GetTilesWithinDistance with old direct distance algo: 0.12ms
UpdatePassability on entire 192x192 map: 82ms
UpdateWalkConnect all types except wcRoad on entire 192x192 map: 17.7ms
UpdateWalkConnect only wcWalk on entire 192x192 map: 5.6ms

So yeah the new system is 10x slower, but when you consider that the old system just scans a big square of the map and checks distances it's not really surprising. What I find surprising is UpdateWalkConnect and UpdatePassability, they seems to be taking quite a while to run. I wonder if they're chokepoints.

[Krom]

They are bottlenecks, and we already discussed ways to optimize them (use 4x4 tilegroups or some other way to generalize terrain)

[stijn263]

@Krom:
Good suggestion on multiplying by 10, I was multiplying by 2 which is less accurate although allows larger radius sizes. However 10 still allows a radius up to 24 tiles so that shouldn't be a problem. I've implemented it.

Man, K&M appears to be full of problems every good math/computerscience geek dreams of

I have another suggestion that uses integers only and is exact (i.e. doesn't use rounding, nor does it take any square roots):

• Store the distance of a path as a combination of two integers (P,Q), where P represents the amount of vertical/horizontal walks and Q the amount of diagonal walks. I.e. the distance (P,Q) represents the value P + Q * sqrt(2).
• Now, if you want to check whether the distance (P,Q) is larger than (R,S), you want to know whether P + Q * sqrt(2) > R + S * sqrt(2) holds.
  There are four situations:
  • P > R and Q > S: in this case it is clear that (P,Q) is larger than (R,S)
  • P > R and Q <= S: In this case we rewrite P + Q * sqrt(2) > R + S * sqrt(2) and then square both sides (the inequality sign still holds because both sides are nonnegative)
    
    P-R > (S-Q) * sqrt(2)
    (P-R)^2 > (S-Q)^2 * 2
    
    This inequality can be checked without taking any square roots and using integers only.
  • P <= R and Q <= S: in this it is clear that (P,Q) is not strictly larger than (R,S)
  • P <= R and Q > S: In this case we rewrite P + Q * sqrt(2) > R + S * sqrt(2) and then square both sides (the inequality sign still holds because both sides are nonnegative)
    (Q-S) * sqrt(2) > R-P
    (Q-S)^2 * 2 > (R-P)^2
    This inequality can be checked without taking any square roots and using integers only.

So, in 50% of the cases a simple integer comparison suffices. In the other 50% of the cases you need 2 substraction, 2 multiplications, 1 addition and 1 comparison. All arithmetics are integer and the answer is exact

[Garnu_Thorn]

Would it be too memory intensive to store the walking tables for map roaming employees on the local computer's RAM in compiled format?

This might save time in each of those units rechecking roam limits every time they leave their house as well as limit third-party RAM hacks manipulating the limits, well, I'd say anything from the Remake going in to RAM would be compiled anyways......

So, a unit taking a home would check their work area on the map and further use that table for reference. The only units I'd see that a recheck is necessary is one, farmers with later added fields (maybe, maybe not as any field within working distance would be worked, unless the player depletes a nearby stone mountain and plants fields on it afterwards), two, stonemasons depleting their mountain (maybe this unit could use a special update time), and three, wood cutters planting and harvesting within the radius of stone. For the time the worker rechecks the work area, that could be based off of the time when they first occupy the house, and a set time they would recheck their work area.

There is the matter of additional buildings put in the work area, though......

[Lewin]

Would it be too memory intensive to store the walking tables for map roaming employees on the local computer's RAM in compiled format?

The problem is it's hard to tell when you need to update that table, since almost anything that changes the terrain COULD effect it in rare cases (e.g. even building a road change the slope of the ground and could cause a tile to become unwalkable and block the only way through an obstacle) So you would end up rebuilding the table more often that we already compute it when needed.

From my tests this walking distance algorithm is far from our worst bottleneck, it's using more than 20x less CPU time than our floodfill and pathfinding code and 10x less than the terrain updating (it makes trees grow). And that's after I optimised our floodfill and pathfinding a few days ago. So there's not much point optimising it.

I have another suggestion that uses integers only and is exact (i.e. doesn't use rounding, nor does it take any square roots):

• Store the distance of a path as a combination of two integers (P,Q), where P represents the amount of vertical/horizontal walks and Q the amount of diagonal walks. I.e. the distance (P,Q) represents the value P + Q * sqrt(2).
• Now, if you want to check whether the distance (P,Q) is larger than (R,S), you want to know whether P + Q * sqrt(2) > R + S * sqrt(2) holds.

That doesn't work in this case because we don't know P and Q and computing them wouldn't be very efficient (this is a localised floodfill algorithm not pathfinding). Multiplying by 10 is a good enough approximation for cases like this, since you can't really tell the difference between a circle with radius 14 compared to a circle with radius 14.14213562 (10*sqrt(2)) when we're dealing with tile based geometry. For efficiency purposes I wanted to use 1 byte (8 bit number) to store the distance to each tile, so if we multiply by 10 and round that means we can do that as long as our maximum radius is always less than 25.5, which it is.

[stijn263]

I see, still I liked the mathematical exercise . Is such a floodfill faster than a plain one-to-all dijkstra? (that stops when the distance is larger than 14)

[Lewin]

I see, still I liked the mathematical exercise . Is such a floodfill faster than a plain one-to-all dijkstra? (that stops when the distance is larger than 14)

I'm not really sure... we still store a 2D array of the shortest path we know to each tile (like dijkstra) but we also use pure recursion and pass the current distance we've walked through the recursion (like a floodfill). I think it's the fastest way, floodfills are very efficient as long as you have enough stack space and using dijkstra with a stack would be less efficient IMO.

[Danjb]

Clever, and very interesting!