A* with wall based tiles

Game Mechanics Artificial Intelligence
#1

Hi guys,

I’ve been trying to build a path finder for my game. As you can see by the pic below, this is using walls instead of simple blocks. I’m not sure how this is affecting the algorithm. Samples I’ve seen use tiles where each coordinate is either blocked or not. In my case each coordinate may be blocked only from a particular direction.

Any tips on how I could do the algorithm differently?

#2

A* should still work the same. When you generate the neighbors, you just exclude any for which there’s a wall in the way.

#3

The algorithm itself does not need to be changed. A-star can work on any type of graph. A grid is a graph. Graphs have nodes and edges. Nodes are the places your search algorithm can visit. Edges are the connections between nodes.

Empty grids have graphs like this:


+E+E+E+E+E+E+E+E+E+E+
E E E E E E E E E E E
+E+E+E+E+E+E+E+E+E+E+
E E E E E E E E E E E
+E+E+E+E+E+E+E+E+E+E+
E E E E E E E E E E E
+E+E+E+E+E+E+E+E+E+E+

Grids with occupied squares have graphs like this


+E+E+E+E+E+E+E+E+E+E+
E E E   E E E E E E E
+E+E+   +E+E+E+E+E+E+
E E E   E E E   E E E
+E+E+E+E+E+E+   +E+E+
E E E E E E E   E E E
+E+E+E+E+E+E+E+E+E+E+

Grids with walls on their cell edges have graphs like this:


+E+E+E+E+ +E+E+E+E+E+
E E E E E E E E E E E
+E+E+ +E+ +E+ +E+E+E+
E E E E E E E E E E E
+E+E+ +E+ +E+ +E+E+E+
E E E E E E E E E E E
+E+E+ +E+E+E+ +E+E+E+

When adding nodes to the list you add the neighboring node [icode]if(!grid.edgeBlocked(currentCell, aNeighbor) && !grid.isOccupied(aNeighbor))[/icode] instead of [icode]if(!grid.isOccupied(aNeighbor))[/icode]

#4

OK thanks. :slight_smile: That means I just have normal bugs but I don’t have to tweak the algorithm itself.

#5

Another common option is to have weights for cells…and unpassables have very high weights (just additive values).

#6

The problem with high weights for impassable cells is that A* will take these cells if there is no other way to get in. e.g. if the target lies in an isolated area. If this behaviour isn’t desired, then it’s better to not include these impassable cells, as sproingie and Best Username Ever already said.

#7

Context dependent, but a very good point. I was thinking in terms of weights related to movement cost, so it isn’t possible (well…unless you support a god mode) in that case. Of course there’s the pruning issue as well. Ignore me and move along.