Sign in to follow this  

Calculate if the path is blocked or not using a normal.

This topic is 3318 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been working on a my path finding algorithm for some time now and I've got that working. (it chooses the path which is cheapest). But now i want to add the factor of road blockage to the equation. Me and my friend are using a height map which calculates the normal of each Cell within the grid. It takes the 4 corners to determine the normal of the surface. I didn't write this code myself but i know how to use it. Now my question is how do i go from here: i receive the normal for this cell. it's stuffed in a D3DXVECTOR3. i figured i should look at the y value of this normal. figuring that 0,1,0 would mean the surface would be completely flat. but what do i do when the surface isn't flat. I've currently tried "normal.y < 0.7" would mean it would be blocked. well that's obviously not the way to go. But i lack the knowledge of the needed math here. Any pointers? P.S. this should have been in the Math forum >.< sorry

Share this post


Link to post
Share on other sites
Perhaps a little more explaining why i want to use the normal.
Me and my friend used the difference in height between 2 cells earlier.

But that results in the characters walking along a wall sideways and up.
which is kind of strange since if something is to steep you won't be able to walk along the side and upwards.
In fact it's easier to do that in Reality but reality is not what we're going for.

Next to the fact they shouldn't walk up walls sideways. it just looks strange.

Share this post


Link to post
Share on other sites
Quote:
Original post by Darsin
I've currently tried "normal.y < 0.7" would mean it would be blocked.
well that's obviously not the way to go.

Why not? Some games simply define terrain at more than 45° slope cannot be accessed. However, I'm not totally sure what you want to reach. Do you want to investigate the slope of the terrain in direction of movement? E.g. the character cannot walk up a steep slope, but can slide it down? Such a thing would also suffer from walking up walls if the movement direction is chosen just orthogonal enough w.r.t. the highest slope.

Perhaps you have 1st to determine whether or not the character is able to walk anyhow, e.g. by comparing the y component of the normal. If it is less than a threshold, let the character slide down and switch off user's walk control. Then, if the terrain is accessible at all, compute the slope in direction of (desired) movement, and decide whether or not the character can walk that way, and perhaps how fast it were possible.

You can use the x and z component of the normal to determine the slope direction and steepness. E.g. build a 2D vector from the x and z components. That new vector points in the direction where the terrain is most sloping. E.g. if the character is sliding, the vector points in direction of sliding. An even terrain will have a zero vector. For all other cases you can normalize the vector to get the pure direction. You can furthur use the length of the vector (besides the value of the normal's y component) to compute/restrict the speed of movement.

Hope that helps.


Quote:
Original post by Rasmadrak
Use the dot product between the "up"-vector and the normal, if this is within a particular threshold the tile is walkable.

The dot-product of the up vector and the normal results in ... the y component of the normal.
Proove: [ x y z ] . [ 0 1 0 ] = x*0 + y*1 + z*0 = y
So that solution is identical to what the OP already does.

Share this post


Link to post
Share on other sites
For now i just need to know if the surface is sloped more than a certain amount so let's say 45 degrees.

how do i go from the normal to an angle?
if the normal is at more than 45 degrees that cell should not be accessed ever.

Share this post


Link to post
Share on other sites
Quote:
Original post by Darsin
how do i go from the normal to an angle?
...

The dot-product has a correspondence
a . b == |a| * |b| * cos( <a,b> )
in which the cosine of the angle between the 2 vectors is used.

In your case, a is the normal [ x y z ] of the terrain and b is the up vector [ 0 1 0 ]. As already shown, computing the dot-product as usual gives
[ x y z ] . [ 0 1 0 ] = x*0 + y*1 + z*0 = y
and with the typical set-up that the normal is of unit length (the chosen up vector is of unit length, too)
|a| = |b| = 1
you can simplify the equation to be
y = cos( <a,b> )

Quote:
Original post by Darsin
...
if the normal is at more than 45 degrees that cell should not be accessed ever.

Using the above equation, the border angle would yield in
y' := cos( 45° ) = 0.707...
so that the condition is
if y<0.707 then not accessible
if y>=0.707 then accessible

Hence I wondered why the OP has denied that condition to work.

Share this post


Link to post
Share on other sites

This topic is 3318 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this