I'm curious as to what sort of techniques exist for handling player movement in a 3D environment without the use of a physics engine.

One approach I've tried in the past was using sphere casting (performing multiple iterations to handle sliding), but it had a number of quirks that I couldn't easily resolve.

Another thought I had was to just move the player along a navmesh, as described in http://digestingduck.blogspot.com/2010/07/constrained-movement-along-navmesh-pt-3.html. The main thing I'm still unsure about is how to handle dynamic obstacles (ex. enemies). And most of the navmesh resouces I've found so far pertain to the implementations in Unity, Unreal, or Source, rather than how to actually implement it.

Any thoughts on the above or alternative techniques? Or good resources on implementing them?

Also, are there any commercial games using similar approaches? From the small amount that I've played it, I think Kingdoms of Amalur: Reckoning might be using an approach similar to the second one I described, but I'm not sure.

Are you referring to perhaps games like diablo, where the movement of the player is abstracted? In a diablo style game, technically you don't need a physics engine, the player character just moves to wherever a valid click is, so essentially the pathfinding is doing all the work to guarantee there are no collisions. (it still has to check for collisions, but there would be no collision response)

Very often there are multiple sets of data. The physics ground is one object, the rendered terrain is a second object, and the navigation mesh is another.

A navigation mesh can be very simple, even a 2D grid that maps onto the terrain. It can also be complex, a full triangulated mesh or even a volumetric representation.

Games will often have multiple parallel representations internally, a fact often surprising to new developers.

I've worked on several games that people think of as bigger 3D worlds but in reality were just 2D grids internally; height is just stacked grids starting at ground level. Players move from cell to cell to cell, animating smoothly along the way. A tiny bit of animation magic and the walked paths can bend and twist organically over the 2D grid yet still move from cell to cell.

Motion is only allowed between areas of a navigation mesh if the two sides are connected. Disconnected edges, like the ramp in your image, are not navigable. They act as a wall or barrier.

What you drew in your image is a great example of a navigation mesh. It isn't a physics mesh since you don't want things to fall off it. It isn't a render model since your stair will will likely have a rail or other barrier. Many times they will have additional information tied to the nav mesh to indicate things like sounds and speed and other attributes (e.g. walking on wood, walking on carpet, splashing over puddles, squishing through mud, etc.)

For your other questions... Yes, they are extremely common. To make them fast people usually break them up with spatial trees, and most of the big articles about loose quadtrees and such are intended for use in navigation meshes with things (like enemies) moving around. There are lots of articles about the subject, you just need to realize what you are looking at. For alternate implementations, you can rely entirely on physics for some games (Super Monkey Ball comes to mind) and you can rely on strict grids for things like board games, but nav meshes with spatial trees over the navigation mesh is really the standard method.

Jeff

1. This method seems like you're basically doing your own form of collision response.

2. This method seems like the diablo method I mentioned before. I've implemented variations of it. It was pretty trivially easy to for example, get a the ray from a click on the screen, find where it hits the navmesh and then have the player-actor try to navigate to that point on the navmesh. You are correct that jumping doesn't work with that method, one would either need to have jump as connector node type thing(Aliens the RPG was going to use something like this, if I recall correctly) or make jumping physically driven. Oh, and for enemies and other moving characters, usually a form of local avoidance is used.