Pathing! What fun!
After yesterday’s post on picking and ray-to-convex-polygon intersections, we were able to move our hero around our plane. Now, our hero can walk along an arbitrary path (a collection of points) at an arbitrary speed!
In order to find these paths, I’m generating a navigational mesh (navmesh for short) which is passed into a pathfinder. I’m not yet done here, so the rest of this post will be largely speculative
Navmesh and Rendered Path!
Pathfinding: Notice line stemming from our hero.
Navigational mesh: Triangulation drawn in cyan, graph links drawn in red.
I’m no expert in the field, but pathfinding involves lots of graph theory and computational geometry; things get complicated when you consider holes, obstacle avoidance, character radius when wall-hugging, etc…
I’m mainly debating on two things:
- Navmesh on Hole Update: Full Retriangulation vs Update Triangulation
- Navmesh: Spanning Entire Dungeon vs Per-cell Connected via Waypoints.
Of course, full retriangulation will only meet my minimum demands. Through constrained Delaunay triangulations, I’ll potentially be able to regenerate navigational meshes after holes are removed or added, only affecting a portion of my graph as opposed to regenerating the entire graph.
If we partition the navmesh by cell, then we’ll have to deal with routing between cells. Fortunately, this doesn’t seem too difficult with waypointing – picture four entrances to each cell, placed in the middle of each side. We can treat these entrances as nodes on a graph, and we can easily compute the distance between nodes in a cell via our navmesh. With weights for each edge, we can perform A* to get an approximate path.
That’s all for now!
Cheers,
Michael “ItzWarty” Yu
