Improve Pathfinding

[DudeMcDude]

This will be a thorough overhaul, probably including switching to navmeshes, and including support for danger areas (AoE / AoO) for the AI to consider.

[DudeMcDude]

Issuse with long-distance pathfinding (pathnodes):

• In some cases, connectivity is not reciprocal, i.e. A lists B as neighbour but B does not list A as neighbour - see Hommlet node ids 0x291 and 0x292 for example.
• Retarded cases like this: Caused by nodes being physically close (and thus register as such for A*) but in practice requiring a long walk. Causes pathing failure because they eat up a lot of path subnodes (in this case 127 for the two sides of the fence!)
• Pathnodes in some cases (like Hommlet) are clearly auto-generated on a regular grid, which makes their utility questionable in the first place.
• The short-range pathfinding can be quite inefficient due to the method of collision detection (it runs this for each A-Star step).

[DudeMcDude]

Current state of pathfinding:

Improvements:

• Added Clearance information for most Co8 maps of interest to speed up the short range A-Star
• Calculated actual pathnode traversal distance to prevent situations like the above screenshot
• When the above info is available, it will rely on short-range pathfinding for longer distances, which should prevent such oddities
• PF will always attempt a straight line first, which is often sufficient for open areas.
• When using pathnodes, it will now try a short-range pathfinding using the dense grid for going from the before-last pathnode to the destination, in order to prevent the awkward zigzagging at the end.

Remaining deficiencies:

• Medium-range pathfinding can still produce zigzags, especially when the destination is a critter. (will be solved by NavMeshes)
• Pathnodes still do not contain "zone" information, and the pathfinding selects as destination the closest pathnode by distance to destination. (will be solved by NavMeshes)
• Lack of planning for AoO / AoE avoidance (partially implemented)
• The dense sub-tile grid is not always high-resolution enough (might be solved by flow-field navigation)

These will likely wait for v1.2 as the current situation is not too bad, and implementing the above solutions is a considerable effort.

[Felipefpl]

Any improvements about what is remaining? I'd love to see pathfinding finally being decent. (although the improvements above surely are nice) :)

[DudeMcDude]

Hi! Sorry, but this is not a high priority for me.

[Felipefpl]

Ok then.