Finding the "Important" nodes of a grid path

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?

• 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) Jul 6, 2015 at 8:12
• 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. Jul 6, 2015 at 13:55