A star pathfinding path too narrow for enemy

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.

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).

• Not really that clear on what you're saying, can you explain in more detail and perhaps give some images to show what you mean? I don't see what the difference between this and just making the grid all 32x32 is...but your explanation is not clear so not sure. Commented Jun 24, 2020 at 9:35
• @Hasen I added a bit more illustration to my answer. Commented Jun 24, 2020 at 9:49
• I think your example is not so great, it's a map with almost every tile impassable and then with dilation every single tile is impassable... What would it look like with the impassable tiles in my example image above with the green barriers? Still can't see how it's different to a simple 32x32 pixel based grid? If you're expanding 8x8 by 4 then that is just 32x32 is it not? Commented Jun 24, 2020 at 10:02
• @Hasen I updated the example to be a bit more relevant for your usecase Commented Jun 24, 2020 at 10:11
• Ok thanks. So what exactly is a 2 tile? I mean I realise it's the expanded tiles but what is that in real terms on the grid? They are all impassable tiles? Commented Jun 24, 2020 at 10:16