• Game Engine Physics Development by Ian Millington
• How to Create a Custom Physics Engine by Randy Gaul

And some frameworks:

• Box2D
• Project Chrono

But something that has typically interested me with physics engine is how to potentially detect collisions. Now this is primarily a data structure problem, as we would have to reason about how we would want to structure all of our physics bodies based on their positions. Ultimately, the end goal of this structure is to provide a fast way to check potential collisions without having to brute force and compare every single physics body with each other (this becomes an n² check!).

Spatial Hashmaps

One way to store physics bodies is to divide your play area into a group of cells as a grid. We can then store a bunch of physics bodies into a cell and determine which cells that each physics body is in. By design spatial hash maps are hash maps with chained linked lists as their values. Therefore, potential physics bodies in the same cell will be registered into the same hash.

Key Values
---------
1 -> [A] [B]
2 -> [D]
3 -> [E] [F] [Z]

An example with the left column being the key and the right column being multiple values with the same key.

The Hash Function

Each physics body is typically defined with a position represented as Cartesian coordinates (float3) . Ultimately, the hash function will take each axis value and combine the values into a key which we would use to register into the hash map.

A good hash function balances balances the number of potential collision we have per cell. If we have a very accurate hash function, then we may generate new hash map entries for physics bodies which are close together. If we have an inaccurate hash function, then we potentially may add in all physics body positions into a few cells, which may lead us closer to polynomial time to detect collisions.

By dividing the physics body position x and y values by the grid size and adding the components together, we get a decent hash that can contain multiple physics bodies. Here’s the pseudo code of the description above.

int Key(int size, float3 v)
{
  return ((int)(floor(v.x / size) + floor(v.y / size)) * size);
}

Examples for: (1, 1, 0), (2, 1, 0), and (20, 11, 0) this hash function will produce:

Point: (1, 1, 0)
-------
(floor(1 / 10) + floor(1 / 10)) * 10 = hash_value
(0 + 0) * 10 = hash_value
0 = hash_value

Point: (2, 1, 0)
-------
(floor(2 / 10) + floor (1 / 10)) * 10 = hash_value
(0 + 0) * 10 = hash_value
0 = hash_value

Point: (20, 11, 0)
-------
(floor(20 / 10) + floor (11 / 10)) * 10 = hash_value
(2 + 1) * 10 = hash_value
30 = hash_value

Physics Shapes

Physics bodies are typically defined with a physics shape. For my needs in Carté Diem, most physics bodies currently are defined as a box. Complex shapes will eventually be included later down the line. For example, our player Ellen can occupy multiple cells:

Now the simplest way to ensure that Ellen occupies multiple cells is likely to brute force and sample some points along each edge of the box. This is obviously not a very nice solution because we can potentially register the same physics body multiple times to the same hash. We can, of course, do a final check to ensure we uniquely add physics bodies to a hash, but we possibly would not know how many times we have to perform this uniqueness check.

But even with brute force, a question like this popped up during development:

• Can we accurately get all the cells that the box physics shape occupy?

Well this problem was similar to an old Graphics problem I learned about which was determining which pixel a line potentially occupied. This is known as Bresenham’s Line Algorithm.

The idea behind the algorithm is to calculate the slope of a line segment and to sample intervals to check which cell the sampled line segment belongs to. Here’s the pseudocode implemented in my physics engine below.

Line(float2 from, float2 to, int cellSize) 
{
  value = floor(from);
  diff = to - from;
  step = sign(diff);
  offset = float2(
   to.x > from.x ? 
     ceil(from.x) - from.x : 
     from.x - floor(from.x),
   to.y > from.y ? 
     ceil(from.y) - from.y : 
     from.y - floor(from.y));
  angle = atan2(-diff.y, diff.x);
  angles = float2(cos(angle), sin(angle));
  tMax   = offset / angles;
  tDelta = cellSize / angles;
  dist = abs(floor(to.x) - floor(from.x)) + 
    abs(floor(to.y) - floor(from.y));

  // v will be associated cell's position. We can add
  // this to a collection or process this immediately
  v = FloorToNth(value, cellSize);
  
  for (int i = cellSize; i < dist; i+=cellSize) 
  {
    if (abs(tMax.x) < abs(tMax.y)) 
    {
       tMax.x += tDelta.x;
       value.x += step.x * cellSize;
    }
    else 
    {
       tMax.y += tDelta.y;
       value.y += step.y * cellSize;
    }
    // Recalcule v again to find a new cell
    v = FloorToNth(value, cellSize);
  }
}

What makes Brehansem’s line algorithm incredibly useful is visualization. If we collect all cells associated with the line we can provide the cell’s position and draw a heat map which will visualize the density of potential colliders.

Physics Collision and Spatial Mapping was originally published in initialPrefabs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Questions or comments I hear quite often when I mention I write unit tests for games are:

Why do you need to write tests when games are visual and change over time?

Can’t you just ask someone to help you test your game so you can catch bugs?

Those questions are quite true to a degree and there are certainly times when I think about not writing tests and just being able to move on to the next feature instead. But, more often than not, some of the pain points I had with scaling a game are:

• it’s easy to spot bugs with your eyes but it’s difficult to pin point/debug where the issue is
• with a small team and when we’re under crunch time, not everyone has the time to regressively play test features to ensure they work

You won’t completely solve those issues with unit testing but you can certainly alleviate the pain of those common scenarios by writing smart unit tests.

Game Background

So before I get into how my team and I go about unit testing, it’s worth explaining what our game, Project Arena (name pending), is basically about.

Project Arena is a 2D arena local multiplayer game where players choose cards between each round to defeat their opponent in battle. The game is played with a common local server, like your laptop, and smart phones as client controllers and secondary screens for each player.

I’ll certainly post more about this during the upcoming weeks/months.

Because we’re dealing with network code, we actually have to write tests to reason about our logic to ensure that we expect things to happen correctly despite the network connection. But in this blog, I’ll actually walk you through one of our test which tests our character’s visual effect and gameplay mechanic.

Note: From here on out, I’ll refer to visual effect as VFX.

We build our game using Hybrid Entity Component System (ECS), which is an architecture that allows us to separate data away from logic providing us ease of scale and performance benefits.

For a brief overview, Arturo Nereu of Unity has a nice comic strip which explains ECS in a digestible manner.

ArturoNereu/ECS_101

So much thanks and credits to him!

The Game Mechanic

The playable character is very similar to the mechanics of Megaman/X/Zero. The player can move, jump, shoot projectiles and use cards. Unlike Megaman, our player actually charges automatically since holding down a button on a phone is very uncomfortable while moving and performing other simultaneous actions.

Understanding the Data Behind Charging a Shot

Even though we use the Entity Component System, we still have dependencies on MonoBehaviour such as the Particle System.

In our case, we treat MonoBehaviours as simply objects with properties, with limited functionalities. Below is a table which shows the minimum amount of data we need to get the effect shown in the gif:

Implementing the Charge Shot Logic

So the Charge Shot behaviour is pretty simply, when the ChargeShotTimer’s Current time is greater than or equal to the max Wait time, the larger particle in the center (the parent) will play, otherwise it disappears. The child particle will always play when the Current time is greater than epsilon.

Epsilon denotes the smallest value, in our case we treat epsilon as effectively 0.

When shooting, the Current time is effectively 0, thus both particle systems will stop playing. This ensures that visually, our player does not look like they are getting a more powerful shot when shooting.

Below is the logic for our ChargeFXIndicatorSystem, which handles what was stated above.

Since we don’t actually set up our VFX to be a child of Ellen, we internally map each Particle System by its player’s ID. This keeps our character prefab light with only the data we need and keeps our VFX as a separate entity.

But, what tests are we actually writing for the VFX?

The tests are quite simple with function names that are quite verbose:

• ChargingAttackShowsChildIndicator — if we charge a shot, we show our VFX’s child Particle System
• FullyChargedAttackShowsBothIndicators — when we fully charge a shot, we show our VFX’s parent and child Particle System
• ReleasedChargedAttackShowsNoIndicator — when we shoot, we show neither the parent VFX or child VFX

[ARCHIVED] Prepping Up Our Tests

One of the benefits of testing in Unity is that we can test with real prefabs we use in our game.

To use these assets in our tests, we built a utility function to grab a copy of the assets from the project. This is the code version of dragging a prefab into the scene!

Test Fixture Set Up

Now that we have the assets, we need to set up a clean environment to perform our tests. To do this, we create a text fixture, which has the bare minimum implementation of setting up and tearing down a clean environment for each test to run in.

This helps isolate our logic from the rest of the game/systems so we ensure that the logic works correctly on its own. Below is our minimal implementation of our test fixture.

All we do in our SetUp function is we create a new test world and cache the previous, one so we can restore it in our Teardown function after a test finishes.

To quickly recap we want to test the following scenarios:

• if we charge a shot, we show our VFX’s child Particle System
• when we fully charge a shot, we show our VFX’s parent and child Particle System
• when we shoot, we show neither the parent VFX or child VFX

Here’s our ChargeFXIndicatorSystemTests:

For each test we just have to set our ChargeShotTimer and ensure that the Current time is either greater than, equal to, or less than our Wait time.

• ChargingAttackShowsChildIndicator — we can reason that the Current time has to be larger than 0 but less than our Wait time, so we just set the Current time to be 1 second.
• We only expect there to be 1 entity available after the ChargeFXIndicatorSystem updates, otherwise our system is doing something odd and creating more entities than we need!
• As for our VFX, we should expect that only the child VFX plays and not the parent, otherwise our system’s logic does not operate on our data correctly.

The rests of the tests follow the same structure but just test other values of the Current time.

Some Closing Notes

So that is the general gist of how my team and I go about testing. We usually plan our systems and tend to ask questions regarding the game design and the data we need first. This enables to really understand our direction before we start writing any code.

We also don’t go about writing tests for every single case possible. We’re a small team, so we write tests for our primary essential features. This helps us iterate quickly on our infrastructure and be able to call out poor infrastructure choices we’ve made while we’re developing our game.

Unit testing certainly takes time and patience to do and by no means replaces manual QA testing. You’ll certainly need design feedback on your game, which unit tests can’t provide.

Some additional resources I read about unit testing that I found useful are:

• https://blogs.unity3d.com/2018/11/02/testing-test-driven-development-with-the-unity-test-runner/
• https://github.com/sophiaaar/tdd-pong
• https://docs.unity3d.com/Manual/testing-editortestsrunner.html

Going About Testing in Unity ECS was originally published in initialPrefabs on Medium, where people are continuing the conversation by highlighting and responding to this story.