# How do I handle objects with a width and height in grid-based pathfinding?

I'm using the Jumper library for Love2D to do grid-based pathfinding, which worked fine until I wanted to make larger enemies (with larger collision boxes). How do i do that?

My initial idea was to make a new map for each entity that needed pathfinding I could make a new map, with all the objects scaled up in size, but that seems way to complicated.

To give an example, I could have a wall with a passageway that is wide enough that my player has no trouble walking around it, but a giant ogre would have to walk around.

• I think anyone using any grid-based pathfinding library might face the same problem, so I edited with that in mind. I hope that's OK! – Anko Apr 21 '16 at 1:17
• this is the same question as gamedev.stackexchange.com/questions/14009/… – Julian Apr 21 '16 at 3:12

Store inside each entity not only its position, but also its size. Then you can reconstruct the collision map from your entity list, something like this:

-- [ Assign 0 to everything in the map. ]

-- Then block out a 1 for each square within the entity's size
for _, entity in entities do
local pos = entity.position
for xIncrement=0,entity.size.x do
for yIncrement=0,entity.size.y do
map[pos.x + xIncrement][pos.y + yIncrement] = 1
end
end
end


The entity's position represents its top-left corner and the size the number of squares it occupies in the x and y directions.

Then just use jumper as usual.

• I was not trying to make obstacles with width or height but instead have the entity trying to navigate the obstacles have width and height – Julian Apr 21 '16 at 2:21
• @Julian The Jumper library already does the pathfinding for you. I'm suggesting a way to construct a map with the right sizes of obstacle, so it could be passed to Jumper. Did I misunderstand? Maybe it would help to edit the question with further details. – Anko Apr 21 '16 at 2:45

One way to implement this is to use clearance, and have all of the tiles around obstacles contain numbers represent their proximity to the object for example a map that looked like this:

map = {
{0,0,0,0}
{0,1,1,0},
{0,1,1,0},
{0,0,0,0},
}


would look like this:

map = {
{1,1,1,1}
{1,2,2,1},
{1,2,2,1},
{1,1,1,1},
}