5
\$\begingroup\$

I'm currently trying to convert from grids to navigation meshes for pathfinding, since grids are either too coarse for accurate navigation, or too fine to be useful for object tracking.

While my map is fairly static, and the navigation mesh could be created in advance, this is somewhat of a tower defense game, where objects can be placed to block paths, so I need a way to recalculate portions of the navigation mesh to allow pathing around them.

Is there any existing documentation on good ways to do this? I'm still very new to navigation meshes, so the prospect of modifying them to cut or fill holes sounds daunting.

EDIT: To be clear, I'm looking for solutions that use a polygon navigation mesh, not a grid. I currently use grids, but I'm trying to move away from using them. It is the efficient dynamic modification of that polygon mesh that I'm trying to figure out.

\$\endgroup\$
  • 1
    \$\begingroup\$ If you already have a grid generator, you can easily build an octree to optimize away useless grid cells, and generate your navmesh from that octree. \$\endgroup\$ – MickLH Jun 9 '14 at 2:34
  • \$\begingroup\$ I hadn't considered an octree/quadtree, thanks for that. However ultimately I'd like to get away from square grids entirely, as their axis alignment doesn't match the path angles I'm hoping to allow in my maps. Using grids currently means making a rough approximation of any angles. I'd prefer my navmesh not be limited by that approximation. \$\endgroup\$ – Nairou Jun 9 '14 at 13:11
  • 1
    \$\begingroup\$ You're not necessarily limited to generating the mesh naively from the quadtree, it's just a starting point, you can build a more accurate post process that circumvents the rectangular nature of a quadtree using line of sight tests for example. \$\endgroup\$ – MickLH Jun 9 '14 at 20:02
  • \$\begingroup\$ It is not clear exactly what you are doing now and what is the problem with what you are doing? Is the issue (of the question) splitting nav mesh cells into multiple cells? Modifying them when blocking objects are added to the map? \$\endgroup\$ – wolfdawn Jun 13 '14 at 7:49
  • 2
    \$\begingroup\$ david-gouveia.com/portfolio/pathfinding-on-a-2d-polygonal-map \$\endgroup\$ – jgallant Jun 13 '14 at 13:29
1
+50
\$\begingroup\$

I think you want Dijkstra's algorithm, which is also used for internet routing.

In short, you must create a graph where each edge is a path from one node to another. These could be pre-calculated if some of your geometry is fixed.

For each starting point, you will order the nodes according to their distance from the destination. Then apply Dijkstra's algorithm through the graph to build routing tables for each one. The first route in the table will be the shortest path. Each route after that will be a variation depending on which nodes are blocked. These extra routes could be calculated as necessary, provided their order is maintained in the table (they should be ordered by the sum of their edge lengths). You'll refer to these routes again when a node is changed (blocked/unblocked).

You can then add and remove nodes by splitting edges and moving the new midpoint, then recalculating from the origin node.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.