# Multi-tile agent path-finding algorithm?

Suppose we have a uniform rectanglular grid as shown below. The a is an agent, o is obstacle and g is goal. What are the options of handling multitile agents (e.g. dragons or tanks)?

.  .  .  .  o  .  .  .
.  .  .  .  o  .  g  .
.  a  a  .  .  .  .  .    <-- too tight
.  a  a  .  o  .  .  .
.  .  .  .  o  .  .  .
.  .  .  .  .  .  .  .    <-- should go through this gate
.  .  .  .  .  .  .  .
.  .  .  .  o  .  .  .


Update: Found this article on clearance-based pathfinding from Red Alert 3. It covers not only the clearance - size, but also a capability - ability of certain units to use certain terrains.

The simplest approach I can think of is to designate one tile of the vehicle as the basis point which determines where the vehicle is, and for each potential position in a path, calculate whether the vehicle can fit in the space around that tile, and if not, reject that position as a possibility. Basically the check for whether a tile is passable or not changes to a check whether the given vehicle collides with anything while in this position or not.

For example, if you chose the top left of vehicle 'a' as the basis tile, when you evaluate a node you'd also check the one below it, the one to the right, and the one below and to the right. In this case the obstacle below the basis tile would collide and so this position would be rejected. (In fact, you'd not even get that far, as all positions 1 square to the left of the small gate would also be rejected.)

• I see, I was thinking of modifying the obstacles my making them (vehicle-width) wider and (vehicle-height) taller. – zzandy Oct 3 '11 at 11:51
• That also works. It's the same operation in reverse really. However the collision approach is a bit easier to think about if you have irregularly-shaped vehicles. – Kylotan Oct 3 '11 at 12:09
• True. Even with non-square (e.g. 2x3) vehicles at each step you get to check two rotated states. An L-shaped vehicle ... So, basicall yther is no shortcut, at each step you just have to check that the veicle is not ovelapping with obstacles? – zzandy Oct 3 '11 at 12:23
• If vehicles can rotate and that changes their shape then that could complicate things significantly, because rotation is a movement in itself and may not be possible in certain positions. But I don't see an easy short-cut, no. – Kylotan Oct 3 '11 at 13:00

I would suggest something similar to dilation used in image processing.

Use your vehicle as a kernel to dilate your obstacles. Eg. your kernel could look like this (this would be a good kernel if your vehicle has it's "origin" at top-left):

1,1
1,1  <-- kernel "origin" is at 1,1


Basically you run through each "pixel" (or tile in your case) and render the kernel to a target whenever you encounter an obstacle. The kernel should be rendered with it's origin position at the position of the obstacle.

To illustrate, here's what will happen with a single obstacle:

[ source ]  ---->  [ target ]
. . .              o o .
. o .              o o .
. . .              . . .


Then, your grid dilated with this kernel would look like this:

.  .  .  o  o  .  .  .
.  .  .  o  o  .  .  .
.  .  .  o  o  .  .  .
.  .  .  o  o  .  .  .
.  .  .  o  o  .  .  .
.  .  .  .  .  .  .  .
.  .  .  o  o  .  .  .
.  .  .  o  o  .  .  .


Which would be the grid you want to perform your vehicle path-finding on.

Update: Updated above with some more information. Also this would actually work for different shaped vehicles but will get computationally expensive with a huge map and a large kernel (the smaller the kernel, the better).

• What if the kernel is, say L-shaped? Should I run several iterations of dilation based on different rotations of the vehicle? – zzandy Oct 3 '11 at 12:30
• @zzandy The kernel can have any shape (see update) but this doesn't factor in rotations. If your vehicle should be able to rotate when going from start to goal, then this won't work. Several iterations won't work either.. just imagine a I like shape.. which will fit through the smallest gap horizontally, but not vertically. – bummzack Oct 3 '11 at 12:38
• Not rotate, while moving, just be able to rotate if it allows it to fit through. – zzandy Oct 3 '11 at 12:41
• @zzandy Then it's probably easiest to calculate a dilated grid for every unique rotation-position. Applying the dilations in several iterations on the same grid won't work (again, think of an I like shape). – bummzack Oct 3 '11 at 12:48
• Found this article on clearance-based pathfinding from Red Alert 3. Only for square vehicles though. – zzandy Oct 3 '11 at 12:59