Port a Unity Game to Your Own Engine: Part 21

A concrete look into a data-oriented approach to engine development.

In Part 21 we’ll look at collision detection. In the Unity project, the physics system is used for collision detection, which is an expensive and complex option. We’ll reduce the problem to some simple checks and organize the data so that collision and damage systems can be handled independently from the enemy, hero, and bullet instances. (And so they can all share the same solution.)

21.0 Visualize broad-phase collision grid

Visualize a 16x16 grid to potentially use as a broad-phase collision. Think through possible some storage options of collision data:

• Option 1: Store 1 bit per grid section. If there is a hit, check against all possible inputs. Given the counts are low, it's not unreasonable.

• Option 2: Store 1 byte per grid section. Store index of item at that grid section. If there is a hit, only compare against the indices that are indicated. If multiple items are on the same grid section, just overwrite. Given relative sizes, there's not likely to be any noticeable issues.

• Option 3: Store 16 bytes per row. 1 byte for count. 15 bytes for elements. For each row, a list of items overlapping the row. If there is a hit, walk the list of items indicated. Overlapping items are non-issue. 15 elements per line is a reasonable constraint.

21.1 Collision grid data and input maps

I was thinking of a case I’d like to try that would make option 2 problematic: Intentionally fully overlapping objects. e.g. a shield around a ship. Which makes the case for option 3. So, we’ll start with that. (Although as I said earlier, revisions on various speeds, sizes, and spawn frequencies may change the situation enough to require a completely different solution.)

Start by creating collision_grid. We’ll hook this up to enemy_instances, hero_instances, enemy_bullets, and hero_bullets to get grid data for each of them respectively. To hook them up, we’ll map collsion_source_instances and collision_source_types.

I decided to simplify the mapping process a bit for when I don’t specify a source (i.e. when the offsets in the map are assigned at runtime.) But to do that, I need to fix up the builder scripts a bit.

TODO:

• Need to support importing schemas in schemas, to look up types. (Without source data, we can’t infer the type anymore.)

• Bullet and hero/enemy type data store radius in different formats (radius_q8 and radius_q4, respectively.)

21.2 Support import types in schemas

Update export_bin to use imported schemas to gather type information for maps.

21.3 Support different radius ports

Update collision_grid to have both radius_q4 and radius_q8 ports. The appropriate port is mapped, where the other remains NULL. Update export_c_header to return NULL when offset is zero.

21.4 collision_grid_update

Updating collision_grid_update for the various input cases highlighted a few issues that we need to resolve. There’s no tracking of filtered out instances (e.g. the live_instances bit set for enemy instances.) Got the basic update working and visualized the data being stored to help sort out the issues.

On the left are the hero instances and hero bullets. On the right are the enemy instances and enemy bullets. The play area is divided into 16 slices vertically. The number of instances overlapping that a slice is stored, and the indices of the specific instances are stored per slice, for later more fine-grained collision testing.

21.5 collision_grid_update filter

Add an enabled filter for collsion_grid_update. Enemy instances have a bit vector for each instance that is cleared when the path is complete. Nothing else has enabled bits at the moment, but it’s easy to anticipate them being needed once the rest of this system is in place and we need to start tracking destroyed things.

Also I don’t have dependencies in my makefile setup correctly. Schemas can be dependent on other schemas, so build order for those matters. Which bit me here again for a few minutes. That definitely needs to get fixed soon.

21.6 Fix makefile dependencies

Add dependencies for schema files in makefile. Nothing automated for now.

21.7 Gather damage and health data

Open Unity project and find the health and damage data. Add to enemy_instances, hero_instances, enemy_bullets, and hero_bullets.

21.8 Create collsion_damage

Create a type to gather damage ring buffer (position, time, amount) for a pair of grid types. Pairs to be tested:

• hero_bullets vs. enemy_instances

• enemy_bullets vs. hero_instances

• hero_instances vs. enemy_instances

Also:

• Rename “ref” in schema to “context” (two names for the same concept.)

• Rename “collision_source_types” to “collision_source_radius” for clarity.

21.9 Generate common code for cut and paste

At some point I want to look at codegen for removing the boiler plate around getting the right variable addresses for data lookup in the context. Since there’s only one possible way to do it, I shouldn’t need to specify it every time. In the meantime though, I’m just going to add code I probably want to cut and paste as comments to the generated c header.

Also some other things to the TODO list I want to get to:

• Time in uint64_t as nanoseonds

• binary data column offset to be relative to the sheet instead of the file

• schema yml<->binary converter

• tool to waypoint curve entry

• data playground tool

• s/TypeIndex/Index/g

21.10 Collect damage events

Also output context struct for copy/paste.

Implement collision_damage_update to collect up damage events. Keep it pretty simple:

• Do A and B have anything on the same slice?

• If so, for each of the instances on A and B on that slice,

• Test if each radius overlaps.

Oh, I missed this, so next I also need to add:

• Don’t re-add same collision multiple times if they happen on multiple slices.

21.11 Don’t report same collision pair multiple times

Observation: If the pair exists in the previous slice, we don’t need to add anything. Any collision would have been handled in the previous slice. If it doesn’t exist in the previous slice, the only other possible place is the next slice, which will be handled by this same rule. There are no non-contiguous same-pairs stored.

Create double buffered bit vector on the stack to track previous and next a and b instances processed. On both a and b bits set on previous, do not re-store event.

Cheap and easy.

Add an additional debug view of collision_damage.

21.12 Prepare to accumulate damage

Re-arrange damage_events. Remove redundant time. Combine a and b data under the same sheet.

In order to accumulate anything, you need a reset flag. Add a reset flag to source_instances so that accumulated damage can be stored in collision_damage. Fix up enemy_instances and bullets to set the reset flag on spawn and clear on move. Also change behavior slightly so that instances don’t move on first frame spawned (they are at the spawn location.)

21.13 Accumulate damage

Clear accumulated damage based on reset flag. Add to accumulated damage at each event. Update the debug view to show the accumulated damage for each instance in each damage event.

21.14 Destroy on damage

Add an input line to bullets for damage values. Compare those to health values and destroy if exceeds. Something doesn’t look quite right though…

21.15 Debug and discover the problem

The problem is that I’ve been playing fast and loose with ring buffers and there isn’t really a rule around the data for them. So bullets, being first implemented, are a bit different from the others. The solution is to:

• All sheets should store capacity

• Sheet counts can exceed capacity

• Remove spawned_count from bullets.

21.16 Destroy hero bullets correctly

Updated count and capacity rules to handle ringbuffers consistently and fixed everything up. Turns out though that wasn’t the actual problem. A small typo in the schema meant that the reset flags weren’t being received.

21.17 Destroy enemy instances

Give accumulated damage to enemy_instances. Check damage versus health, and disable enemies.

21.18 hero instances vs enemy bullets

Map the inverse case from above. Enemy bullets damage and destroy handled. Need to decide game loop when hero is destroyed before we hook that up though.

21.19 You died

Remove old level_index from game_state. Quick and dirty version of hero loop. Reset game on hero death.

Quick check on the state of memory and performance.

Links to files below for paid subscribers.