RTS pathfinding

Newbie & Debugging Questions
#1

I guess I’m starting to understand how RTS can afford to have so many unit moving and still having time to calculate all the path for those unit. The key seems to be in the AstarFlood algorithm, where you basically calculate the distance of each node relative to a certain one, but only when you need to use that node.

For example, if you take a Command Center in Starcraft II that has a shit load of SCV gathering mineral around it. It could possibly take a lot of time to calculate the path for all these SCV. (especially if the command center is not very close to the mineral). But, if you precalculate the distance map for the command center then all the path your SCV ask you are basically precalculate and take 0 time to return.

That was the first key. Now the second.

Starcraft map always seems to have a lot of level (cliff). Those level separate the map in a couple of different zone. Each of these zone can access other zone by ramps. Those ramps are the access point between each zone. Do you get where I want to go?

If you can split the map into smaller zone and get the access point between the different zone you can precalculate easily the movement of unit between the different zone. For example, if a unit is in Zone A and want to go to Zone C. Zone A connect to Zone B and Zone B connect to Zone C. You could precalculate the path for every place in Zone A in order to get to Zone B in the most efficient manner, and you could precalculate for every place in Zone B to get to Zone C in the most efficient manner. You could think than that look like a lot of calculation but it’s not the case. You just have to precalculate the distance map for the ramp between Zone A and Zone B and for the ramp between Zone B and Zone C. Then you have precalculate optimize path for every location in zone A to get to B and in every location in zone B to get to C.

The other benefits is that if you put a building in a certain zone, you only need to recalculate the distance maps for this zone as the other one are not affected :).

By the way, calculating a distance map take roughly the same time as calculating a long normal A* path. So it’s very cheap and done once.

N.B. : Moving object collision, moving unit of different size and realistic movement are still out of my league :(.

#2

Is there a newbie/debugging question hidden somewhere in the post? I see a “Do you get where I want to go?” (the only questionmark) so I must say that the answer to your post is “yes!” :wink:

Mike

#3

Lol sorry, just felt like sharing my thoughts :slight_smile:

#4

Yes, but if the distance to the minerals is short, the computation will not be very expensive at all, especially with the heuristics of A*. If the distance however is long, it will not have to be computed very often, as the SCV will be on its way to the minerals a majority of the time, right? Your optimizations seem a little bit overkill for a game like Starcraft 2 that “only” has a few hundred units.

What are these distance maps you talk about? Do you mean a complete precalculated path from every position to every other position? o_0

#5

Explanation of what a distance map is (I invented this term so I guess I have to explain it. If someone know the real name pls tell me).

Let’s say you have a map with 50X50 cells (so 2500 cells in total).

When you calculate the distance map for one of these cells, you create a distanceMap = double[50][50] variable then you run an A* algorithm that will simply get the distance for every cell in the map and you then store it the double[50][50] variable.

The heavy calculation is to create the double[50][50] variable.

Now, to get a path from this array, you simply get the value at your current position. Let’s say you are at position 1,1 and want to reach 10,20. Value = distanceMap[1][1]. Then you just look around your current position to see what is the lowest value. (here you can add additional calculation to determinate which move are valid too but pretty much everything is lightweight). If the lowest value was 1,2 then Value = distanceMap[1][2] and so on.

You don’t need to calculate the distance map for every cell of the map everytime. You just need to calculate the one that path are requested for and the time to calculate a distance map is the same complexity as a worst case scenario A*. (I found that worst case scenario A* could happen quite often in maze map - I probably had a bad heuristics but I don’t know anything else then Manhattan, Euclidian and similar to them). So basically, it’s a lot faster than regular A*. Especially if you reuse often the same destination (or start point).

#6

I can’t make out much from your explanation to be honest. I still think you want to store some precomputed/computed-when-needed path information in each cell that caches the path to each other cell, but why is your distance map a double[][]? What do you get from storing the distance from each node to each other node? How does it speed up your pathfinding? ???
This is going to scale ridiculously bad with map size. If you double the width and height of the map, you’ll end up with 4x the number of cells and distance maps. The distance maps will also be 4x as big.
Just look:
50x50 map -> 2500 tiles -> 2500 distance maps, each with 2500 doubles -> 50000000 bytes -> 47,7 MB, just for those distance maps.
100x100 map -> 10000 tiles -> 10000 distance maps, each with 10000 doubles -> 800000000 bytes -> 762,9 MB.
I hope you can see the problem with scalability.

Really, you’re making it really hard for yourself. For a 50x50 map, you don’t these kinds of optimizations. In an impossible (assuming cells are either passable or unpassable) worst case scenario you’d have to visit all those 2500 nodes for each unit. If you’re scale is similar to Starcraft 2, that would be about 100 units. The only paths that repetively occur are the SCV paths to crystals and geysers and back again, right? Just have each SCV cache the path to and from it’s resource. The only other scenario I can see benefiting from cached paths would be moving a large group of units. You could optimize this by having units standing close to each other share the same path to the goal. There’s no need to calculate a close group’s path to the same goal independently, as their paths will be very similar if not identical to each other’s paths. I also think the player appreciates all the selected units taking the same path and not having a lone Marine run along a different path, possibly through the enemy base. xD

#7

I guess that you didn’t read the part where you only need to calculate the distance map for the cell that you want to reach. Also, you can use distance map from the starting point too so you will never calculate the distance map for all the cell in the map. Also, all the cells having obstacle in them will never need to be calculate.

You should try the algorithm yourself before commenting about speed. You will realize that it’s a lot faster to calculate the path with precalculate distance. When I say faster, it means faster by a factor of 100 nearly. Instead of calculating path in milliseconds you will be calculating them in microseconds

#8

I never said anything about the speed of it, only that its memory usage scales badly. If you don’t have maps larger than 50x50, then go with your idea.

I’d love to implement it or try it out myself, but as it is you who came up with this idea, it’s kind of hard for me to do it. I do not understand exactly what these distance maps are. You say they are a double[][], but I do not understand how this helps with calculating the path around cliffs and buildings (like in Starcraft 2).
distance = sqrt((unit.x - target.x)^2 + (unit.y - target.y)^2);
How would this help in pathfinding? I’m trying to understand here…

[quote]Instead of calculating path in milliseconds you will be calculating them in microseconds
[/quote]
If your A* implementation takes more than 1 ms for any path on a 50x50 map (especially with most paths being short like an SCVs mining path) then you have a serious problem with your implementation.

All I’m doing is trying to understand your algorithm. It might be awesome. It might be not so awesome. I don’t know yet. I’m just interpreting what I’m reading. No need to accuse me of not knowing everything you know when you aren’t telling me. :clue: Just try to explain what these distance maps are again, please.

#9

You can get more information in this thread of the concept of distance map

http://www.java-gaming.org/index.php/topic,24596.0.html

When I said pathfinding taking milliseconds I was not referring to the case where the grid is 50X50. Usually, worst case scenario for a 200X200 map (40 000 cells) takes around 40 ms with traditional A* for me. The algorithm using distance map will take 15 ms the first time (it can’t be worst and can’t be better), then in the subsequent time, the worst case scenario is : 0.04 ms. Which is an improvement by a factor of 1000.

Also, I did some test on 1000X1000 map. The calculation of a distance map is very long (takes a few seconds). But once it’s done, it takes around 0.3 ms to find a path in that 1000X1000 map. So, it scale really well with huge map as well. (BTW, if you get a worst case scenario on the 1000X1000 map using normal A*, it would take longer than calculate an entire distance map, so a couples of seconds).

The algorithm is not perfect (and memory allocation might be one big problem), but the difference in speed is so big that it’s worth it.

Also, speed is probably the most important thing that you need when you work with pathfinding. You calculate a lot of path all the time. Every new unit appearing on the screen need a path, everytime a unit hit an obstacle that was not there before you need to calculate a path. You calculate path all the time. What happens if you have a huge map so your pathfinding code takes a few milliseconds to calculate everything, then you have like 300 unit requesting a path nearly at the same time (yes it can happens). You can’t have some unit moving 2-3 seconds later. The player want to see them moving right now or he think that something is wrong. (either with the game code or his computer). So, I would gladly sacrifice a few Mb of memory to get better performance if I have that option. Anyway, now we have a shit load of memory on computer.

One thing that might seems strange is that calculating the entire distance map is faster than a worst case scenario normal A*. The reason for that is that, even if the algorithm for both are practically the same, you can make some optimization when calculate the distance map because you don’t actually need to find a path at this time. So you can skip some calculation that make the process faster.

So, in conclusion. The distance map algorithm is mostly always faster than normal A* and that stay true on small map and on big map.

N.B. : You can check the source code here http://code.google.com/p/gudrasoft/downloads/list
It includes both the ancient version of my A* (GridAstar) and the new one using distance map (GridAstarFlood).

#10

I don’t know where you’re getting these numbers from but:
50x50 = 2500 doubles * 8 bytes = 20,000 bytes = 20KB
100x100 = 10000 doubles * 8 bytes = 80,000 bytes = 80KB

Not that big of a problem :wink:

@Gudradain
I kinda understand your idea of a distance map and I quite like the idea!

#11

It turns out I even posted in that thread earlier. Jeez, my memory sucks.

Yes, for each distance map. However, in a dynamic world were units can be anywhere and move to any other cell it seems impractical as you’d need one distance map for each cell. This was what I thought Gudradain wanted to do.

Reading in the other thread, I’ve gotten to the conclusion that this would be use to optimize paths that either have the same start cell/object or the same goal cell/object. Yes, it’s absolutely perfect for tower defence games. Yes, you can optimize gathering paths in RTS games. I just don’t think it’s very practical in RTS games, as if a building is built or something, you’d have to recompute some paths (or all if an obstacle disappeared). The memory usage is kind of bad too. Sure, each crystal and geyser in SC2 could have a distance map. That would be really good idea to be honest. I can see where your distance maps really shines!

However, in an RTS the biggest pathfinding problem is according to me giving orders to many units at the same time (select them all and then a move command), as this can create a huge hitch as all these paths are calculated. Distance maps could be the solution for these kinds of problems too! Calculate a distance map to the target position and just build paths from the map for each unit. That is definitely going into the RTS I’m making, as I don’t have any gather-able resources like SC2.

Just one small question: Why are you using a double[][]? The only thing that needs to be stored in the distance map for each cell is a way to find the next cell for each path, right? In theory you’d only need 2 bits to represent 4 directions (3 bits if you also have diagonals) for each cell to represent the next cell towards the goal. With some clever packing, you should be able to reduce the memory usage by a lot from 64 bits to 2 bits per tile.

I think I’m starting to understand this. Please tell me if I’m still completely off. xd

#12

Agreed, multi-unit pathfinding is probably the hardest problem in RTS games, its a problem that still has no optimal solution (like A* is for single unit pathfinding). Almost all attempted algorithms for this problem still use various hacks to get round corner cases (even big games like Starcraft 2). Its definitly a problem that bites most people that attempt RTS games who think that standard A* with a few tweaks will suffice.

#13

I would say it hugely depends on the collision model used between the units. The pushing model used by SC2 and other games blends quite nicely with pathfinding, even if SC2 uses a very advanced one that tries to keep groups together and keep their formation intact. WC3s collision model does have it’s problems, with units changing paths all the time etc. The most common problem is units eventually moving in a line after a few corners.

#14

I’d love to see Blizzards RTS pathfinding algorithm someday, especially since its the same one that they’ve been tweaking, gradually changing and optimising throughout their games. They’ve actually tweaked it to a point that its actually now part of the gameplay and used to carry out manovers such as intentionally surrounding a unit. Too bad its their trade secret reciepe and likely to never see the light of day :slight_smile:

#15

Yeah, would really like to know it too. Their algorithm seems amazing. Although, if I remember correctly Starcraft II bother less then it’s predecessor to keep a group intact right? Like if the group can stay in formation without any computation (because there is no obstacle) it will do it, other wise it might probably move one behind the other (a line of unit). I need to reconfirm this. Didn’t play starcraft II for some time.

@theagentd : yeah you understand it right this time.

I was using double[][] because I was lazy and didn’t need to think of a way to use less memory. But your 2 bit idea might be really great. Although you will need 3 bit to work with my algorithm because I allow diagonal move (so 8 directions). If you ever hit a wall with memory and need to implement this tweak, I would be glad to help you work on that.

Btw, it seems you are making an RTS. Have you found a way to handle collision between unit?

#16

Yeh, they also take into account unit speed and ability. So the group usually moves at the speed of the slowest unit to keep the army together. The melee units tend to move to the front while artillary units stay at the back. This also has the effect of adding more strategy to the game since if you flank an army it has a much more devestating effect on them as melee units will end up fighting the artillary units first so the army flanking the other will usually come out on top.

As for collision many newer games avoid pushing this down to traditional pathfinding algorithms (like A*) and tend to use some sort of flocking behaviour as it is magnitudes faster then things like A*. Flowfields (aka Continuum Crowds) are a really nice recent algorithm that demonstrates this, a video can be seen here.

#17

http://www.teamliquid.net/forum/viewmessage.php?topic_id=132171
Not that technical, but quite interesting.

Shouldn’t be that hard, just keep a int[] and generate indices based on the position. A small bitshift later, you have the direction. 3 bits makes it a little harder, but it shouldn’t be that hard. The easiest way would be to just waste the last 2 bits in the int and store 10 cells per int.


private int getDirection(int x, int y){
    int index = y * width + x;
    int arrayIndex = index / 10;
    int shift = index % 30;
    return (distanceMap[index] << shift) & 8;
}

Something like this. Programmed it in this post though, so something might be off. The size of the array should of course be (int)Math.ceil(width * height / 10f);.

I’m going to try to treat every unit as a magnet, and just compute a force between units when they get too close to each other, which I apply to their velocity. That way units can have a “mass” depending on how large they are. The pushing behavior that the units can have is acceptable in the kind of RTS I’m making, but it might upset some people who like to be able to surround units, etc. The collision behavior can however be tweaked to allow this too, by only allowing moving units to be pushed, so if a unit is surrounded he will try to push the other units around him, who will be “immune” to pushing as they do not move.
I haven’t even begun to implement this yet, but I think it will work. At least for my game.

#18

oh nice, thx, pretty nice read.

#19

I dunno if people do this in games, but we use it in robotics.

A* is rubbish because it enumerates way too many states. We use sampling base planners that return sub-optimal solutions but majorly faster by skipping alot of states. Instead of exploring a complete square, you explore just the frame of the square.

A one shot planner of this style is rapidly exploring random trees.

However, in a map with alot of static objects its better to precompute stuff, like the track you are on. So the multi shot version of that planner is probabilistic road-map planning (PRM).

  1. Randomly generate waypoints
  2. Joint each way-point to its X number of spatially nearest neighbors using some other search (e.g. A*) (maybe try searching for 6 paths, but terminate when you find 4). Now you have generated a course roadmap of the state space.

Now when you get a query for a point to point position, you plan to the (spatially) nearest way-point on the roadmap (or try a few and go with the first one that returns a result) to the start and goal. This find a path onto and off the roadmap. Now you just do a graph search on the low complexity roadmap between the two waypoints you just planned to (e.g. Dijkstra). Concatenate the three paths together (1. start to roadmap vertex A path, 2. vertex A to vertex B roadmap path, 3. the inverted end to vertex B path) Now you have a sub optimal path between start and goal, where 95% has come out the roadmap. HOWEVER, you will find the roadmap path a little jerky when it changes between waypoints (they were randomly generated), so its normal to smooth the final path (http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html) which is relatively easy to do albiet a slightly tedious exercise.

If the map is a little dynamic, leave the PRM roadmap as it is, but double check its validity when a specific path is found. You can then just discount whatever edges are problematic temporarily and use the other edges of the map (called lazy PRM). Superfast and can deal with really complicated non-euclidean state spaces.

PS got my doctarate in robotics path planning two weeks ago :stuck_out_tongue: back to games programming now! Here is an example of a hard planning problem : https://sites.google.com/site/tomlarkworthy/

#20

Hm unless my understanding of A* is completely flawed… it’s not supposed to evaluate every square unless it can’t find a quick route? If your heuristic is right you end up with a very efficient path to the solution in most cases.

Also - no need to use A* if you can draw a direct LOS to your goal. Always try that first before invoking A*.

Cas :slight_smile: