A* width edges

[Rick]

Has anyone done A* on a 2D grid where edges are considered being passable or not, not just entire nodes? Think original Sims where you build walls between nodes. If each node has 4 variables for edges that represent open/wall, when looking to consider if a neighbor node is walkable, would things still work if you check the current nodes 4 edges and if there is a wall there don't check that neighbor at all (this would assume the nodes share the edge value of wall).

 

Has anyone done something like this before or the people who are more experienced in A* does this sound like it could work? If so I'll give it a shot for a small test I want to do.

[flachdrache]

If generating a navgraph one usually removes non-valid edges between nodes in a post step e.g. if a node is inside a entity aabb remove the node or if node A cant see node B ( blocked by a wall ) dont link these nodes ( north-west-south-east ). MG had something implemented for dynamic obstacles - i dont know how he solved that, however.

[Rick]

OK, that seems like sort of what I was thinking then. When checking adjacent tiles if there is a wall on 1 edge just skip that adjacent tile (basically removing the link). I'll start giving that a go.

[AggrorJorn]

Hi Rick,

 

I actually made this for a school project. The way you describe it is perfectly fine for this. First you check the edge which is adjacent to the tile you are coming from. When there is no wall there, you can start looking for the other 3 (if you have square tiles) walls.

pseudo:

1. Check the tile next to me is walkable (water, lava etc)
   
2. Check the origin-tile edge with the adjacent-tile edge.
   
   1. 
      
   2. There is a wall? Done
      
   3. There is no wall?
      
      1. Check if the adjacent tile has 3 other walls (excluded the one you allready checked).
         
         1. If it has 3 walls: done.
            
         2. If it doesn't have 3 walls: Continue search algo.