Swamp / dead end pruning in non-mesh nets
Are there existing algorithms for finding and eliminating problem areas ( swamps , dead-end ) in finding a way when using non-network maps? There are many meshes available that either avoid these areas, or pseudo-avoid these areas by recursion of the jump point , etc., but I still have something useful to find for quadrants, nav meshes, or other uneven maps.
source to share
Such a thing probably exists - hundreds of pathfinding and traffic planning articles are published every year, but I think you need to ask yourself the more important question: why do you want to do this?
The idea behind moving to a grid or sparse grid is to reduce the time required to find a solution by reducing the number of nodes on the graph. If your search is too slow, just trim the number of nodes and edges in your graph. By manually removing any dead ends from your offline search before you start, you will reduce the overhead for each search.
If even after you've cropped your graph the search still slows down and you can tolerate rough solutions to search problems, consider using Weighted A * , where you rearrange, decreasing the inflation rate until you get the optimal value.
Scheduling algorithms are full of trade-offs, just make sure you understand what the pros and cons are for what you decide to do.
Next final suggestion, make sure you apply the primitives correctly in the scheduler you are using - algorithms like A * depend on the correct implementation of priority queues, in particular, make sure the decrement key is O (log n) or better .
source to share