Adventures in Shade 04: Dabbling in Pathing I

By | September 4, 2014

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!

Bitmap-based dungeon generationPathfinding: 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.
As you can see in the above picture, there’s a square-shaped hole in the middle of the navmesh. Solid barriers in our dungeon (treasure chests, Trundle-like pillars, etc), will add holes to the navmesh! For now, I’ll be fully retriangulating the scene (or cell) on every obstacle modification – there’s definitely a ton of space for optimization here, but I’m hoping performance won’t be an issue due to my low polygon count and infrequent duration of hole modification. This approach will, in fact, make a few other operations a bit kludgy – for example, I’ll have to add special cases for pathfinding to obstacles. If the player were to pathfind to a treasure chest, I’d have to include the treasure chest’s navmesh hole in the pathfinder’s graph search.

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!

Michael “ItzWarty” Yu

Loading Facebook Comments ...

Leave a Reply

Your email address will not be published. Required fields are marked *