May unstable before version 1.0.0! Still in dev!
Hierarchical path finding on quadtree for equal-weighted 2D grid map.
Reqiures: c++ >= 20
In a rectangle with no obstacles inside, the shortest distance between two cells is a straight line. So we can use a quadtree to split the map into two kind of regions: completely obstacles and completely empty areas, and then build a graph on top to perform A* search.
Colors:
- White: Land.
- Red: Walls (buildings).
- Blue: Water
- Green: Agent and Path.
- Purple: Gate cells
- Yellow: Quadtree nodes on path.
agent-size=2, capability= Land  |
agent-size=2, capability= Land | Water  |
agent-size=2, lager map  |
agent-size=2, flowfield  |
- A QuadtreeMap is a 2D grid map maintained by a quadtree.
- The quadtree splits the grid map into multiple sections.
- A section on a quadtree map contains no obstacles or all obstacles.
- The shortest path inside a section without obstacles will be a straight line.
- Adjacent quadtree nodes are connected by multiple gates.
- A gate is composed of two adjacent cells, one on each side, directed.
- All nodes compose the 1st level abstract graph.
- All gates compose the 2nd level abstract graph.
- Path finding performs on the 2 or 3 levels graphs:
- Find the node path on the 1st level graph (it's optional, faster but less optimal).
- Find the gate path on the 2nd level graph.
- Fill the straight lines between gate cells.
- A QuadtreeMapX is a manager of multiple quadtree maps for different agent sizes and terrain types supports.
- A PathFinder always works on a single QuadtreeMap the same time. A pathfinding request is reduced into a progress without the agent-size and terrain factors.
To use it, copy away files under Source folder
API list can be found at Source/QDPF.h.
Install conan, and build:
make -C VisualizerRun the Visualizer:
./Visualizer/Build/QuadtreePathfindingVisualizer -w 100 -h 60 -step 1- Dynamical weighted A*.
- Height Map.
BSD.