A* in 2D grid with obstacles in between graph nodes

Question

I am using standard A* (and Jump Point Search) for pathfinding in my 2D game. A map in this game is a simple 2D grid (tile-based). A node (i.e. grid cell) in my map graph can either be blocked or walkable. That works fine so far.

Now I got a new requirement: There can be obstacles in between cells as well, i.e. walls. I thought the easiest way to implement this is to make the cell "behind" a wall an obstacle while searching for a path. However, that does not really work, because if I search for a path from the other side of the wall, then "behind" is also on the other side...

So my question: Is there any "best practice" to implement this, or, if not, what are your ideas?

Answer 1

A* is defined on a graph structure, which consists of nodes (cells) and edges between the nodes (i.e. the walls between cells, or corners). When you make an entire cell not walkable, you remove an entire node from the graph. When you place something between two cells, you effectively remove the edge which is normally there.

Most of the time the neighbors of (x,y) are (x+-1,y-1),(x+-1,y),(x+-1,y+1), and (x+-1,y), for a total of 8 neighbors. If a neighbor is not walkable, then you remove it from this set of neightbors. Likewise, if there is a wall between (x,y) and (x,y+1), then they aren't neighbors, even though they are adjacent. So you don't need to change the properties of the other cell, just filter it out when you are finding the neighbors of a certain cell. The important thing is that the other cell can have it's own distance and everything; you aren't removing it in any way. Instead you remove the edge between two cells.