Multi-tile agent path-finding algorithm?

Question

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.

Answer 1

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

Answer 2

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