Threading and better distance metrics for Pathfinding
This is a discussion on changing our pathfinding algorithm to use better distance metrics as well as incorporate threading.
Whiteboard
The pathfinding algorithm currently is implemented as a special case of A*, which is Dijkstra's algorithm (all things weighed equally). This falls apart when a user has large areas with many connections, as the search space grows at a rapid pace in all directions.
This implemention is designed to account for a fundamental issue with MUD maps, they do not have to be spatially coherent -- especially between areas. Therefore things like euclidean distances are not applicable when transversing areas. To address this, I propose breaking the problem into transversing the zones individually -- where distance metrics will apply since they are on the same coordinate system. This is also inherently parallelizable, as we are chunking the work.
So implemention wise -- we make 2 maps. One is our current map in which all parts are interconnected, and the other is a new map of all the exit nodes from an area. Then we break the problem into 4 parts:
1) Find the paths from the current room out of the area
2) Find the paths from the end room to the start of its area
3) Find the paths on the new exit-node-only map (which will be small) which connect those rooms.
4) Pick the shortest combination of choices.
This will add more work for simple paths, but drastically reduce time for more complex paths -- especially those from larger areas. However, for the short cases the additional time encountered thus far is not noticably different and for the complex cases it's orders of magnitude faster (from 7-8 seconds down to milliseconds).
Some caveats:
Areas with MANY exit/start nodes -- we are calculating a lot of useless paths potentially. A potential workaround is to choose the closest node that has a complete path, and deal with things like teleporters with a 'wormhole' type flag that will cause the mapper to consider that room as well as the closest via the other metric, and then choose the cheaper of the 2.
The current work can be found on my pathfindingRevision branch:
https:/
