How can I explore a path with A* (or another) by taking care of a rectangle collision ?

I have a 2d map, where I know for each coordinate if it is an obstacle :

map view with Tiled Map Editor software

For example, dark tiles are not traversable :

map view with my game engine

I use A* algorithm to find path, where for a given point, all around successor are possible with a variable cost. There is a visual example (game is top view):

path finding example

How can I make a A* (or other) algorithm taking care of obstacles for a (for example) vehicle ?. In the previous image example, a man can use this path, but tank. should not


1 Answer 1


You can generate a different graph for a different kind of unit.

For example a graph for humans, a graph for land vehicles, a graph for water vehicles, and so on.

And there is no change to the algorithm. The difference is that each graph is created considering the space and the type of terrain that the kind of unit requires.

And yes, that means it would be convenient to have some standard spacing so you don't have to create graph for each individual unit type, but you can reuse them for similar unit types.

For clarity: A square grid is a kind of graph, and this approach is not limited to square grids.


You must log in to answer this question.

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