Hi, i have some question how to structure my pathingmaps.
I want to create a RTS game like Warcraft 3/Starcraft 2. For the pathfinding I want to use a modified A*Star and steering behaviours.
There are 4 different pathingmaps for ground-,air-,water-units and for buildings and all these pathingmaps should be grids.


Each of this submaps should contain one Grid for the detailed pathing information and one quad tree which contains the Obstacles for the steering behaviors.

Here is one example how the grid could look like:


The negative values represent fields which are blocked (red) and arround these blocked fields there is an information how large the units can be which can pass these fields. (for the A*Star)
Besides I could use different negative numbers for different layers. (Example:A building blocks a path, than a trigger says that the area where the building stand is blocked for units and after this the building is killed.)
I am not sure if a QuadTree would be useful in this case because there a many different values.

Here is an image how the obstacles could look like:


I think the obstacle tree is okay but the other map has some problems.

For example every time a pathing blocker is deleted I would need to check all field arround and recalculate the value by searching the nearby blocked fields. This would mean that about 25*25 fields must be checked -> high costs...
The only way to fix this would be to support only 3 unit sizes and than i would only need to check about 9*9 fields. Or the A*Star needs to check for the size every time but I cant imagine that this could be better.
But maybe this could be a tip that i generaly made some mistakes in my structure.

So I am intrested in the opinion of some experts.Is everything alright?
(Atm I would implement the simlple version but maybe there exists a solution with a good performance and many different unit sizes?)

I was a little bit surprised that you chose the values that you did. In the A* implementations that I've seen the numbers were a cost, e.g. clear ground = 1, hilly ground = 3, impassible object = infinity (or similar). If you did it that way, things like a destructible building may be cost 50, e.g. it takes 47 turns worth of shooting to destroy the building then 3 to cross the area it took up. As for quadtrees... I don't really see how they apply to A* because A* may potentially explore every grid cell worst-case and has to look at the cost for every cell, although you could look into a hierarchical A* if you have very large maps. Are you thinking of using steering behaviours for path smoothing, or for flying units where obstacles aren't really a problem?

I was a little bit surprised that you chose the values that you did.[/quote]
I found this thread here:
http://www.gamedev.net/topic/511923-pathfindinga-with-variable-unit-size-in-rts/
and I think your maps is maybe useful for other strategy games but in my case I dont have hilly grounds nore I want to save the HP of a building in the map.

Are you thinking of using steering behaviours for path smoothing, or for flying units where obstacles aren't really a problem?[/quote]
I think in a rts game an A* is used to find the way arround buildings and trees and the steering behaviours to smooth the path and avoid other units.

I agree that you should probably stack your values the OTHER direction... that is, thinking in terms of cost. That's the way I've seen it the most. If the quickest you can travel is 1.0 and a type of terrain takes twice as long to traverse, it is a 2.0. The reason for this is that, at some point, you have to add up your path lengths and compare them. If you simply use the relative time to traverse, it takes all of that into account without any sort of adjustment. That is, you have already converted the uniform lengths of your grid into time... which is what you are using to compare anyway.

I found this thread here:
http://www.gamedev.n...it-size-in-rts/
and I think your maps is maybe useful for other strategy games but in my case I dont have hilly grounds nore I want to save the HP of a building in the map.

Right, it's a perfectly valid way to determine the minimum approach distance for different size units to the terrain. However I would then process that further to turn it into a cost map for A*. A* is designed to find the minimum cost path between A and B where all costs are positive and represent the difficulty of traversing that area.

Looking at your example I think perhaps I'm barking up the wrong tree - your 1-4 aren't meant to represent costs at all, they're just a way of determining how big the impassible area should be for later A* pathfinding. So if you were pathfinding for a unit of size 3, you would turn cells marked 1 and 2 into red cells, correct?

I'm still not seeing the point of the quadmaps unless perhaps it's for a steering behaviour?

your 1-4 aren't meant to represent costs at all, they're just a way of determining how big the impassible area should be for later A* pathfinding. So if you were pathfinding for a unit of size 3, you would turn cells marked 1 and 2 into red cells, correct?[/quote]
Yep. The only costs of terrain I could imagin are hills but for this I would use the heightmap of the terrain.

I'm still not seeing the point of the quadmaps unless perhaps it's for a steering behaviour?[/quote]
Youre right that is not useful for the grid but the quadtree for Obstacles is a better way than creating one obstacle for every blocked cell.

Ugh... I got distracted by something farther down the thread and thought you were talking about terrain weights too.

I believe that I have seen people just have separate pathing maps for objects of different sizes. Can't remember where I saw it recently though.

I found some nice articles and it will take me some time to read and think about them:
http://aigamedev.com/open/tutorial/clearance-based-pathfinding/
http://aigamedev.com/open/tutorial/symmetry-in-pathfinding/
http://www.moddb.com/games/0-ad/news/the-pathfinding-saga-continues

Okay, I will use the map like in the clearance example:

Every field gets the value by checking how large we could expand the rectangle.
This is useful because it is easy to change blocking fields and to recalculate the size for the units.
I can simply start at the bottom right position I want to change and than always determine the new value by looking at the right/bottom/diagonal neighbour of this field. (if it exists)
Therefore I have a larger if construct but I dont need to visit some field "twice". I already tested it and it works fine. (+ should be fast)