# How can I move a hero along the floor mesh?

## Recommended Posts

Posted (edited)

I am sure this question has showed up from time to time, but I can not find any information about this.

I am creating a Game/Rendering Engine and do not want to use Physics in my 3D Game(not yet anyway), and I want to learn and implement moving a character along a quad floor mesh.  I understand this involves a Bounding Volume and Hit Detection, but I am unsure how to test different locations of the quad mesh and how to smoothly move over rugged terrain because the floor mesh is not always smooth, it could be jagged with sharp angles(stairs).

I have come up with alternatives that use a TileMap approach and stores the height(average) for each section of the quad floor mesh, but I would rather use this simple mesh in real time for better accuracy.  Maybe this requires a Ray Cast to know the X,Y,Z of the triangle face in world space, but I am a big confused how I would use this to test collision?

Id like to know alternatives, especially ones used for Servers(for speed).

Edited by IndieGuyy

##### Share on other sites

It sounds like you are looking to use a 'NavMesh' or navigation mesh (also used to be called walkabout polys).

There's an extensive literature on this, if you google the term. For rugged terrain and stairs often the navmesh is simpler than the visible geometry.

Greg Snook wrote a good introductory article to these in Game Programming Gems (2000) if you can find it, also there will be lots more tutorials on the web.. e.g.

##### Share on other sites
Posted (edited)

Thank you!  I did not know what it was called.  I can finally start reading about it.  🙂

Actually, Im not really seeing the Math behind how to move a character along the surface ....

I want the pure math on how to make my Bounding Volume intersect the mesh as tight as possible while moving in a direction.

Edited by IndieGuyy

##### Share on other sites
Posted (edited)

A navmesh is used for AI controlled entities.

Raycast on the barycentric coordinates of a given triangle to find the correct height at the location your standing on.

ED: You might not need raycast, linear interpolation may be all you need.

Edited by fleabay

##### Share on other sites

Okay!  And for moving a character along a surface, I would basically just find this P point and then from there generate some triangle based on this to test the BV correctly and move my Hero/Mesh accordingly per frame... in a nutshell.

Is there some technical term for this process so I can read about the various ways this can be done?

##### Share on other sites
1 hour ago, fleabay said:

A navmesh is used for AI controlled entities.

Usually, but can also be used for players, depending on the game type.

1 hour ago, IndieGuyy said:

Okay!  And for moving a character along a surface, I would basically just find this P point and then from there generate some triangle based on this to test the BV correctly and move my Hero/Mesh accordingly per frame... in a nutshell.

I would ideally point you to a decent link, but google seems full of searches about unity and unreal, rather than doing it yourself.

There are a number of variations, but the general idea is that usually instead of testing a bounding volume, you pull in the edges of the navmesh from the walls by the radius of the player, and model the player as a single point. So if a player has 50cm radius, the navmesh polys stop 50cm from the wall, and when you reach the edge of the poly, you know you are at a wall (and can slide).

In a lot of cases you don't need to do anything very complex to find out which poly a player is in. You simply keep track of the poly it was in last time, then test against each edge. If it has crossed an edge, it goes into the linked navpoly, or else slides if there is no link.

You can test for crossing the edge with cheap 2d tests, like suggestions here:

##### Share on other sites

Okay!  Great, but how do I make my hero stick to the floor mesh?  Is it the same concept?

##### Share on other sites
6 minutes ago, IndieGuyy said:

Okay!  Great, but how do I make my hero stick to the floor mesh?  Is it the same concept?

You can use e.g. barycentric interpolation of the vertex heights, as suggested earlier. (You may also be able to use barycentric methods to determine whether the player is within a navtriangle, which may work as an alternative to edge tests.)

##### Share on other sites
Posted (edited)

Using barycentric interpolation is great, but I think it is a bit slow if I had to do this test for each movable unit in the area, right?  So what are alternatives that use precalculated data?

Edited by IndieGuyy

##### Share on other sites

Is it actually too slow (based on profiling data), or do you just think it will be too slow? What leads you to believe that a precalculated solution (likely adding another memory access in lieu of a calculation) would be faster?

You would likely be better off implementing the interpolation, then optimizing if profiling indicates it is too slow.

## Create an account

Register a new account

1. 1
2. 2
frob
20
3. 3
Rutin
17
4. 4
5. 5

• 13
• 10
• 9
• 18
• 9
• ### Forum Statistics

• Total Topics
632555
• Total Posts
3007035

×