1
\$\begingroup\$

On a Navmesh Grid, all nodes are essentially vertices or turn-points so the returned path is efficient in that it only involves points where an entity must change its direction.

A grid path, however, involves nodes at every point along the path. For long paths, there could be hundreds of nodes contained even though most of those nodes just follow a line and don't change the direction of the path.

Note: Paths are lists of a GridNode object.

I haven't tested this hypothetical issue in application yet so my first question is: Is this even an issue? For a game that requires real-time pathfinding for roughly 200 entities on a grid of 4,096 nodes, will the returned paths consume too much memory and resources? My main concern is related to how entities will handle paths, which is to check for reaching the target node before moving on to the next one and calculating the new direction needed. With more spaced out nodes, entities might have more leeway with following their paths if pushed off of it.

Secondly, if it is a potential issue, how would I solve it and cull out the insignificant nodes of a path?

\$\endgroup\$
2
  • \$\begingroup\$ a grid of 4096 nodes is 64 on a side so 200 entities will take at worst 128*200=25600 nodes in the path going corner to corner with no diagonals (or obstacles) \$\endgroup\$
    – ratchet freak
    Commented Jul 6, 2015 at 8:12
  • \$\begingroup\$ Note that as you increase the size of your map, the number of grid nodes in a path increases linearly, but the cost of finding a path tends to increase quadratically. So if you're pathfinding over a regular grid instead of a sparse mesh, the pathfinding cost is more likely to be a limiting factor than the path-storing cost. \$\endgroup\$
    – DMGregory ♦
    Commented Jul 6, 2015 at 13:55

1 Answer 1

Reset to default
2
\$\begingroup\$

At 4096 nodes, it's probably not an issue. The pathfinding should be fast, and the resulting paths will be pretty small.

The simplest approach to reduce the number of nodes on the paths is to first find the path on the grid, and then use "string pulling" to eliminate most of the nodes from the resulting path.

If you're working with a large grid you might want to reduce the graph to just the places where you need to turn. It's every grid node that's a "convex corner". Here's an example (interactive demo here):

Waypoint graph made from a grid

You may be able to do this as part of your map editor or map generation algorithm, or you can write an algorithm to find these points and edges. I have an unfinished page here that runs a brute-force algorithm on Bioware maps. There are also much more clever algorithms; see one demo here (800x800 grid, ~1ms to find a path in javascript), or look at this paper from the grid-based pathfinding competition to learn about lots of other techniques that people use.

\$\endgroup\$
1
  • \$\begingroup\$ Scanning before-hand for important nodes on a grid never occurred to me. It's kind of like a navmesh on a grid. In perspective though, for my case, I don't think I'll need to do this but I hope your answer helps others with larger maps in need of more optimization. \$\endgroup\$
    – JPtheK9
    Commented Jul 6, 2015 at 17:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .