Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 9 down vote accepted
  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.

share|improve this answer
2  
Note that Kevin is suggesting doing this once when your map is loaded, not every time you want to find a path. –  BlueRaja - Danny Pflughoeft Jan 8 '13 at 19:13
    
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) –  Qqwy Jan 8 '13 at 19:46
    
I've added info on what to do if the map changes. –  Kevin Reid Jan 8 '13 at 22:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.