1
\$\begingroup\$

It bothers me that a lot of character controllers are written to rely on raycasting for movement along the ground. While this solution is very straightforward and general (especially in the sphere casting formulation!), it requires constantly casting said rays against potentially large numbers of triangles. This strikes me an inefficient - surely there's a better way? Heightmaps and tilemaps work for some special cases, and if you don't need the ability to jump, navmeshes are obviously superior to raycasting as you reduce the whole problem to some simple math in 2D. Given that I'm interested in allowing players to freely move about the world, I'm curious whether the navmesh approach can be extended and remain more efficient than the raycasting approach.

Idea:

Since the world already is described by a series of polygon meshes, it stands to reason that the geometry itself can be used as a navmesh - assuming you have a way of transferring characters between surfaces. This should work because you can use surface normals to determine which surfaces are "up" and what their angles are, approximating a hand-crafted navmesh. Transfer could be achieved by the usual broad-phase AABB approach giving way to a narrow phase where the line segment of the player's movement is used for a single raycast against the mesh. If the intersected face has a low enough slope, the player is simply transferred to the coordinates of the intersection.

From the rough sketch, I don't see any reason why this approach would be less efficient than constantly raycasting. Yet the fact I haven't seen such an obvious solution described elsewhere gives me pause to reconsider. Have I missed something? Does this have the potential to be more efficient than raycasting?

For context, we can use MMOs since they have to contend with many active characters roaming the world simultaneously and can get away with low poly geometry. I remember being able to jump on tables and trees in Everquest, so this shouldn't be outlandish as a point of discussion.

Misc:

On a related note, would it be worthwhile to open another question on "the most efficient way to ground characters without requiring hand-made navmeshes" or "How did X MMO pull this off"? General questions soliciting solutions to grounding characters are pretty common and are usually answered with raycasting, while asking for how specific games achieved a feature is usually a long-shot.

\$\endgroup\$
2
  • \$\begingroup\$ You say "a lot of character controllers are written to rely on raycasting for movement along the ground", but I wonder if they are really that common. What I mostly see is some capsule collider that is pushed down by gravity, and then you can check what it collider with (where and with what normal) to decide if it is on the ground. Which is ultimately relying on a shape cast. Also the colliders can use simpler geometry than what the player sees. Plus any good physics engine will use some spatial structure (edit: I mean oct-tree or similar) that allows to only check nearby objects. \$\endgroup\$
    – Theraot
    Oct 22 '21 at 22:21
  • \$\begingroup\$ @Theraot Raycasting is suggested in almost all SE and Reddit answers I've found. The capsule collider here is immaterial - the bottom is just a sphere, which is a point with distance. What do you mean, specifically, by shape cast? If projection onto a surface, that is essentially what I am suggesting. As for optimizing collision meshes, these are indeed options, but they apply to a limited situation: where the geometry is small in comparison with the scene. If you instead have a big castle or level mesh, you will need to decompose it (not always possible) to apply these techniques. \$\endgroup\$ Oct 23 '21 at 0:51

You must log in to answer this question.

Browse other questions tagged .