Saturday, February 24, 2018

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.



Answer



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


No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...