i was playing with using A* to find a path on uneven ground (basically a height map); the cost for movement to an adjacent spot on the grid is a function of the slope of the hill (i.e. it has a higher cost to move "uphill", and a lower cost to move "downhill", and it is somewhere in between for level ground. but, it seems really really slow. is there something more appropriate for this type of problem? if so what should i google for? or must i just optimize it somehow? thanks!

Could you post a little more information please? There shouldn''t much of a slowdown if you are just adjusting the weighting. Are you doing any continual calculations because for something like that an approximation would make very little difference over something using a little trigonometry. Are you precalculating your slope values becuase if you are not you may want to do that as it sounds like you are using static stuff here.

1. precalculate the costs
2. what kind of priority queue are you using? There could be other, faster ways to do it, though maybe not as accurate
3. overestimate heuristics. It won''t give optimal paths anymore then but for a game it could suffice. Play around a bit to see what kind of error is acceptable.

I think an idea might be to modify the cost of each node as you deal with them with something like:

node_cost = terrain_cost + ( terrain_height - previous_terrain_height)

terrain_cost is the weight of the node ie mud, grass, concrete.
terrain_height is the elevation of the terrain the node relates to.
previous_terrain_height is the elevtation of the terrain the node that linked us to this one relates to.
You should have instant access to all the information in this calculation if you are using a heightmap (I think).

That may or may not be what you are already doing. It obviously involves an extra addition and subtraction per node and probably other calculations that I have not considered (such as re-setting the parent of a node when the situation calls).

Note that I am not an A* expert in any way so what I have just suggested may not be the best aproach. It is merely what I might try.

quote:

---

Original post by krez
i was playing with using A* to find a path on uneven ground (basically a height map); the cost for movement to an adjacent spot on the grid is a function of the slope of the hill (i.e. it has a higher cost to move "uphill", and a lower cost to move "downhill", and it is somewhere in between for level ground.

but, it seems really really slow.

---

Given your description of costs, it is entirely possible that your cost function is non-monotonic, which violates one of the assumptions required for A* to be optimally efficient. It really depends on your heuristic estimate and whether it takes into account the change in height required between the current node and the goal. For instance, consider a node on top of a hill. The cost of this node is taken as the cost to get to the top of the hill, g(hill), plus the estimated cost to get to the goal, h(hill): f(hill) = g(hill) + h(hill). Now consider a child node at the bottom of the hill toward the goal. It's cost is the cost to get to the top of the hill from the start plus the cost to get down to the bottom of the hill plus the estimate to get from the bottom of the hill to the goal: f(valley) = g(hill) + g(valley-hill) + h(valley). You have to ensure that g(valley-hill)+h(valley) >= h(hill). This requires that your heuristic take into account the change in height between hill and goal and valley and goal. A direct use of straight line distance (SLD) in 2D would have g(valley-hill) < h(hill)-h(valley), because the down hill bit costs less than going straight at the same level (which SLD assumes), causing your cost function to be non-monotonic. Make sense?

There are various ways to deal with this. You could simply enforce monotonicity by checking that f(valley) >= f(hill) and forcing it to be at least equal if f(valley) < f(hill). Another method is to alter your heuristic function and add a parameter, e, which varies between 0 and 1, such that f(node) = g(node) + e*h(node). e < 1 can be chosen to enforce the admissibility of h, but obviously the closer to zero, the more your search behaves like a depth first search, which will be slower than pure A*.

Good luck,

Timkin

[edited by - Timkin on March 3, 2004 2:01:57 AM]

The D* algorithm might be what you are looking for, from what I know it''s a modified version of the A* pathfinding algorithm, and is much more suited for terrain, as well as even dynamic landscapes.

I could be wrong, but it''s worth a shot to check it out, I think one of the Game Programming Gems books even covers it as well.

~Graham

----
while (your_engine >= my_engine)
my_engine++;

quote:

---

Original post by gwihlidal
The D* algorithm might be what you are looking for, from what I know it''s a modified version of the A* pathfinding algorithm, and is much more suited for terrain, as well as even dynamic landscapes.

---

No, the D* algorithm is applicable in domains where you don''t know the costs of certain actions ahead of time, due to uncertainty in the domain. For example, you might know the door is closed, but you don''t know if it is locked or not. Hence, you wont know the cost of moving through the door until you find out whether it is locked or not. D* is an efficient algorithm for updating costs in your search tree based on new information, such as that described above. It''s efficient because it restricts the propogation of new costs to only the proportion of the search tree that lies as a subtree under the current state.

quote:

---

Original post by gwihlidal
I could be wrong, but it''s worth a shot to check it out, I think one of the Game Programming Gems books even covers it as well.

---

I have that book and I don''t recall it discussing D*... but I could be wrong. Indeed though, I don''t recall any book that I have read on Game AI (and thats quite a few) discussing D*.

Timkin

I''ve implemented something similar to this. I suspect what is happening from your description of how you calcuate cost, A* is favoring downhill paths, this will cause it to always search down to the lowest walkable height.

It does this irrepsective of the desintination height, due to the cost calucation. So say you have 2 points on the same hill, it will search down the hill first, then start a exhaustive search from this vally upwards, until it reaches the destination. This will cause A* to act like a flood fill, filling the vally uniformly.

Instead of favoring downhill, I use a cost estimaition based upon absoulute change of height between nodes. That way A* tries to stay on the same hieight, however it will change heights when it has too. You have to do some trial and error to find the right balance of cost and heurstic using scaling factors, so A* find efficent paths. It''s very much an art, as the range of your height fields, the distance travelled etc. have to be considered and carefully weighted.

Good Luck!

-ddn

quote:

---

Original post by ddn3
Instead of favoring downhill, I use a cost estimaition based upon absoulute change of height between nodes. That way A* tries to stay on the same hieight, however it will change heights when it has too.

---

That's a different problem though to the one being discussed here. Your cost function penalises a change in height whereas krez's cost function penalises climbing hills and discounts going down hills.

A* shouldn't act like a floodfill filling valleys before it fills hills... at least, not in the state space. A* expands all nodes within a given cost contour before expanding any node in a higher cost contour. This is how it guarantees to find the lowest cost path, if it exists. Certainly, A* will fill as much as the valley as it can with costs less than or equivalent to a hill climb earlier in the search tree... but it shouldn't fill it all, unless the cost of climbing a hill, or going straight, is greater than the worst path cost through the valley.

ddn3, I would suspect that if you saw this sort of behaviour when you set the problem up with costs proportional to directional change in height, that you had a problem with either your heuristic or a bug in your code.

krez, my best suggestion for you is to perform a search on a small, restricted subset of your domain that you can easily verify the optimal path by hand (say a 10x10 surface). Check that the algorithm is executing properly and that the costs being computed are what they should be. Dump a log of all the iterations and watch what is happening in the search. This is the best way to find out if the search is bugged, or your cost function has problems with it.

Good luck,

Timkin

[edited by - Timkin on March 4, 2004 10:33:38 PM]

Possibly Timkin, however given that description of krez cost function I suspect it''s exhibiting behavior similar to my A*. Also the original cost function I used was the same as krez. They both exhibit vally filling though, but the one which favored downhill paths much more so.

When I was doing the pathing across uneven terrain, the paths would naturally move downhill I noticed, this is given since my terrain isn''t overly hilly, so the chances of encountering terrain lower or at the same level is higher. Once it enter a vally it then have to climb out of it, if the desintaiton was on a hill. Depending upon the cost of climbing vs the heuristic estimation, A* will search many nodes around the hill when it tries to climb it. Reducing the cost would produce unatural paths which ignored the natural terrain curvature and details. So it''s a fine balance, between the cost of climbing vs the huerstic estimate.

Good Luck!

-ddn