GridGraph walkable vs tags

General Grid graph
1

Hey,

So I’m making this game that plays on a grid-based level, so I’m using a GridGraph for pathfinding. I created a GridGraphRule that sets nodes walkable based on the type of the cell at a given position. As currently all agents move in the empty space it works great. In the future we would like to have enemies that can only move inside the walls (so essentially the inverse of the graph). I assume that node walkability is a stronger concept than tags, so if I set a node to non-walkable no Seeker will be able to navigate that area no matter how I set up tags. The naive solution would be to use 2 graphs, but that case I would need to keep both updated as the whole environment is destructible. So what I’m thinking about is to instead of setting node walkability introduce a tag for non-empty space (or probably more depending on cell type) and set that tag to non-walkable for most of the agents, while enemies that move in walls would only be able to walk on that tag.
My question is if there would be any problem with this setup, even from performance perspective? I’d assume there is a reason non-walkable is its own property and not just a tag, but it might be due to historical reasons.
Thanks

2

Hi

Marking nodes as unwalkable has the benefit that the pathfinding system does some pre-processing to be able to immediately query if a given end point is reachable from a given start point.

With tags, you can have pretty severe performance drops if you happen to request a path to a point that cannot be reached. Because in that case, the path will have to search through every single node it can reach. Which might be a lot, if the graph is large.

If the destination was not reachable due to an unwalkable node, the path would instead short-circuit and return an error immediately.

1 Like
3

Hey,

Thanks for the quick answer. I plan to mostly use RandomPath and FleePath to get a target destinations so having an unreachable destination should not happen very often. Would you expect tags to have worse performance compared to walkability with those methods as well? Would you recommend going with the two separate graph approach instead?

Thanks

4

For those path types, the difference shouldn’t be significant.

1 Like