(1)
--------------------
|
|
| (2)
|
|
---------------------------
(3)
A* and cliffs
August 20, 2009 07:42 PM
Hey folks, have an interesting problem I'm trying to get around at the moment with my A* pathfinding...
My nav-mesh for various levels contains (simplified) geometry that looks something like this
where 1, 2 & 3 are nodes in the nav mesh. I'm trying to figure out a way of determinining the G score so that 3->2 will be untraversable, but 1->2 will be.
Obviously comparing the dot product of the normals between 3 & 2 against some constant will block the traversal in the desired manner, but the same thing is going to happen when trying to get from 1->2.
Any ideas?
Cheers!
120
August 20, 2009 08:39 PM
Disclaimer: I'm a novice at this stuff.
Maybe you can add some mega-huge value to your heuristic score if the height difference to the next mesh polygon is greater than "x" [assuming that a path that goes upwards is positive]. Then if your best path is some mega-huge number, you can assume the best path is untraversable.
Maybe you can add some mega-huge value to your heuristic score if the height difference to the next mesh polygon is greater than "x" [assuming that a path that goes upwards is positive]. Then if your best path is some mega-huge number, you can assume the best path is untraversable.
August 20, 2009 09:04 PM
Quote: Original post by HostileExpanse
Disclaimer: I'm a novice at this stuff.
Maybe you can add some mega-huge value to your heuristic score if the height difference to the next mesh polygon is greater than "x" [assuming that a path that goes upwards is positive]. Then if your best path is some mega-huge number, you can assume the best path is untraversable.
I've been doing just that, but yesterday I found a couple of places where the method falls flat on it's face...
If a long slope leads up to a cliff the center (used for height comparisons) of the slope can be lower than the center of the cliff, in which case my check fails. I guess I could compare the connecting edge of the slope with the trailing edge of the cliff face... that might be a whole lot better :)
120
August 20, 2009 09:07 PM
Quote: Original post by CapoeiristaQuote: Original post by HostileExpanse
Disclaimer: I'm a novice at this stuff.
Maybe you can add some mega-huge value to your heuristic score if the height difference to the next mesh polygon is greater than "x" [assuming that a path that goes upwards is positive]. Then if your best path is some mega-huge number, you can assume the best path is untraversable.
I've been doing just that, but yesterday I found a couple of places where the method falls flat on it's face...
If a long slope leads up to a cliff the center (used for height comparisons) of the slope can be lower than the center of the cliff, in which case my check fails. I guess I could compare the connecting edge of the slope with the trailing edge of the cliff face... that might be a whole lot better :)
Yeah... I was going to note that my suggestion would probably fail if there are large uphill/downhill meshes. One inefficient workaround would be to break up sloping meshes into small pieces.
Or... instead of calculating height differences, you can just have a 2-D list of some sort, where you manually add in paths that you want to make untraversable. Your heuristic function could check to see if AddedCost[currentNode][nextNode] is present in your list, and, if so, it can add in the mega-huge number as suggested earlier.
1,420
August 20, 2009 09:14 PM
well when you calculate the g value right now, do you score it based on the cost for transitioning to the next node as well as the penalty of the next node? The penalty for both moves is that the node is perpendicular, but the decision from 1 to 2 should say "it's below me" vs. 3 to 2's "it's above me", which should pass for 1 to 2 and fail for 3 to 2.
120
August 20, 2009 09:20 PM
Quote: Original post by Funkymunky
... but the decision from 1 to 2 should say "it's below me" vs. 3 to 2's "it's above me", which should pass for 1 to 2 and fail for 3 to 2.
Yeah... I think he's saying his current use of that method fails 3=>2, but also fails a desired path like 4=>1 below:
(1) -------- / | / | /(4) | (2) / | / | (3)/ -----------------As for the mesh being perpendicular .... perhaps he can make use of that data. I might try modifying my earlier suggestion so that I check the slope of the next mesh in the path. If it is less than "y" I could skip adding the "mega-huge" cost value. This way the addition is only done when the algorithm is considering travel over a mesh that is nearly perpendicular.
August 20, 2009 09:32 PM
Quote: Original post by Funkymunky
well when you calculate the g value right now, do you score it based on the cost for transitioning to the next node as well as the penalty of the next node? The penalty for both moves is that the node is perpendicular, but the decision from 1 to 2 should say "it's below me" vs. 3 to 2's "it's above me", which should pass for 1 to 2 and fail for 3 to 2.
At the moment there are penalty checks, but they're buggy and don't work for every case in my nav-mesh. Just trying to figure out a clean way of working out whether a drop or a cliff face is involved, as simply working out the angle between the sector normals doesn't give enough information.
I think comparing the average height of the connecting edge of the current sector with the height of the trailing edge of the next sector in the mesh should do the trick... up until recently I've been comparing the heights of the sector centers, which fails when a slope's center is lower than the center of a cliff face.
August 20, 2009 09:44 PM
Quote: Original post by HostileExpanseQuote: Original post by Funkymunky
... but the decision from 1 to 2 should say "it's below me" vs. 3 to 2's "it's above me", which should pass for 1 to 2 and fail for 3 to 2.
Yeah... I think he's saying his current use of that method fails 3=>2, but also fails a desired path like 4=>1 below:
*** Source Snippet Removed ***
As for the mesh being perpendicular .... perhaps he can make use of that data. I might try modifying my earlier suggestion so that I check the slope of the next mesh in the path. If it is less than "y" I could skip adding the "mega-huge" cost value. This way the addition is only done when the algorithm is considering travel over a mesh that is nearly perpendicular.
Yeah that's exactly it - although I think I can get around the problem by checking the angle between the sector normals first. If it's above a certain value then I can assume I've met a cliff, otherwise I can perform regular checks to see if the next sector is traversable.
982
August 22, 2009 11:53 AM
How about this:
You're on sector A, you know that sector B is a "vertical wall," and you want to know whether you can move from sector A to sector B. Let na and nb be the unit normals for these sectors. Compute v=nb-na. The vector v will point down if the move is acceptable and up if it is not. So just check the sign of the vertical component of v.
You're on sector A, you know that sector B is a "vertical wall," and you want to know whether you can move from sector A to sector B. Let na and nb be the unit normals for these sectors. Compute v=nb-na. The vector v will point down if the move is acceptable and up if it is not. So just check the sign of the vertical component of v.
113
August 22, 2009 07:52 PM
Calculate the normal to the face (using a cross product).
Normalize the normal vector and examine the vertical elevation (call it phi).
normal = x*i + y*j + z*k;
Where i,j,k are direction vectors.
Thus phi = ArcTan[1-Abs[z]];
Now that you have the elevation angle you can decide if you want units to be able to come up it. So set some angle threshold and your done.
Note that phi will range from 0 to PI radians.
This mean that you should probs set 60 or 70 degrees as the threshold.
Cheers.
Normalize the normal vector and examine the vertical elevation (call it phi).
normal = x*i + y*j + z*k;
Where i,j,k are direction vectors.
Thus phi = ArcTan[1-Abs[z]];
Now that you have the elevation angle you can decide if you want units to be able to come up it. So set some angle threshold and your done.
Note that phi will range from 0 to PI radians.
This mean that you should probs set 60 or 70 degrees as the threshold.
Cheers.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
