BLOOD CHURCH

written by @prophet_goddess // RSS

STOP DOING PHYSICS: a manifesto/tutorial for better collision with ECS

these tutorials are supported by viewers like you over at patreon and ko-fi.

action games are essentially a complex set of rules for what happens when things collide with other things. even outside of action games, many games require collision detection. the solution most big game engines go with for this is an enormous clunky rigidbody physics simulator, despite the fact that such heavy duty tech is only required for a vanishingly small minority of games. on top of this, the architecture used by engines such as Unity and Unreal to handle collision responses is catastrophically bad, leading to a nightmare of tightly coupled spaghetti code that means that whenever you change the behavior of any object in your game you break everything. we can do so much better. let's write some good code.

pt 0: setup

i'm going to be using C# and FNA for these examples, but these principles apply in any environment. if you want to follow along, you can get started quickly with all the tools you'll need with my FNA ECS Template. follow the instructions over there and you'll be up and running in no time. feel free to delete the ExampleRenderer, ExampleSystem, and ExampleComponent, those are just for demonstration purposes. if you want to know all the gory details of how the template is set up, check out this writeup i did

pt 0a: what is ECS?

i have written the "what is ECS?" paragraph a lot in writeups and tutorials i've made, so i'll pull a morpheus here and say that no-one can explain to you what ECS is, you have to see it for yourself.

pt 1: rendering

before we can detect collision, we need to draw something on the screen. we'll do this really quickly and simply, because this is not a tutorial about rendering. you can do this however you want, and just ignore it if you're following this tutorial in a different framework and do your own thing.

first, in LoadContent, generate a new 1x1 texture:

protected override void LoadContent()
{
    /*
    CONTENT
    */

    SpriteBatch = new SpriteBatch(GraphicsDevice);

    var white1x1 = new Texture2D(GraphicsDevice, 1, 1);
    white1x1.SetData(new Color[] { Color.White });

this creates a 1 pixel by 1 pixel texture that is just white. this will allow us to very easily draw arbitrarily sized rectangles.

now we need a new component to store information about these rectangles. XNA has a Rectangle struct, but it has an issue for our purposes: it assumes that the X and Y coordinates of the rectangle are the top left and not the center. this is a perfectly reasonable assumption to make in many circumstances, but for what we want, we want X and Y to be the center. create a new file in Components called AABB.cs:

using Microsoft.Xna.Framework;

namespace CollisionTutorial.Components.Motion
{
    public readonly record struct AABB(float X, float Y, float Width, float Height);

    public static class AABBExtensions
    {
        public static Vector2 Min(this AABB aabb)
        {
            return new Vector2(aabb.X - aabb.Width * 0.5f, aabb.Y - aabb.Height * 0.5f);
        }

        public static Vector2 Max(this AABB aabb)
        {
            return new Vector2(aabb.X + aabb.Width * 0.5f, aabb.Y + aabb.Height * 0.5f);
        }

        public static Vector2 Top(this AABB aabb)
        {
            return new Vector2(aabb.X, aabb.Y - aabb.Height * 0.5f);
        }

        public static Vector2 Bottom(this AABB aabb)
        {
            return new Vector2(aabb.X, aabb.Y + aabb.Height * 0.5f);
        }

        public static Vector2 Left(this AABB aabb)
        {
            return new Vector2(aabb.X - aabb.Width * 0.5f, aabb.Y);
        }

        public static Vector2 Right(this AABB aabb)
        {
            return new Vector2(aabb.X + aabb.Width * 0.5f, aabb.Y);
        }

        public static AABB ToWorld(this AABB aabb, Vector2 position)
        {
            return new AABB(aabb.X + position.X, aabb.Y + position.Y, aabb.Width, aabb.Height);
        }
    }

}

AABB stands for Axis Aligned Bounding Box, and it's the only kind of collision we need. an AABB is a rectangle that can't be rotated. its sides are always "axis aligned," meaning that the left and right sides are always parallel with the Y axis and the top and bottom are always parallel with the X axis. if you've ever looked into collision detection, you've probably seen algorithms for detecting collision with things like circles, OBBs (Orientable Bounding Boxes), or arbitrary polygons. the truth is, we can approximate all of these other shapes with AABBs, and get a huge boost to both our game's performance and the simplicity of the code. if you want to see the full potential of the axis-aligned bounding box, look no further than just about any fighting game. the hitboxes and hurtboxes in every fighting game you've ever played are made up entirely of axis-aligned bounding boxes.

if it's good enough for street fighter, it's good enough for you.

here, we create a record struct, a fancy new kind of struct in C# that has two benefits: it lets us simplify struct declaration to just one line, and it autogenerates equality-checking code for a big performance boost in some circumstances.

next, we have a static class that holds a bunch of extension functions to get us various properties of our AABB that we'll use later. of particular significance is the ToWorld extension function, which transforms an AABB from the local space of the entity it's attached to to world space.

now, create a new file in Renderers/ called AABBRenderer.cs.

using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using MoonTools.ECS;
using CollisionTutorial.Components.Motion;

namespace CollisionTutorial.Renderers
{
    public class AABBRenderer : MoonTools.ECS.Renderer
    {
        Filter AABBFilter { get; }
        SpriteBatch SpriteBatch { get; }
        Texture2D White1x1 { get; }

        public AABBRenderer(World world, SpriteBatch spriteBatch, Texture2D white1x1) : base(world)
        {
            White1x1 = white1x1;
            SpriteBatch = spriteBatch;
            AABBFilter = FilterBuilder
                .Include<AABB>()
                .Include<Vector2>()
                .Build();
        }
        public void Draw()
        {
            SpriteBatch.Begin();
            foreach (var e in AABBFilter.Entities)
            {
                var box = Get<AABB>(e);
                var pos = Get<Vector2>(e);

                SpriteBatch.Draw(
                    White1x1,
                    new Rectangle(
                        (int)pos.X + (int)box.X - (int)(box.Width * 0.5f),
                        (int)pos.Y + (int)box.Y - (int)(box.Height * 0.5f),
                        (int)box.Width,
                        (int)box.Height
                        ),
                    Has<Color>(e) ? Get<Color>(e) : Color.White
                );

            }
            SpriteBatch.End();
        }
    }
}

very simply: we create a filter that looks for AABBs, and then draw them to the screen. again, this isn't a rendering tutorial, so i won't spend too much time on this. we're using XNA's built-in Vector2 struct to store the position, so we don't have to create a special component struct for that. we have to use XNA's Rectangle struct to draw to the screen, which means subtracting half the width and height to get the graphics to align with the collider.

we're conceptualizing of the AABB position as a sort of offset to the Vector2 position, or if you like the AABB position is specified in the entity's local space. this isn't really relevant now, but if you want to composite multiple AABBs to build more complex colliders like they do in street fighter, this is how you'll want to do it.

finally, we also use XNA's build-in Color struct to tell the renderer what color to draw the rectangle, and draw it white if it has no color.

back in our main Game class, we need to add a reference to the RectangleRenderer:

...
static World World { get; } = new World();
static AABBRenderer? AABBRenderer;

and then initialize our renderer in LoadContent:

...
/*
RENDERERS
*/

AABBRenderer = new AABBRenderer(World, SpriteBatch, white1x1);

and give it something to render:

/*
ENTITIES
*/

var player = World.CreateEntity();
World.Set(player, new Vector2(Window.ClientBounds.Width * 0.5f, Window.ClientBounds.Height * 0.5f));
World.Set(player, new AABB(0, 0, 32, 32));
World.Set(player, Color.Green);

finally, call the RectangleRenderer draw function in Draw():

protected override void Draw(GameTime gameTime)
{
    GraphicsDevice.Clear(Color.Black);

    AABBRenderer.Draw();
    base.Draw(gameTime);
}

you should see something like this:

pt 2: motion

ok, now let's move that rectangle around.

first, we finally need to create some components. create two new files in Components/: Motion.cs and Player.cs.

in Motion.cs, put:

namespace CollisionTutorial.Components.Motion
{
    public readonly record struct Speed(float Value);
}

this will store the speed of our game objects.

in Player.cs put:

namespace CollisionTutorial.Components.Player
{
    public readonly record struct Player();
}

this is just a flag component to tell our systems which object the player is.

we also need to create a message. create a new folder called Messages and put a file in it called Motion.cs:

using Microsoft.Xna.Framework;
using MoonTools.ECS;

namespace CollisionTutorial.Messages.Motion
{
    public readonly record struct Move(Vector2 Velocity, Entity Entity) : IHasEntity;
}

this is going to be the message that gets sent to tell our motion system to move things around.

to move things around, first we need to get player input. create a new file in Systems/ and call it InputSystem.cs:

using System;
using CollisionTutorial.Components.Motion;
using CollisionTutorial.Components.Player;
using CollisionTutorial.Messages.Motion;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Input;
using MoonTools.ECS;

namespace CollisionTutorial.Systems
{
    public class InputSystem : MoonTools.ECS.System
    {
        public InputSystem(World world) : base(world)
        {

        }

        public override void Update(TimeSpan delta)
        {
            var player = GetSingletonEntity<Player>();
            var speed = Has<Speed>(player) ? Get<Speed>(player).Value : 1.0f;
            var state = Keyboard.GetState(0);

            Vector2 dir = Vector2.Zero;

            if (state.IsKeyDown(Keys.Up))
            {
                dir -= Vector2.UnitY;
            }

            if (state.IsKeyDown(Keys.Down))
            {
                dir += Vector2.UnitY;
            }

            if (state.IsKeyDown(Keys.Left))
            {
                dir -= Vector2.UnitX;
            }

            if (state.IsKeyDown(Keys.Right))
            {
                dir += Vector2.UnitX;
            }


            if (dir.LengthSquared() > 0)
            {           
                dir.Normalize();
                Send(new Move(dir * speed, player));
            }
        }
    }
}

we could do something much fancier than this, but this isn't an input handling tutorial. all we're doing is getting the keyboard state and creating a Vector2 for the movement direction based on the status of the arrow keys. after that, we check and see if any keys are being pressed by checking if LengthSquared is more than zero. using LengthSquared instead of Length saves us the here-unnecessary square root, because we don't care about the specific length.

if anyone asks, i did not tell you it was ok to handle input like this.

if a key has been pressed, we have to normalize the dir. if we didn't, then the player would move faster diagonally than orthogonally, and that's no good. then we send our Move message with the appropriate velocity and entity reference. if we try to normalize the dir when a key hasn't been pressed, we'll get a divide by zero error.

now, create another file in Systems/ called MotionSystem.cs:

using System;
using CollisionTutorial.Messages.Motion;
using Microsoft.Xna.Framework;
using MoonTools.ECS;

namespace CollisionTutorial.Systems
{
    public class MotionSystem : MoonTools.ECS.System
    {
        Filter MotionFilter;

        public MotionSystem(World world) : base(world)
        {
            MotionFilter = FilterBuilder
                                .Include<Vector2>()
                                .Build();
        }

        public override void Update(TimeSpan delta)
        {
            foreach (var e in MotionFilter.Entities)
            {
                if (SomeMessageWithEntity<Move>(e))
                {
                    var vel = Vector2.Zero;
                    var msgs = ReadMessagesWithEntity<Move>(e);

                    foreach (var msg in msgs)
                    {
                        vel += msg.Velocity;
                    }

                    var pos = Get<Vector2>(e);
                    Set<Vector2>(e, pos + vel * (float)delta.TotalSeconds);
                }
            }
        }
    }
}

now we have two approaches here and you'll see why we chose this one in a moment. we could iterate over every Move message, or we could iterate over every movable entity and check if there's a Move message referring to it. we've chosen the second one. the benefits of this will become clear shortly. for now, we go over all the movement messages we've received for this entity, add them all together, and then move the position by that amount times DeltaTime1.

now let's pull it all together. add references to the new systems in the main Game class:

...
static AABBRenderer? AABBRenderer;

static InputSystem? InputSystem;
static MotionSystem? MotionSystem;

initialize them in LoadContent:

/*
SYSTEMS
*/

InputSystem = new InputSystem(World);
MotionSystem = new MotionSystem(World);

add our new components to our player:

/*
ENTITIES
*/

var player = World.CreateEntity();
World.Set(player, new Vector2(Window.ClientBounds.Width * 0.5f, Window.ClientBounds.Height * 0.5f));
World.Set(player, new AABB(0, 0, 32, 32));
World.Set(player, new Player());
World.Set(player, new Speed(256.0f));
World.Set(player, Color.Green);

and call our new systems Update methods in the game loop:

protected override void Update(GameTime gameTime)
{
    InputSystem.Update(gameTime.ElapsedGameTime);
    MotionSystem.Update(gameTime.ElapsedGameTime);
    World.FinishUpdate();
    base.Update(gameTime);
}

pt 3: collision

time for the meat of things. we have two problems to tackle to make a collision system, referred to in collision detection as the "broad phase" and the "narrow phase."

the narrow phase is what you might think of when you think of collision detection. you take two shapes, put them into an algorithm, and determine whether they are overlapping and by how much. you then move them apart so they aren't colliding anymore.

the problem is that, while most narrow phase collision algorithms are fast, the growth of how many checks you have to do is n! for n objects in your simulation. this is extremely bad. think about it: for every object in your simulation, you have to check every other object in the simulation for collisions. that is not sustainable even for the most basic collision algorithm. if only there were some way to tell if our objects could conceivably be near each other...

pt 3a: broadphase

enter the collision broadphase. the broadphase invovles putting all your colliders into some kind of data structure that allows you to quickly answer the question "what other colliders are close enough to this one to possibly be colliding?" there are lots of options here: quadtrees (and octrees in the 3d case) are popular, as are k-d trees for certain kinds of level geometry. we are going to be using a spatial hash.

the big advantage of the spatial hash is that it is incredibly simple to implement. all we have to do is divide the game world up into fixed size "cells," and then stick each collider into the cells that its shape crosses. then, to retrieve possible collisions, we go through all the cells the collider we're checking crosses.

here's a graphical example:

in this example, the smaller blue square fits only in one cell, (7, 10) (assuming the bottom left cell is numbered (0, 0)). the larger red square fits in several cells, from (2, 3) to (6, 7). but we can know for sure that these two shapes can't be colliding, because they aren't in any of the same cells. the medium sized yellow square does share some cells with the large red square, so we have to check in the narrow phase to discover that they are collding. and finally, the green square is colliding with the red square, and we know to check it becuase they share several cells.

one important aspect of spatial hashes is you want to tune the cell size correctly. too small, and most objects will be in multiple cells, which means the insertion time will go up. too large, and most cells will contain too many objects, making the narrow phase collision checking slower. the sweet spot is usually somewhere around twice as large as a typical object in your game.

you can stick your spatial hash implementation in its own class; for the sake of simplicity i'm just going to put all of our collision code in MotionSystem. first, we ned some new variables:

Filter MotionFilter;
Filter AABBFilter;
int CellSize;
float CellReciprocal;
public Dictionary<long, HashSet<Entity>> SpatialHash;

and to initialize them in the constructor:

public MotionSystem(World world, int cellSize, float sweepStep) : base(world)
{
    MotionFilter = FilterBuilder
                        .Include<Vector2>()
                        .Build();

    AABBFilter = FilterBuilder
                    .Include<Vector2>()
                    .Include<AABB>()
                    .Build();

    CellSize = cellSize;
    CellReciprocal = 1.0f / CellSize;
    SpatialHash = new Dictionary<long, HashSet<Entity>>();
}

CellSize is, as you can probably guess, the size of the spatial hash cells. CellReciprocal is the reciprocal of the cell size, which we use becuase multiplying by the reciprocal is equivalent to but faster than dividing by cell size. SpatialHash is where we're going to store our entities for fast retrieval. our keys are long integers, and our values are a HashSet of entities, which will let us insert the same entity multiple times without it getting duplicated.

now we need some helper functions for calculating the hash. first:

(int, int) Hash(Vector2 position)
{
    return ((int)Math.Floor(position.X * CellReciprocal), (int)Math.Floor(position.Y * CellReciprocal));
}

this will convert a Vector2 position into its SpatialHash cell coordinates. so every X less than 64 will become 0, every X greater than 64 but less than 128 will become 1, every X greater than 128 but less than 192 will become 2, and so on; same for Y. next:

long GetHashKey(float x, float y)
{
    long ux = (int)MathF.Floor(x * CellReciprocal);
    long uy = (int)MathF.Floor(y * CellReciprocal);
    return (ux << 32) & uy;
}

now we convert those hash cell coordinates into a single hash key that will be unique for each coordinate pair using the bitwise left shift and AND operators. how this works isn't exactly important. if you want to know more, consult the docs. the important thing is that this will map each pair of x, y coordinates to a unique single number, which is easier and faster to compare.

now we need functions to add to and retrieve from the spatial hash. first, adding:

void SpatialHashAdd(Entity e)
{
    if (Has<AABB>(e) && Has<Vector2>(e))
    {
        var pos = Get<Vector2>(e);
        var rect = Get<AABB>(e).ToWorld(pos);

        var minHash = Hash(rect.Min());
        var maxHash = Hash(rect.Max());

        for (int x = minHash.Item1; x <= maxHash.Item1; x++)
        {
            for (int y = minHash.Item2; y <= maxHash.Item2; y++)
            {
                var key = GetHashKey(x, y);
                if (!SpatialHash.ContainsKey(key))
                {
                    SpatialHash.Add(key, new HashSet<Entity>());
                }

                SpatialHash[key].Add(e);
            }
        }
    }
}

this takes an entity and first makes sure that it has the correct components to be assigned a spatial hash key. then we use the position of the entity to transform the AABB to world space for insertion into the hash.

we use that hash bucketing function to get the minimum and maxmimum hash coordinates, and then go through them in a double for loop to insert the object into every bucket it crosses.

retrieval is very similar:

IEnumerable<Entity> SpatialHashRetrieve(AABB aabb)
{
    var minHash = Hash(aabb.Min());
    var maxHash = Hash(aabb.Max());

    for (int x = minHash.Item1; x <= maxHash.Item1; x++)
    {
        for (int y = minHash.Item2; y <= maxHash.Item2; y++)
        {
            var key = GetHashKey(x, y);
            if (SpatialHash.ContainsKey(key))
            {
                foreach (var e in SpatialHash[key])
                {
                    yield return e;
                }
            }
        }
    }
}

we do the same hash buckets double for loop thing, but now instead of adding to the hash, we get all of the entities that are in the hash with that key and yield return them one by one.

part 3b: narrow phase

we can't really test our our spatial hash without a narrow phase to resolve possible collisions, so let's write that.

if you've done any collision math before, you probably know of a very simple way to check if two rectangles are overlapping:

if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
     RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top ) 

this is good and very fast, but we need more. we don't just want to know if the shapes are overlapping, we also want to know by how much, so we can correct it. this "how much" is called the penetration vector. there are several ways to calculate it, but one of the fastest and most straightforward is to get the minkowski difference.

the minkowski difference is a big complicated subject. essentially, it is the shape you get when you subtract all the vertices of one shape from the vertices of another.

the minkowski difference is significant to us because of a key fact: if the minkowski difference of two shapes contains the origin, the shapes are overlapping. this fact is at the center of one of the most famous collision detection algorithms, GJK.

the minkowski difference is expensive to calculate for arbitrary polygons. a huge part of GJK is coming up with clever ways to compute successive approximations to the minkowski difference, so as not to waste resources computing the full difference for shapes that aren't good collision candidates. fortunately, we have a shortcut.

computing the minkowski difference is hard for arbitrary polygons. for AABBs, there's an extremely easy shortcut:

AABB MinkowskiDifference(AABB a, AABB b)
{
    var mdLeft = a.Left() - b.Right();
    var mdTop = a.Top() - b.Bottom();
    var mdWidth = a.Width + b.Width;
    var mdHeight = a.Height + b.Height;

    var mdX = mdLeft.X + mdWidth * 0.5f;
    var mdY = mdTop.Y + mdHeight * 0.5f;

    return new AABB(mdX, mdY, mdWidth, mdHeight);
}

yeah, that's it. nothing fancy, just simple addition, subtraction, and multiplcation of vectors. we can figure out if two shapes are overlapping from this with similar simplicity:

(Vector2 v, bool overlaps) Overlaps(AABB a, AABB b)
{
    var md = MinkowskiDifference(a, b);
    var min = md.Min();
    var max = md.Max();

    if (min.X <= 0 && max.X >= 0 &&
        min.Y <= 0 && max.Y >= 0)
    {
        return (PenetrationVector(md), true);
    }

    return (Vector2.Zero, false);
}

yep, just four inequalities and we have the answer. logically, if the minimum and maximum of a shape are less than and greater than zero respectively, then zero must be somewhere between them. to calculate our penetration vector, we need to do a little more work:

Vector2 PenetrationVector(AABB md)
{
    var min = md.Min();
    var max = md.Max();

    var minDist = MathF.Abs(min.X);
    var boundsPoint = new Vector2(min.X, 0);

    if (MathF.Abs(max.X) < minDist)
    {
        minDist = MathF.Abs(max.X);
        boundsPoint.X = max.X;
    }

    if (MathF.Abs(max.Y) < minDist)
    {
        minDist = MathF.Abs(max.Y);
        boundsPoint.X = 0;
        boundsPoint.Y = max.Y;
    }

    if (MathF.Abs(min.Y) < minDist)
    {
        boundsPoint.X = 0;
        boundsPoint.Y = min.Y;
    }

    return boundsPoint;
}

we need to figure out which point on the surface of our shape is closest to the origin. because our shape is a rectangle, this can be done with three inequalities. first, we assume that the left side of our shape is closest to the origin. then we check and see if the right side is actually closer, then we check the bottom side, then we check the top side. whichever one is closest will be in boundsPoint at the end.

there's just one more thing we need before we can put this to use. your first idea might be to just move an object to its destination point, and then check to see if it's colliding, and then correct its position if necessary. this will work in some situations, but it has a problem: what if the moving object has a velocity high enough that its destination point is on the other side of a wall? if that happens, it'll just pass right through.

now, in the world of floating point, we can't really check every single in between step practically. instead, we're just going to check every 1 world unit. since 1 world unit = 1 pixel, our game can't even render objects smaller than that, so this is fine for preventing quantum tunelling shenanigans.

doing this kind of thing where you move the object through space and check every step in between is called a "sweep test." this is probably the most complex method we have to write, so let's break it down:

(Vector2 hitPosition, bool hit, HashSet<Entity> hitEntities) SweepTest(Entity e, Vector2 velocity)
{
    var aabb = Get<AABB>(e);
    var pos = Get<Vector2>(e);

    var results = (pos, false, new HashSet<Entity>());

    var totalDist = velocity.Length();
    var distance = 0.0f;
    var step = velocity;
    step.Normalize();

our method takes an entity and its velocity, and returns its final adjusted position, whether it hit anything, and all the entities it hit.

first, we initialize a default results tuple. next, we initialize our starting variables. totalDist is the total distance we have to travel. distance is how far we've traveled. step is our vector step, which is going to just be a normalized vector in the direction of our velocity.

now, let's sweep:

while (distance < MathF.Ceiling(totalDist))
{
    results.Item1 += step;
    results.Item1 = Vector2.Clamp(results.Item1, Vector2.Min(pos, pos + velocity), Vector2.Max(pos, pos + velocity));
    var a = aabb.ToWorld(results.Item1);

    var entities = SpatialHashRetrieve(aabb.ToWorld(results.Item1));

    foreach (var other in entities)
    {
        var otherAABB = Get<AABB>(other);
        var otherPos = Get<Vector2>(other);

        if (other != e)
        {
            var b = otherAABB.ToWorld(otherPos);
            var o = Overlaps(a, b);

            if (o.overlaps)
            {
                results.Item2 = true;
                results.Item3.Add(other);
                results.Item1 -= o.Item1;
            }
        }
    }

    distance++;
}

first: we're going up in steps of length 1, so we need to round up our total distance to make sure we actually travel any fractional distances. we then move our tentative position (stored in Item1 of results) by step. we have to clamp our travel distance so we don't move further than our velocity because of the rounding.

then, we get a transformed AABB for our tentative position and use it to retrieve all the entities we might collide with.

we iterate over all those entities, checking to make sure we don't check and see if an entity is colliding with itself. we transform the other entity's AABB into world space, and then check if they're overlapping. if they are, we adjust the resulting position by the penetration vector (results.Item1 -= o.Item1), mark "hit" as true, and add the entity we hit to the list of hit entities.

we then increment the distance and repeat, and finally return the results:

        distance++;
    }

    return results;
}

now, let's bring it all together in Update:

public override void Update(TimeSpan delta)
{
    SpatialHash.Clear();

    foreach (var e in AABBFilter.Entities)
    {
        SpatialHashAdd(e);
    }

    foreach (var e in MotionFilter.Entities)
    {
        if (SomeMessageWithEntity<Move>(e))
        {
            var vel = Vector2.Zero;
            var msgs = ReadMessagesWithEntity<Move>(e);

            foreach (var msg in msgs)
            {
                vel += msg.Velocity;
            }

            var pos = Get<Vector2>(e);

            if (!Has<AABB>(e))
            {
                Set(e, pos + vel * (float)delta.TotalSeconds);
            }
            else
            {
                var velX = new Vector2(vel.X, 0) * (float)delta.TotalSeconds;
                var velY = new Vector2(0, vel.Y) * (float)delta.TotalSeconds;
                var sweepX = SweepTest(e, velX);
                var sweepY = SweepTest(e, velY);
                var finalPos = new Vector2(sweepX.position.X, sweepY.position.Y);
                Set(e, finalPos);
            }
        }
    }
}

at the start of every frame, we have to clear the spatial hash and re-populate it using our new AABBFilter. then we iterate over the MotionFilter like before and sum up all the velocities.

here's where it's different: if our object doesn't have a collider (which describes no objects in this example, but it's good to have options), we just move it without checking collision. if it does, we have to check.

we split the velocity into separate X and Y components. this is to allow the player to still move along walls while holding a direction that is pushing them into the wall. if we just sweep tested the velocity vector directly, then pushing into a wall would cause you to stop moving entirely until you released the direction that the wall was in. this might be what you want sometimes, but it usually isn't.

then, we sweep our velocities, and adjust our position to the new final position. we take the X component of the X velocity sweep and the Y component of the Y velocity sweep.

finally, we can see some collision:

pt 4: improvements

there are two big problems with this implementation. i added some more behavior to show a moving object, how i did this is left as an exercise for the reader. as you can see, the collision behavior between two moving objects is not exactly correct. this may be fine for you, depending on what kind of game you're making. in many games, the only moving objects besides the player are collectibles and enemies, and so you may not have to worry about what happens when they touch each other: the player will either pick them up, or get i-frames that let them pass though the enemy. solving this issue is beyond the scope of this tutorial, becuase it really depends on exactly what you want. one possible approach is to create a component to store every entity's momentum vector, and add that to their total movement vector each frame. you can adjust it whenever two objects collide based on their relative masses and momenta and newton's second and third laws.

the second is an even more minor issue. see, our AABBs and positions using floating point coordinates. in a game with 3d or vector graphics, this would be fine. in a game with raster graphics however, especially low-resolution pixel art ones, we generally want to store coordinates as integers to prevent strange behavior. this isn't as straightforward as just creating a vector struct that uses integers instead of floats, however. we want to keep that subpixel data, we just want to have more control over how it gets used. for an example of this, check out this position2D struct by evan hemsley, the developer of moontools.ecs.

finally, you may wonder how to handle collision events, like taking damage or collecting powerups. we already have everything we need! sweepX and sweepY contain every entity that was hit by our entity this frame.

you could create a CanTakeDamage component and a CanDamage component, check and see if entity A in the collision has CanDamage and entity B has CanTakeDamage, and send a message with those two entities off to a DamageSystem to deal the damage (perhaps by subtracting health from a HealthSystem) and resolve any consequences (like death). having CanTakeDamage as a separate component from a Health component has the big advantage of letting you easily implement something like i-frames by just removing the CanTakeDamage component and re-adding it again later.

pt 5: conclusion

i hope you found this useful. collision is something that i found really intimidating when i got started making games, but as i learned more about it it stopped being so scary.

in the future, i plan to publish a full game tutorial making use of many of the techniques i talked about here, to show you how to best implement all the various moving parts that go into making a game.


1: we could be using a better timestep as outlined in this classic blog post. in many contexts, espeically single-player games, having the best possible timestep that gaffer describes is not necessarily worth the hassle.