Benjamin Yang · EAE 6320

Engine System Update #2: Collision

Solid objects now stop each other, raycasts work, MyGame is a small platformer built on both, and the first version of the user guide is written

⬇ Download the demo (Direct3D, x64) ⬇ OpenGL build (x86) User guide (first version) Unzip anywhere and double click MyGame.exe. ESC closes the game. The left and right arrow keys move the orange ball (the player), and the up arrow or SPACE jumps, but only while a raycast says that it is standing on something. W/A/S/D move the camera and Q/E turn it. Every touch that starts or ends is written to eae6320.log next to the exe.

Where the project is

My Engine System is a collision system: sphere and axis-aligned box colliders described in data files and attached to game objects, collision layers that decide what can touch what, and events that tell the game when colliders start touching, keep touching and stop touching (that much was Update #1). Since then the system keeps solid objects out of each other and answers raycasts, MyGame has become a small platformer that is built on both, and the first version of the user guide is written. This is what my proposal planned for this update:

Planned for Update #2Status
Solid response and velocity correctionDone. A dynamic collider is pushed out of a static one, two dynamic ones are pushed apart equally, and the velocity that points into the surface is removed. Triggers never push and are never pushed.
Triggers and the layer tableAlready done in Update #1. Raycasts now filter by layer too.
RaycastsDone. Spheres (a quadratic) and boxes (the slab method), a layer mask, triggers only if asked for, and the closest hit with its collider, point, normal and distance.
The MyGame demoDone. Walls, a floor and steps of crates stop the player, a raycast decides whether it can jump, the coils are pickups (triggers), and an enemy patrols with a raycast and reacts to the player through events.
First version of the user guideDone. Engine/Collision/UserGuide.md is part of the Collision project, and it is also online (link at the top).
The diagram from my proposal
The diagram from my proposal. After this update everything in it exists: the game moves objects, Collision::Update() pushes solid objects apart and sends the events, and the game can ask Raycast() questions.

The demo

MyGame (Direct3D, x64) just after it starts
MyGame (Direct3D, x64) just after it starts. The player (orange) has fallen onto the floor. The yellow diamond under it is drawn where a ray cast straight down from the player hits the world. On the left the patroller (violet) walks back and forth in a pen behind a crate, under one pickup; on the right three steps of crates lead up to the other pickup. The floor, the two walls and the seven crates are static colliders, and the pickups are static triggers: 14 colliders in all.
Holding the right arrow against the first step
Holding the right arrow against the first step. Every update the player moves 0.05 units into the crate, and Collision::Update() pushes it back out and removes the velocity that points into the crate, so it stays pressed against the face. In Update #1 it would have gone straight through. The crate counts its touches in OnEnter and OnExit and is drawn red while anything touches it.
Jumping onto the fence crate
Jumping onto the fence crate. The marker shows where the ground raycast hits, so while the player is still in the air the marker is already on top of the crate it will land on. The game only allows a jump when that hit is no more than the player's radius plus 0.05 below its center.
At the top of the steps (holding right and jump climbs them)
At the top of the steps (holding right and jump climbs them). The pickup that floated here is gone: it is a trigger, and its OnEnter hides it and disables its collider. It comes back four seconds later. The top crate is red because the player is standing on it: resting on something counts as touching, so the crate got one OnEnter and then gets OnStay every update.
Landing on the patroller
Landing on the patroller. Both are dynamic, so each is pushed half of the way out. The player's OnEnter looks at the contact normal, which points from the patroller toward the player. Mostly up means that it landed on top, so it bounces. Pickup 1 is gone because the player collected it on the way in.
When the patroller walks into the player from the side, the normal is mostly horizontal, so the player is knocked back (up and away from the patroller) and drawn red for half a second, and the patroller turns around and walks off to the left
When the patroller walks into the player from the side, the normal is mostly horizontal, so the player is knocked back (up and away from the patroller) and drawn red for half a second, and the patroller turns around and walks off to the left. The player was knocked against the fence crate, which is red because the player is touching it.
The OpenGL (x86) build at the top of the steps
The OpenGL (x86) build at the top of the steps. Both builds behave the same.

This is the beginning of the log from the run in the knockback screenshot (the player jumped over the fence crate into the pen). The system writes the layers when it starts. The rest comes from MyGame's event functions and its raycasts:

Collision: initialized with 4 layers from "data/Collision/game.binlayers"
Collision:   layer 0 "world" touches: player, enemy
Collision:   layer 1 "player" touches: world, enemy, pickup
Collision:   layer 2 "enemy" touches: world, player
Collision:   layer 3 "pickup" touches: player
The application was successfully initialized
MyGame: the patroller's raycast hit the fence crate 0.60 units ahead, so it turned around
Collision: the player started touching the floor (normal +0.00 +1.00 +0.00, depth 0.100 before it was pushed out)
MyGame: the patroller's raycast hit the left wall 0.60 units ahead, so it turned around
Collision: the player stopped touching the floor (OnStay was called 79 times in between)
Collision: the player started touching the fence crate (normal +1.00 +0.02 +0.00, depth 0.000 before it was pushed out)
Collision: the player stopped touching the fence crate (OnStay was called 2 times in between)
MyGame: the patroller's raycast hit the fence crate 0.60 units ahead, so it turned around
Collision: the player started touching pickup 1 (above the pen) (normal +1.00 +0.00 +0.00, depth 0.047 before it was pushed out)
MyGame: the player collected pickup 1 (above the pen) (1 collected so far)
Collision: the player stopped touching pickup 1 (above the pen) (OnStay was called 0 times in between)
Collision: the player started touching the patroller (normal +0.77 +0.64 +0.00, depth 0.054 before it was pushed out)
MyGame: the patroller knocked the player back and turned around
MyGame: the patroller's raycast hit the left wall 0.60 units ahead, so it turned around
Collision: the player stopped touching the patroller (OnStay was called 0 times in between)
Collision: the player started touching the patroller (normal +0.46 +0.89 +0.00, depth 0.016 before it was pushed out)
MyGame: the player landed on the patroller and bounced off
Collision: the player stopped touching the patroller (OnStay was called 0 times in between)

The depths are now "before it was pushed out". Falling onto the floor at about 7 units per second sinks about 0.1 units into it in one update (MyGame updates its simulation 60 times a second now), and the push takes all of it out again. The touch with the fence crate's side has a depth of 0 because the player walks exactly 0.05 units per update and happened to stop right at the face. The patroller sees the wall and the crate at 0.60 units, its radius plus the 0.1 units that it looks ahead. The two touches with the patroller show the threshold in the player's OnEnter. The first normal, (0.77, 0.64), doesn't point up enough (0.7 is the threshold), so it counted as a hit from the side. The second, (0.46, 0.89), was a landing on its head.

Solid response

Collision::Update() has one new step, between finding the pairs that touch and sending the events:

Left: what the response does to a sphere that the game has moved into a static box
Left: what the response does to a sphere that the game has moved into a static box. Right: the slab method that raycasts use for boxes (next section).

The rules come from my proposal. A collider is dynamic unless it is static, and solid unless it is a trigger:

// cWorld.cpp, ResolveOverlaps(): called by Collision::Update() with every pair that touches
// (solidPairs are the ones where neither collider is a trigger)
for ( unsigned int passIndex = 0; ( passIndex < s_maxResolutionPassCount ) && !solidPairs.empty(); ++passIndex )
{
	bool wasAnythingMoved = false;
	for ( const auto& pair : solidPairs )
	{
		// The overlap is found again from where the colliders are now (an earlier pair might have moved one of them)
		Math::sVector normal;	// (from b toward a)
		float penetrationDepth;
		if ( !Intersections::DoShapesTouch( GetShape_world( *pair.a ), GetShape_world( *pair.b ), normal, penetrationDepth ) )
			continue;
		auto& rigidBody_a = pair.a->GetRigidBody();
		auto& rigidBody_b = pair.b->GetRigidBody();
		if ( pair.b->IsStatic() )
		{
			// Only a moves: all of the way out, and it can't keep moving into b
			rigidBody_a.position += normal * penetrationDepth;
			RemoveVelocityIntoSurface( rigidBody_a.velocity, normal );
		}
		else if ( pair.a->IsStatic() )
		{
			rigidBody_b.position -= normal * penetrationDepth;
			RemoveVelocityIntoSurface( rigidBody_b.velocity, -normal );
		}
		else
		{
			// Both are dynamic: each moves half of the way, and their approaching speed is taken from both equally
			const auto halfOfTheCorrection = normal * ( penetrationDepth * 0.5f );
			rigidBody_a.position += halfOfTheCorrection;
			rigidBody_b.position -= halfOfTheCorrection;
			const auto approachingSpeed = Math::Dot( rigidBody_a.velocity - rigidBody_b.velocity, normal );
			if ( approachingSpeed < 0.0f )
			{
				const auto halfOfTheVelocityChange = normal * ( approachingSpeed * 0.5f );
				rigidBody_a.velocity -= halfOfTheVelocityChange;
				rigidBody_b.velocity += halfOfTheVelocityChange;
			}
		}
		if ( penetrationDepth > 0.0f ) wasAnythingMoved = true;
	}
	// Once a pass doesn't move anything every overlap has been resolved
	if ( !wasAnythingMoved ) break;
}

// RemoveVelocityIntoSurface(): moving away from the surface or along it is left alone
const auto speedAlongNormal = Math::Dot( io_velocity, i_normal );
if ( speedAlongNormal < 0.0f )
	io_velocity -= i_normal * speedAlongNormal;

Decisions

Raycasts

// Collision.h
struct sRaycastHit
{
	cCollider* collider = nullptr;	// the closest collider that the ray hit (valid until the next Update())
	Math::sVector point;	// where the ray entered it
	Math::sVector normal;	// the surface's unit normal there, pointing back toward the side the ray came from
	float distance = 0.0f;	// how far the point is from the ray's origin
};
bool Raycast( const Math::sVector& i_origin, const Math::sVector& i_direction, const float i_maxDistance,
	sRaycastHit& o_hit, const uint32_t i_layerMask = ~uint32_t( 0 ), const bool i_shouldTriggersBeHit = false );

The direction can have any length except 0 (it is normalized). Only colliders whose layer is in the mask can be hit, so Collision::GetLayerMask( "world" ) finds only walls and floors. The layers file's interactions don't matter here. Disabled colliders, triggers (unless asked for) and colliders that the game has already released are skipped. A ray that starts inside a collider doesn't hit that collider, so a ray cast from an object's center never hits its own collider (my ground check relies on that). Raycast() changes nothing, so it can be called at any time after Initialize(), even from inside an event, and o_hit is only written when something was hit. Every collider is tested, and each test only looks as far as the closest hit found so far.

Using it from a game

This is how MyGame uses the new parts (shortened). The names and numbers are MyGame's, but the patterns (a look-ahead ray, a ground check, a trigger that disables itself, reacting to the contact normal) work in any game:

// cMyGame::UpdateSimulationBasedOnTime() (shortened)
// 1. The patroller looks ahead, only at the "world" layer, and turns around before it bumps into anything
Collision::sRaycastHit hit;
if ( Collision::Raycast( patroller.position, Math::sVector( m_patrollerDirection, 0.0f, 0.0f ),
	s_patrollerRadius + 0.1f, hit, m_layerMask_world ) )
{
	m_patrollerDirection = -m_patrollerDirection;
}
patroller.velocity = Math::sVector( m_patrollerDirection * s_patrollerSpeed, 0.0f, 0.0f );
// 2. Everything moves as usual (the player's acceleration is gravity); then the collision system
//    pushes the player out of whatever it moved into and sends the events
m_object_player.Update( i_elapsedSecondCount_sinceLastUpdate );
m_object_patroller.Update( i_elapsedSecondCount_sinceLastUpdate );
Collision::Update();
// 3. The ground check: one ray straight down finds the world under the player
if ( Collision::Raycast( player.position, Math::sVector( 0.0f, -1.0f, 0.0f ), 50.0f, hit, m_layerMask_world ) )
{
	m_isPlayerOnGround = hit.distance <= ( s_playerRadius + 0.05f );
	m_object_marker.rigidBodyState.position = hit.point + Math::sVector( 0.0f, 0.03f, 0.0f );
}

// cMyGame::UpdateSimulationBasedOnInput(): jumping is only possible on the ground
if ( m_isPlayerOnGround && ( UserInput::IsKeyPressed( UserInput::KeyCodes::Up ) || UserInput::IsKeyPressed( UserInput::KeyCodes::Space ) ) )
	m_object_player.rigidBodyState.velocity.y = s_jumpSpeed;

// A pickup's OnEnter (pickups are triggers in "pickup", and only "player" interacts with that layer)
pickup.collider->OnEnter = [this, &pickup, i_pickupIndex]( const Collision::sContact& )
{
	pickup.isVisible = false;
	pickup.collider->SetEnabled( false );	// nothing can touch it until it comes back
	m_secondCount_untilPickupRespawns[i_pickupIndex] = s_pickupRespawnDelay;
};

// The player's OnEnter, when the other collider is the patroller
// (the contact's normal points from the patroller toward the player)
if ( i_contact.normal.y >= 0.7f )
{
	velocity.y = s_bounceSpeed;	// it landed on the patroller's head
}
else if ( m_secondCount_hurtLeft <= 0.0f )
{
	// hit from the side: knocked back, away from the patroller, which turns around
	const auto awayFromThePatroller = ( i_contact.normal.x >= 0.0f ) ? 1.0f : -1.0f;
	velocity = Math::sVector( awayFromThePatroller * s_knockbackSpeed_sideways, s_knockbackSpeed_up, 0.0f );
	m_patrollerDirection = -awayFromThePatroller;
	m_secondCount_hurtLeft = s_hurtDuration;	// drawn red for half a second
}

The demo's data files changed a little: the floor's collider is thicker, there is a wall collider for the two new walls, and the spinner from Update #1 became the pickup collider that both pickups load. The layers file is the same as in Update #1 apart from its comments. The new wall mesh and the marker mesh are human-readable mesh files like the cube.

-- Colliders/floor.collider: a whole unit thick now (it was 0.1 in Update #1), with its top at the floor mesh's plane
return
{
	shape = "box",
	halfSize = { x = 4.0, y = 0.5, z = 4.0 },
	center = { y = -0.5 },
	layer = "world",
	isStatic = true,
}

-- Colliders/wall.collider: matches the new 0.5 x 6 x 1 wall mesh (one at each end of the floor)
return
{
	shape = "box",
	halfSize = { x = 0.25, y = 3.0, z = 0.5 },
	layer = "world",
	isStatic = true,
}

-- Colliders/pickup.collider: the spinning coil from Update #1, now used by both pickups
return
{
	shape = "box",
	halfSize = { x = 0.55, y = 0.85, z = 0.55 },
	layer = "pickup",
	isTrigger = true,
	isStatic = true,	-- (it turns, but an axis-aligned box that encloses it doesn't change)
}

The user guide (first version)

The guide is in Engine/Collision/UserGuide.md, which is part of the Collision project so that it shows up in Visual Studio next to the headers. It is also online at the link at the top of this page. It is written for a classmate who has never seen the system:

The header comments were updated as well. Collision.h explains the three things that Update() does and has a raycast example, and cCollider.h has a new RESPONSE section.

Testing

What is left for the final week

The presentation is on Monday, November 16, and the final write-up is due on Thursday, November 19. What is left: