How to deal with different sized objects in a pathfinding situation (A*, A-star)

Question

I'm working on a game that uses A-star (A*) for path finding but I've come to a point where by I have some objects that are larger than a single grid square.

I'm running on a grid of 16*16px. wall segments are 16*16 and so make a single square impassable. Some of my baddies are 32*32 and so they need to check that a gap is at least 2 grid square wide in order to be able to pass throguh it.

I can't simply make the grid 32*32 as the design requires thin walls (at 16px) and there are a couple of smaller baddies that only take up a single 16*16 square.

How do I implement this mutli-resolution environment? Is A-star still the correct tool to use?

Answer 1

http://aigamedev.com/open/article/clearance-based-pathfinding/

Answer 2

For a relatively simple solution, I would stick to the same A* algorithm as for 16x16 sized objects but with a slightly different way to evaluate if a square is walkable or not.

• A 16x16 sized object can walk on a square if that square is walkable.
• A 32x32 sized object can walk on a square if that square and its' neighbors are all walkable.