A star pathfinding path too narrow for enemy

Question

The tiles for my top down 2D shooter are 32x32 and the player and enemies are too. But obstacles like walls and other things can of course be smaller than this - the smallest being 8x8. This causes a problem where a single 8x8 barrier intruding in a 32x32 tile will cause that whole tile to be impassable if my AI Grid is based on 32x32 tiles, like as follows:

This results in a grid with more impassable area than it should have. (On the left the red being the AI grid's impassable area, and on the right, the green being the box2d barriers for the same map section).

The other option is to make the grid 8x8 based and then the grid will perfectly calculate the actual impassable areas but it will create paths too narrow for the 32x32 enemy to pass through. With design I can make the first way (pathfinding grid of 32x32 tiles) work but it's not ideal since you're limited to placing everything in perfect tiles so as to not create impassable areas that are in fact passable.

Answer 1

You can make your grid 8x8 and expand all impassible tiles into a 4x4 patch of impassible tiles. Or in other words a tile is impassible if any of the tiles in a 4x4 region around it is impassible.

Then you can path find based on a 1x1 entity on that modified grid and when you make an entity follow that path you expand it's location opposite as you expanded your walls (swap left and right in your expansion).

In effect I created the minkowski sum between the obstacles and your enemy's hitbox. That way you can shrink the bounding box of the pathing agent to a point. This technique is also called dilation.

To copy give an example, take this map with 1 as impassible tiles and 0 as walkable.

0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 1 0 0 0 0
0 1 1 1 1 1 1 0 0 0 0 
0 1 0 0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 

with a 4x4 dilation (2 up and right, 1 down and left) this turns into the following map with 2 as the expanded tiles:

2 2 2 2 0 0 0 0 0 0 0 
2 2 2 2 0 0 0 0 0 0 0 
2 1 2 2 0 0 0 0 0 0 0 
2 1 2 2 0 2 2 2 2 0 0
2 1 2 2 2 2 2 2 2 0 0 
2 1 2 2 2 2 1 2 2 0 0 
2 1 1 1 1 1 1 2 2 0 0 
2 1 2 2 2 1 2 2 2 0 0 
2 1 2 2 2 2 2 2 2 0 0 
2 1 2 2 0 0 0 0 0 0 0 
2 1 2 2 0 0 0 0 0 0 0 
2 2 2 2 0 0 0 0 0 0 0 

Note de lack of notch in the bottom edge of the wall (a 4x4 entity wouldn't be able to fit in there) and presence of a notch in the top edge of the wall (where a 4x4 can fit).