travel path calculation

[DylanDog]

Hello

I think the AI engine is really ok and allows to develop good AIs but possibly there is one thing missing which could be worth to be implemented: travel distance calculation.

With this I mean the real travel distance,between two points, to cross for a droid (not VTOL!).

something like: getTravelDistance(int x1,int y1,int x2,int y2)

Nowadays you can only use distBetweenTwoPoints() which returns the linear (air) distance between the two given points. This is used in many parts of all AI scripts, for example to get the nearest oil Resources, but its reliability for such purposes is not 100% ok.

I know that this could be really hard to implement but if you managed to get droidCanReach() working maybe it is possibly to get this new feature too.

[Per]

Yes, I know. This is really needed. However, it is not easy. The basic problem is that path-finding is expensive. If you hog the cpu while you wait for it, you really hurt frame rates. What we can do, is push a path request to the path finding work thread, then pick up the answer later (in another frame) when it becomes available. However, this is really hard to program for, since you need to keep a lot of state between script executions just to remember what you were doing and why you wanted that path in the first place.

I think the only logical way of handling this is by putting each AI script into its own thread, so that blocking or running a long function does not impact on the running speed of the rest of the game. To avoid race condition hell, we would have to create command queues to handle script results. (We may have to create such a command queue anyway to handle network sync properly, so there may be some overlap with other work.)

None of the above are simple to implement, though. If anyone have other ideas, feel free to share.

[crux]

why not precalculate all possible paths on map load then use a lookup table to find best path?
maps are only 250x250 max right?

[KukY]

why not precalculate all possible paths on map load then use a lookup table to find best path?
maps are only 250x250 max right?

Great idea. That may make pathfinding engine almost useless(=lower CPU usage)!

[Zarel]

why not precalculate all possible paths on map load then use a lookup table to find best path?
maps are only 250x250 max right?

Yes, which means, assuming 128 bytes per path, that would only take up 500 GB of RAM, which would need to be recalculated each time someone builds a structure.

[milo christiansen]

Just move it to the HD xD

[Black NEXUS]

500 GB RAM, OMG

Is this really so heavy?

[Samowar]

Is this really so heavy?

Nearly. 250*250 tiles makes 62'500 tiles overall. Now let's assume only ~40'000 of them are considered for pathfinding, the rest is impassable terrain. Now from each of these 40'000 tiles you have to find a way to each of the 39'999 other tiles. This makes ca. 40'000*40'000 = 1'600'000'000 paths. As every path also works in reverse, we have 800'000'000 effective paths. Assuming we need 2 bits to encode one step of a path and limit path length to 512 (which just barely allows you to traverse the map from one corner to the opposite corner), we need 1024 bits, or 128 bytes per path. 800'000'000 paths à 128 bytes makes 102'400'000'000 bytes or ~100GB. Too much to stuff it into the RAM and inconvenient even to store it on the HD.

Now what could be possible however: At the start (by some clever algorithm or just by the map designer himself manually), the map is partitioned into several smaller and larger "unobstructed areas" and a graph is constructed with all connections between those areas. You don't need expensive pathfinding to drive inside one such area; you can just take the straight path. Now if your destination lies in another area, you perform pathfinding on the graph from your area to your destination's area and, once inside the destination's area, drive straight to your actual destination. This would probably be less computationally expensive (but perhaps still too much) and it would always give a sensible path (no more stuck units). I'm not sure, however, if this path would always be the shortest path. And it's certainly annoying to see your units perform miles of detours where they could have driven nearly straight. Plus, it doesn't take into account buildings blocking the way (except if we recompute the areas and the graph every time something is built...)

[Per]

Now what could be possible however: At the start (by some clever algorithm or just by the map designer himself manually), the map is partitioned into several smaller and larger "unobstructed areas" and a graph is constructed with all connections between those areas. You don't need expensive pathfinding to drive inside one such area; you can just take the straight path. Now if your destination lies in another area, you perform pathfinding on the graph from your area to your destination's area and, once inside the destination's area, drive straight to your actual destination. This would probably be less computationally expensive (but perhaps still too much) and it would always give a sensible path (no more stuck units). I'm not sure, however, if this path would always be the shortest path. And it's certainly annoying to see your units perform miles of detours where they could have driven nearly straight. Plus, it doesn't take into account buildings blocking the way (except if we recompute the areas and the graph every time something is built...)

You are pretty much describing the zones system that the original game had. I ripped that out precisely because it had all of the problems you describe above, and then some.

[Samowar]

Well, if it really were such a good idea, it would be strange if someone hadn't implemented it before .

[Per]

I've been thinking that we could generate a full movement map from the Command Center every second or so, then query that from the AI. I think it will be a useful approximation, as most AI movements happen from the base anyway.

[nobby]

why not precalculate all possible paths on map load then use a lookup table to find best path?
maps are only 250x250 max right?

All pairs shortest path calculation is O(N^3) or thereabouts (Floyd's algorithm IIRC). It also requires a fair bit of storage, O(N^2) for a 2D array based implementation. For a 250x250 map, you would need 65200 * 62500 * 2 (probably a min of 16 bits for each entry) bytes, or about 8GB. You might be able to cut this somewhat by using a sparse array of some description, but this is unlikely because the connectivity isn't very sparse - most maps have >50% of the squares accessible from any other square.

Additionally, it is possible to do things during the game that can obstruct certain paths (like building walls), so a static map won't suffice in all cases as it would need to be recalculated when anything was built.

[Terminator]

Yea , I've thought about pathfinding & precalculation seems would be better if It could be implemented. & in current wz(master) version this stacking units issue should be solved so to improve overall playability.

[Goth Zagog-Thou]

I experimented with my own modified builds using 500x500 maps and it locked up as soon as we crossed into tile 251+. I'd love to get pathfinding working for sizes up to 1000x1000 -- and believe me, I could fill up a map that size with all sorts of interesting things. I looked at the code and it *seems* possible if we use the grids system like above. Perhaps four 250x250 grids could work?

[Per]

Just increasing the limit would be easy. Making it not suck all performance out of the game, now that is another question altogether. Things like path-finding can react very badly to more available space (eg you may not know that a solution is not found unless you search almost the entire map). I think increasing the map size is one of the things we should not prioritize at the moment.