[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. :)

[sanderd17]

I think that a Dijkstra or floodfill based algorithm is best suited for this. Just use the pathfinder grid, and expand the tiles equally in all directions (no need for a heuristic, as there's no preferred direction). When a tile is found that is obstructed by the entity with the right class/component, that's the nearest one. When another obstructed tile is found, don't proceed.

And ofc limited to everything visible by the unit (so there's only a small search space).

[wraitii]

See IRC on 18/05/2016

[wraitii]

So there are actually two distinct issues here: the unitAI and the AI. This ticket is for the UnitAI part of the problem.

In this situation, the issue is that if the AI cannot find a good resource, the first thing it does is it looks for a fitting resource near the old one (in FindNearbyResource ). Really it should probably look for a fitting resource near the dropsite. Secondarily, even then on maps like acropolis the result could be unacceptable. In this situation, I believe a simple "hierarchical pathfinder" evaluation of distance, ie "how many of the hierarchical pathfinder tiles do we need to cross to get there" is probably a good enough fit. If you need to get around the acropolis, that count will get bumped up a lot.

Another solution, which is similar to what the AI does, would be to rely on some caching from the dropsite itself: if we compute the distance to closest resources once for the dropsite, we can very easily access the closest resource. We can even probably accept using some simple JPS for this, doing it over a few turns. This info could probably also be sent to the AI which would help with the AI side of the issue..

This solution is perfect only for non-moving resources, obviously, for moving resources perhaps we could recompute every now and then, or even only once, most animals don't move that much.

[elexis]

Backlogging due to lack of progress.