Pathfinder sometimes creates inefficient paths

[stefanhendriks]

Using A* algorithm, see also: https://www.youtube.com/watch?v=-L-WgKMFuhE

Regardless.

It looks like bots, especially when retrying connections, they re-create a path that seems to go way around only to end up at the same place they started from and continue from there.

Ie:

For testing #17 i noticed the bots detected this wrong connection, but then went way back and retried. Not only going back one node but several.

Now I removed all the danger/contact heuristics already and it still happened. The heuristic is quite simple:

cost = distance from open node to destination + distance from open node to start vector

where start vector is the start of the path. Since this is testing as_oilrig which is a vertical map, I suspected the inefficiency came from the height of the map. Ie, some nodes, although going backwards horizontally are closer to the target vertically.

I removed that complexity by setting the z axis for all vectors to zero so we compare as if we were on a 2d grid. This reduced the inefficieny a bit, but still there is some.

I wondered if this is due to the algorithm, or something else going on.

It is almost as if not all nodes are connected as expected (ie, it would overwrite open connections with better scores).

Another way would be to run some final check over the created path:

• for each node in path
• check if there are future nodes in path that this node could reach, if so skip to that node and remove all nodes in between, ie:

[0] = node 100
[1] = node 200
[2] = node 201
[3] = node 190
[4] = node 99
[5] = node 110

suppose 100 could reach 110, then starting from index 0 it would check if node 100 could reach 200, 201, 190, 99, and at last 110. If it concluded that 110 is reachable, it would reduce the path to:

[0] = 100
[1] = 110

Still, this feels like solving a bug somewhere in the heuristic. Or perhaps this is just because of the drawbacks of A*?