Delete "Unused" Nodes from GridGraph?


#1

I am using GridGraphs for enemy pathfinding in a top-down action game. I’ve chosen to use GridGraph because I need to make fairly frequent graph updates (such as destroying walls, opening doors, moving crates, etc – DynamicGridObstacle is fantastic :heart_eyes:) and because I am procedurally generating levels in a similarly grid-based fashion.

However, I have noticed that I am generally building levels that have large chunks of unwalkable area in them. I understand that this is one of the trade-offs of using a GridGraph because it’s fundamentally square (while interesting levels are often irregularly shaped), but I am curious – since I know (as a level designer) that some areas of the level are unwalkable and will never become walkable, would it be possible to manually delete all the “unused” nodes in these areas to improve performance?

So:

  • Is it possible to delete nodes from a GridGraph? Would it break everything forever?
  • Would there even be any (noticeable) performance improvement in doing so? (Maybe on larger graphs? Currently looking at 240x240 with node size 1 and about 20 seekers floating around, but dreaming bigger in the long term.)
  • If yes to both of the above, what would be the best/safest way to go about it?

#2

Hi

Unfortunately this is not possible. The grid graph can make a lot of assumptions to simplify things when all nodes are present. It wouldn’t improve performance in any significant way in any case, though it would reduce the memory usage.

If you want to improve performance, try enabling the ‘Use Jump Point Search’ option in the grid graph settings. It might help.


#3

Makes sense, thanks for the confirmation.


#4

I’m currently working on an infinite procedural terrain and removing unused memory would be really beneficial. Does enabling the ‘Use Jump Point Search’ option improves the memory footprint? I don’t want my user to reopen the game after playing for few mins.

Thanks


#5

Hi

Jump point search will not reduce the memory usage, in fact it will increase it slightly.
You can open the ‘Optimizations’ tab and enable ‘ASTAR_GRID_NO_CUSTOM_CONNECTIONS’. That will reduce the memory usage by about 8 bytes per node (assuming you don’t use any off mesh links or other things which require custom connections on grid nodes). You could also enable ‘ASTAR_NO_PENALTY’ if you don’t use penalties (tags are handled in a different way and don’t count as using penalties for this purpose).