[PATCH] Use the pathfinder to perform distance checks

[andrew123]

In this situation (acropolis map), workers finish a tree, and the closest one is downhill so they leave the base.

It would be nice to compute the actual move cost instead of the distance in this type of situation.

[historic_bruno]

It's hard to tell what's going on in your screenshot due to the perspective. In my tests, units always choose the nearest tree, but it may not be the shortest walking distance (it only tests straight line / as-the-crow-flies distance). This works well enough in most cases. Maybe the new pathfinder design will make it feasible to search for the nearest resource by walking distance.

[FeXoR]

It is not always the best to get the resource closest to the depleted one gathered from before but to choose the resources of that type with the shortest distance to the building the resources are brought to. Since the first target to gather from is a player given command - and I think this should be higher priority than any wild guesses - it may still be the better choice to take the resource closest to the last on gathered from. However, the point the player gave the order to would be even better for minimizing the distance to - though that point would have to be stored somewhere then even if there's no entity left there.

[Deiz]

The root issue being that the distance-to-target used is simply a comparison of positions. That case only works well for open maps, and come to think of it, it's probably a large part of why the AI tends to stumble majorly on Acropolis-style maps.

To my knowledge, the current pathfinder doesn't expose any distance information, so there's no trivial way to compute actual walking distance to a target.

[Stan]

Pushing it to A19 since its related to pathfinder

[wraitii]

Bumping back, this could probably be fixed somewhat easily by using the hierarchical pathfinder, at least the worst cases.

[Matthew Guttag]

Modifies the Pathfinder to optionally, add return the heruistic cost of the path, then allows this to be access in javascript though the unit motion interface. Modifes the resource dropsite, resourse, auto garrison, and nearby foundation finders in UnitAI to use this new code. Fixes the issue where units would go to a clearly wrong resource/dropsite/foundation when on an acropolis.

[Itms]

Thanks for that patch!

Unfortunately, I'm afraid this approach will be far too expensive and will slow down the game a big deal. You're calling ComputeJPSPath synchronously and multiple times for every entity which calls FindNearest, which can happen for a handful of entities each turn.

A better approach would be to use the hierarchical pathfinder. It cuts the map into chunks (you can see them with the Hierarchical Overlay, if you toggle the developer overlay with Alt+D in-game). You can then take a look at whether the closest entity determined by the range manager is in the same chunk as the unit. If it doesn't, a naive thing to do would be to try to find one nearby entity that is in the same chunk; a more sophisticated solution would be to implement a new function for the hierarchical pathfinder that computes the distance in terms of chunks crossed, and you would discard the target entity if you need to cross more than two chunks for instance.

I hope that what I wrote here is clear. Don't hesitate to ask me to connect to IRC if you want to discuss anything, I'm a bit AWOL but I can make myself available to give you pointers. :)