I would like to determine accessibility of nodes before applying pathfinding algorithm to Grid Graph.

I have a surface with nodes overlayed on it and I would like to somehow determine that nodes inside yellow region are unreachable from outside of it (from behind the wall).

enter image description here


1 Answer 1

  1. Choose a walkable node.
  2. Flood-fill it. Any square not filled is not reachable from the chosen square.
  3. Repeat the above with another unfilled walkable node to find another separated region.

If you do this completely, you will have a list of connected regions of the map (a partition of it into connected components).

If your map is static, you only need to do this once. Otherwise, it's still not hard: If a node becomes unwalkable, rerun just on the component containing it and you may find you have two components. If a node becomes walkable, then if if it has immediate neighbors from two different components, combine them.

  • 2
    \$\begingroup\$ Note that Kevin is suggesting doing this once when your map is loaded, not every time you want to find a path. \$\endgroup\$ Commented Jan 8, 2013 at 19:13
  • \$\begingroup\$ Yup. Once when your map is loaded and possibly again when the walkable areas have significantly changed.(for instance when a previously closed door is opened and now is traversable) \$\endgroup\$
    – Qqwy
    Commented Jan 8, 2013 at 19:46
  • \$\begingroup\$ I've added info on what to do if the map changes. \$\endgroup\$
    – Kevin Reid
    Commented Jan 8, 2013 at 22:34

You must log in to answer this question.

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