# Pathfinding for units of variable size

I'm using a grid map for a top-down RTS, and I am using the a* algorithm for pathfinding. Specifically, I've found one implementation which is heavily optimized, and I've been using it for a while, but now I've realized I only checked it with infantry and not with vehicles, which take more map space, and so I can't rely on the algorithm - what would be "hugging a cliff" for infantry would be passing through it for a vehicle.

So, I'm trying to decide what to do. I see three options. a. The obvious thing is write my own A* implementation, but this is both very time consuming and I presume I won't reach near the optimized speed of the algorithm I found. (rewriting the algorithm is out of the question - I just don't have the time to try to read it and understand it).

b. corrections - read the path generated by the algorithm, and either correct it at every step or when receiving the path recalculate it for width.

c. Hold variable sized maps, that are different representations of the free space on the map, on account of size.

Option C sounds to me the simplest, but is likely to be too memory heavy, even if there're only three-four size categories. Between options a & b, I'm not sure what is likely to take more calculation time - a non-optimised A*, or running over & correcting a path.

A* is not a hard algo to understand and it is one you should get intimately familiar with if you plan on using it in games.

What you really need from your description is an annotated pathfinder. (clearance based) There is a great description of one here.

Clearance Based Path Finding

This article describes a hierarchical annotated a* path finder however once you can write your own A* from scratch adding features you need for each project is very simple.

Heavy use of a profiler will help you optimize your path finding in short order. It really is a simple piece of code once you get the hang of it.

Edit: I am sorry I forgot to add. If you already have a fast a* the modification to add the clearance based checks is pretty simple. Obviously your base object that anything that is going to use the path finder is derived from needs a "clearance" variable of some kind.

Inside the actually path finder just find the spot where it is checking against if things are walkable or not and that is where you add in the clearance checks. Also when you first generate your map you need to add a var to the node or however your graphing your map to pre-calculate the clearance values.(that will make it faster) Really that is basically all there is to it.

• The webpage doesn't exist anymore Nov 29, 2023 at 12:03

Without stepping in and altering the algorithm itself, you could just stick with option B.

Calculating corrections won't be optimized anyway, and most probably you'll have to define ad hoc routines for each type/size of unit you're going to use.

Another thing to take into account is a possible collision detection implementation: The very idea of 'hugging' a wall with a vehicle can be (sort of) easily solved that way, even more if you won't care for vertical movement collisions since you'll be just working with a 2D world at that point. Even more easy and fast if you also don't care for a high level of precision with collisions (i.e: every unit is a circle with a defined radius).

Edit:

If you need a generic explanation on collision detection just search for any tutorial (or this website), there's plenty online.

If you mean in this specific case instead, once you obtain the path from your algorithm, just make the unit follow the path, and have the collision detection do its job once the unit actually tries to pass through any surface that you defined as a surface to check.

I.E: If you define your tank unit as a circle (A is the center, R is the radius) for the collision detection, once it's following a path that would be correct for infantry, the collision detection will prevent the tank from passing through (partially or completely) the wall by checking if the point A is closer than distance R to the wall. The way you handle the result of the collision depends entirely on what you want to do. The easiest way is to make the component of the movement that is perpendicular to the wall null, so it will 'slide' along, basically 'hugging' the wall.

I suggested this approach mainly because working with 2D bound shape is easy and fast.

• Could you expand on collision detection? I'm not sure I get your drift. Apr 28, 2012 at 20:02
• Just edited my previous answer to make it more clear. In a way it's an extended option B, adding a simple algorithm to your existing one. Apr 28, 2012 at 20:31

I don't understand how you can be resistant to ditching your "heavily optimized" code in favor of finding multiple paths each time or the increased complexity of holding multiple maps (both clearly the other direction from optimized). I doubt your current code is so optimized that you would be better off going with those options instead of writing your own implementation.

I suggest you go with option A (in an option B sort of way). I think your presumption is correct that you won't reach the same optimization, however you're ruining that optimization anyway with options B (multiple paths) and C (considerably more work than re-writing your path-finding). I do believe you could reach a better optimization with option A than B or C.

Combine options A and B. Rewrite your algorithm to include checks for size when picking a new node. You'll maintain most of your optimizations, learn something along the way and get the end result you desire.