Grab a cup of something.
Collisions In 3DGetting up and running with a 3D first-person game in Unity is quick and easy. When it comes to collision and player movement, scene meshes can be marked as a solid colliders on import and there's some half-decent FPS player movement controllers, with or without physics. Build a scene, make it solid, drop in your player, walk around. Done.
Typical 3D colliders. The near table legs and distant chair have no collision, to avoid catching the player.
Except:
JitteringWithout careful planning, walking into certain configurations of colliders can causing the player's capsule to jitter awkwardly.
Unexpected collisionsThe Obra Dinn is a dense ship with low ceilings, and there's often cargo and other stuff strewn about the decks. Smaller objects above or below the player's general line of sight can block the player's movement, hit their head, or bump them upwards while walking, which makes moving around uncomfortable and frustrating.
Poor scene rotationThe game has basically one environment, but in many flashbacks the ship is statically pitched at a steep angle as it crashes through the waves. The player remains upright in these scenes and hits the tilted colliders normally in 3D. This leads to many previous walls becoming ramps that can now be walked right up, pinches that trap the player's capsule, or just general chaos.
Falling through the floorFor whatever unfortunate reason, Unity 3D physics behave differently on different computers. With the FPS controller code I'm using, these differences manifest as falling through the solid decks at random spots.
A pitched ship with manually-added upright collision boxes to prevent walking over the edge or getting
pinched while walking around.
Most of these problems are pretty typical, and can be fixed with code hacks and careful collider placement and tweaking. Unfortunately for me, there's >40 flashback scenes with drastically different ship configurations. Hand-tweaking each of these would take forever, and there's good odds I'd miss at least a few pinching ceilings, invalid ramps, annoying obstacles, jittery corners, etc somewhere. I'd really like a robust generalized solution for smooth, well-defined player movement.
Player Movement on the Obra Dinn 1 The player's feet never leave the ground. No jumping, no falling.
2 Player movement is mostly limited to traversing large manifold surfaces (decks).
3 Decks are stacked vertically and connected via narrow staircases.
4 Most ship geometry is static.
5 The ship can be tilted in any direction, sometimes extremely.
6 The player shape is modeled as a capsule with radius and height, always upright regardless of ship tilt.
7 There are a few dynamic objects (doors) that affect player movement.
8 There are many (statically built) ship configurations.
Extra Dimensions UnwelcomeOne thing that's always frustrated me with standard 3D collision is how hard it is to visualize. Can I creep under that branch? Fit through that doorway? Visualization is the core method I use solve problems and figuring out the best way to visualize something usually leads me to a decent solution. How can I visualize 3D collision better?
The key for Obra Dinn turns out to be ditching the 3rd dimension entirely and treating ship collision as top-down 2D maps. Each deck has its own map and they're connected via special staircases. I built a system called "Walkways" to automatically generate and use these 2D maps.
WalkwaysOnce we decide that player movement and collision can happen in 2D, the challenge is how to automatically collapse the complex 3D scenes into 2D without the need for manual touchup. Walkways encapsulate this as an offline build process. I'll first cover how individual walkways are built to let the player walk around on a single manifold surface. After that I'll talk about how multiple stacked walkways can be connected together to allow full navigation through a complex 3D scene.
A small test scene. Blue capsule is the player.
The Ground FloorWalkways are built from several components, starting with a floor. The floor defines the ground surface that the player sticks to. It doesn't have to be flat - the geometry can include bumps, dips, ramps, etc. The only restriction is that the player's foot position always stays on the highest Y point of the surface; no overlapping.
The floor
Brow and Knee HeightsOur goal is to take the collection of 3D obstacles in the scene and reduce them to a top-down 2D representation. Since we're generating a 2D map of a 3D scene, we need to decide which slice of that scene will contribute to the map. Ideally we want to ignore small obstacles on the ground and ceiling and only consider the parts of obstacles that would cross the player's middle. To do this, "brow" and "knee" heights are defined as offsets from the floor. Anything above the knee and below the brow is considered solid. Anything outside this region should be ignored.
Solid region between brow and knee heights, defined as offsets from the floor.
Poor Man's CSGIgnoring anything outside the solid region is easy to say, but how can we actually implement it? One way would be to run full geometry CSG on the shapes, intersecting each obstacle with the solid region. That's mathy and prone to CSG fuckups, the worst kind.
Instead, we turn to the GPU:
1 Create a down-facing orthogonal camera that encapsulates the entire scene.
2 Render the floor+brow offset depth encoded into the RG channels of a render target.
3 Render the floor+knee offset depth encoded into BA channels of the same render target.
4 Render all the obstacles into another render target, clipping any pixels greater than or less than the brow/knee depths.
Floor with brow and knee height offsets encoded into RGBA, and resulting obstacle map
Debug view of the result. Note how the geometry is properly clipped based on the uneven floor shape.
Animating through different brow/knee heights. First animated gif of the post and it's a good one.
AlmostThis "GPU CSG" technique is fast and easy but it critically misses writing any edges perpendicular to the top-down camera. In this case, the tall wall and tall cylinder are absent from the obstacle map. This is because their top/bottom caps are outside the solid region and the perpendicular edges resolve to no visible pixels.
There's a relatively simple fix for this. Instead of just rendering a single top-down orthogonal view it's possible accumulate multiple renders, skewing the view a little bit each time using a carefully-calculated oblique matrix:
Skewed accumulated obstacle map. The wall and cylinder now appear.
This accounts for all shapes within the solid region and has the added bonus of exposing an "expansion" feature:
Animating through various skew magnitudes
VectorizingNow that we have the obstacle map, how can we use it? There's more than one way, but I decided keeping huge images around was a waste and I should vectorize it first. To do that, I reached back 9 years to dig out some code from one of our old games,
Mightier. There, the code was used to convert player drawings into inflated 3D characters that run around in small puzzle-platformer levels. Sort of. It's a weird game.
Anyways, my partner wrote the 1-bit bitmap vectorizer code for Mightier and after a quick port from C++ to C# it worked great for this task. The algorithms are pretty simple, based on flood fills and border tracing. The end result is a hierarchy of shapes.
Vectorized obstacle map
Debug shapes rendered in-scene
The vectorizer also has a simplification pass, which makes it easy to scale the level of detail. I don't adjust this currently; just set it once and forget it. Maybe it'll be useful later when I want to tweak the complexity in some scene. It makes another decent animated gif though so here:
Running through the simplifier with various thresholds
To a Physical WorldWith the vectorized shapes, it's now possible to get a 2D physics simulation going. You could add a simple circle or ray caster and be most of the way there. Or if you're on Unity you can just use the built-in Box2D implementation, which is totally independent of the 3D physics/collision system and can run concurrently.
Shapes converted to PolygonCollider2Ds, from XZ to XY
Unity makes this really easy - the shape points can be fed directly into closed PolygonCollider2D or open EdgeCollider2D components. There's some need to consider the coordinate changes since the 2D physics system runs on XY and our 3D world uses XZ, but it's not too painful.
Where's the AirBecause the vectorizer finds all the nested shapes, and there may be shapes that completely enclose the player's movement area (like the half-cylinder wall on the left), it's necessary to know which part of the obstacle map is considered "air" or empty space. In the Unity 2D physics world, this determines which shapes the player will be confined within (possibly-open EdgeCollider2Ds) and which ones they're prevented from entering (closed PolygonCollider2Ds).
Given my pipeline I found it simplest to just add a locator child to the floor plane to specify where the open air was.
Placing the "air" locator to define empty space where the player can move
Resultant shapes with different air positions (white cross)
In the debug view, the dotted orange line represents the EdgeCollider2D that contains the player's outer bounds of movement. Moving the air position to inside the small half-circle wall limits the player to that space since there's no connection to the outside.
This could be used with the shape expansion parameter set to the player's radius to easily show the accessible area, a super useful thing in navigation. I say "could" because right now the shape expansion is only good enough for catching perpendicular edges and doesn't give exact expansions. Visually auditing the walkway is so easy currently that I haven't gone further.
2D walkway generated for the top deck of the ship
(Too big for one post. Continued in next)