Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm using a grid map for a top-down RTS, and using a* for pathfinding. Specifically, I've found one implementation which is heavily optimised, and I've been using it for a while, but now I've realised 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 optimised 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 simpolest, 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.

share|improve this question
add comment

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Could you expand on collision detection? I'm not sure I get your drift. –  nihohit Apr 28 '12 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. –  Darkwings Apr 28 '12 at 20:31
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.