Game graphics scaling

In game I would like every player to have more or less the same game experience. And, most importantly, I want players to have the same chance of winning, and not limiting players’ skills based on their devices etc. One of the things that need to be handled is visible game arena size. Ideally players with ultra HD screens and players with smaller laptop screens with 1600 over 900 for example should all see the same part of game arena, to not make players on bigger screens have it easier to spot enemies. This means there needs to be standard game size defined. But that would mean that some players would have only part of their screen space used for game, while others would have to scroll to see whole content – that makes terrible user experience. Scaling should solve the problem!

OK, first things first. I have to define base game arena size to server as reference. On screen with this resolution scaling factor should be equal to one. This could possibly be any set of two numbers (width and height), not corresponding to any particular screen size, but I’ve decided to base it on my full hd screen, or to be more precise, on my canvas size on Raim page – 1600 over 861 (with some space being taken over by address bar, developer tools, icons etc.).

var originalSize = { x: 1600, y: 861 };
var scale = 1;

Then, it is time to scale canvas on page when size of browser changes, so that resizing window will cause scale to change.

var resizeCanvas = function () {
    var arenaElement = document.getElementById(arenaHandler);
    var widthDiff = originalSize.x - arenaElement.offsetWidth;
    var heightDiff = originalSize.y - arenaElement.offsetHeight;

    var aspectRatio = originalSize.x / originalSize.y;
    var w, h;

    if (Math.abs(widthDiff) > Math.abs(heightDiff)) {
        w = arenaElement.offsetWidth;
        h = w / aspectRatio;
    } else {
        h = arenaElement.offsetHeight;
        w = h * aspectRatio;
    }

    canvas.width = w;
    canvas.height = h;

    scale = canvas.width / originalSize.x;
};

(function init() {
    ...

    var arenaElement = document.getElementById(arenaHandler);
    viewport.x = 0;
    viewport.y = arenaElement.offsetHeight;

    canvas = document.createElement("canvas");
    document.getElementById(arenaHandler).appendChild(canvas);
    resizeCanvas();

    window.addEventListener('resize', resizeCanvas);

    gfx = new raimGraphics({
        canvas: function () { return canvas; },
        viewport: function () { return viewport; },
        arena: function () { return arena; },
        scale: function () { return scale; }
    });

    ...
})();

Calculating the scale is not too hard. There is aspect ratio I want to hold (calculated as width divided by height). Given that, if I have new screen width, I can calculate screen height by dividing width by this ascpect ratio. Holding aspect ratio will ensure that graphics don’t get distorted in any axis (e.g. circles do not turn into elipses). The calculation formula is simply taken from proportion:

newWidth / newHeight = originalWidth / originalHeight
newHeight = newWidth / (originalWidth / originalHeight)

With new scale calculated, drawing graphics is as simple as multiplying every coordinate by this scale, for example:

...
x = player.Position.X + args.viewport().x;
y = player.Position.Y + args.viewport().y;
drawingContext.arc(x * scale, -y * scale, player.Size * scale, 0, 2 * Math.PI);

...

var x = points[0].X + args.viewport().x;
var y = -(points[0].Y + args.viewport().y);
drawingContext.moveTo(x * scale, y * scale);
for (var i = 1; i < points.length; i++) {
    x = points[i].X + args.viewport().x;
    y = -(points[i].Y + args.viewport().y);
    drawingContext.lineTo(x * scale, y * scale);
}

x = points[0].X + args.viewport().x;
y = -(points[0].Y + args.viewport().y);
drawingContext.lineTo(x * scale, y * scale);

Easy! Is that it? Well, no. There is also user input to be taken into account – mouse movement and mouse clicks are used in application and game required coordinates to be handled in game world coordinates, not screen coordinates. So what needs to happen is – mouse coordinates have to be scaled accordingly. Does this mean multiplying by game scale?
No. Since I’ve stretched game twice (for player with big screen) and user clicks in coordinate [10, 10] on the screen, it must be [5, 5] coordinate in game world (remember – game world got stretched two times). It makes sense – if I put stuff onto the screen, I multiply it by scale. If I get it from back the screen, I have to devede the value back by reversing the operations.

var inputChange = function (input) {
    var player = getCurrentPlayer();
    if (player == undefined) return;

    input.mouse.x /= scale;
    input.mouse.y /= scale;
    input.mouse.x = input.mouse.x - viewport.x;
    input.mouse.y = -input.mouse.y - viewport.y;
    ...
}

And just one more fix – in my calculations of viewport I was taking canvas size into account. Since canvas account is no longer a real game world size, I cannot take it into account. But thankfully there is game world size already there – originalSize, so that makes viewport calculation really easy:

viewport.x = originalSize.x / 2 - currentPlayer.Position.X;
viewport.y = -originalSize.y / 2 - currentPlayer.Position.Y;

And now game scales on every window sizes!

Case of player uncertainity, or about double comparison

If anyone tried my code for collision detection, he or she might have noticed that it sometimes behaves unexpectedly. For example object seems to go inside the colliding object, just to be ejected in next frame or two. Quickly, but slowly enough to be noticable glitch, and in case of corners to cause object to skip to the other side. Not good!

Turns out there are two problems. First – When messing around with border of my game arena, I defined for walls. But I did that incorrectly. My algorith depends on polygons to have points defined in clockwise manner. So for example first lower left corner, then upper left, upper right, and finally lower right. When done differently it messes things up for some sides of polygon as the normal axis does not point outside of the polygon – which is needed for collisions to be resolved correctly, moving player outside of polygon.

Second error was more hidden. Took me almost two hours to figure out what is going on. Since player was just going a little bit inside the object and then was correctly resolved (to the correct side of obstacle), I thought that collision code must be OK, and maybe somehow I’m skipping collision detection, or maybe two frames are rendered at the same time, applying double movement to the object, temporarily putting it inside obstacle?

Turns out issue was way simpler. I’ve messed up something that every developer on earth should know by the time he or she writes first application in highshool. And definitely before taking first money for their code. Double comparison. When comparing doubles you can never skip epsilon. If you do, you gonna find yourself figuring out why sometime, for some sides of polygon, collision detection does not work. Or why you suddenly get infinity printed out on the screen during client demo. Been there, done that. This year. Yea, I suck.

Check this code:

var intersectionRange = obstacleProjection.Intersect(objectProjection);
intersectionRange = intersectionRange.Add(axisVector.Item2);

if (intersectionRange.Length < 0.0001)
    return null;

if (intersectionRange.Length < smallestDisplacement.Item2.Length || // new collision is smaller
    (Math.Abs(intersectionRange.Length - smallestDisplacement.Item2.Length) < 0.0001 && // or collision sizes are the same
     Math.Abs(intersectionRange.Start) < Math.Abs(smallestDisplacement.Item2.Start)))    // but collision is closer to polygon side
{
    smallestDisplacement = Tuple.Create(axisVector.Item1, intersectionRange);
}

It does exactly what is needed, right? If new collision is smaller, it needs to be picked as smallest displacement. If not, we check additional stuff. Worked perfectly for the single test polygon I used for my testing. I even picked one that is not aligned with X and Y axes to make sure everything works exactly as it should!

So what is the problem? Sometimes, when conditions are just right, doubles get a little bit unprecise. And then all hell breaks loose. Imagine if two axes are parallel, like in rectangle top and bottom sides, collision displacement counting from 0 axis would be exactly the same, just axis will be different (one pointing down, for bottom axis, and other pointing up, for top axis). So when collision happens form the bottom and bottom side was checked first, it puts smalles displacement. And I go to check other sides, including top one. Displacement is the same there, just for different axis. And if it would be the same – all would be fine. But if double missies precision in calculations and return slightly lower value (say, 2.5118300001 versus 2.5118299991) algorithm decides that it has found new smallest collision side!

Fix is simple, add epsilon value:

var intersectionRange = obstacleProjection.Intersect(objectProjection);
intersectionRange = intersectionRange.Add(axisVector.Item2);

if (intersectionRange.Length < 0.0001)
    return null;

if (intersectionRange.Length < smallestDisplacement.Item2.Length - 0.0001 || // new collision is smaller
    (Math.Abs(intersectionRange.Length - smallestDisplacement.Item2.Length) < 0.0001 && // or collision sizes are the same
     Math.Abs(intersectionRange.Start) < Math.Abs(smallestDisplacement.Item2.Start)))    // but collision is closer to polygon side
{
    smallestDisplacement = Tuple.Create(axisVector.Item1, intersectionRange);
}

Even if there is double error in calculations, small epsilon will make sure that it will not get interpreted as smaller collision size. And what if it actually is better collision? Second part takes care of it, checking if collision is roughly the same size (again, using epsilon) and it is closer to the side.

Uff, problem solved! Never again doing this error. Or, well, hopefully not this month.

DajSiePoznac summary

Daj Sie Poznac summary

With May coming to an end, it is time to summarize DajSiePoznac competition.

First, few numbers:

Views: 1156
Visitors: 891
Posts: 36
Commits: 138

Thanks everyone for visiting!

Second, project progress. It has been good. I’ve done a lot, more than I thought I will manage, between work, private life and everything. 36 posts, 138 commits. And With those commits came some code. Moving objects around, drawing stuff in javascript, calculating collisions in couple of ways, reacting precisely to those collisions. And synchronising everything between multiple players on simple html web page with SignalR. Not exactly ground breaking, but gave me a lot of fun and helped me produce working prototype that will be further extended.

With all of that, I hope I did well. Cheers!

Obstacle collisons pt. 5, Solving collisions

Having info that there is collision between two objects there is nothing more left but solving the collision. What I want to do is to move object away so that there is no longer a collision, and to do this by doing as little movement of objects as possible. So Rather than having info that collision happened, I need to have info what kind of collision happened – in what axis objects collided and how much of objects are colliding. This is exactly the same thing I did in circle-circle collision, just way more generic case.

High level implementation should do something like this: find collision displacement (axis and collision size) and move object along this axis (it should point out of the object) by the size of collision – this will put game object outside of obstacle boundaries.

private void CalculateCollisions(IGameObject o1)
{
    foreach (var obstacle in Obstacles)
    {
        var collisionDisplacement = ObstacleCollide(obstacle, o1);
        if (collisionDisplacement != null)
        {
            // Item1 - axis unit vector, Item2 collision size
            var collisionFix = collisionDisplacement.Item1.Scale(collisionDisplacement.Item2);
            o1.Position = o1.Position.Add(collisionFix);
        }
    }
}

This means I have to update my collision detection code. I am storing smallest collision values in variable and updating it whenever I find collision with smaller size then previously found. Still in case of finding out that there is no collision, code quits quickly and returns null.

private Tuple<Vector2d, double> ObstacleCollide(Obstacle obstacle, IGameObject gameObject)
{
    var smallestDisplacement = Tuple.Create(new Vector2d(0, 0), new Range(double.MinValue, double.MaxValue));

    foreach (var axisVector in GetAxisVectors(obstacle, gameObject))
    {
        var obstacleProjection = ProjectOntoAxis(axisVector, obstacle);
        var objectProjection = ProjectOntoAxis(axisVector, gameObject);

        var intersectionRange = obstacleProjection.Intersect(objectProjection);

        if (intersectionRange.Length < 0.0001)
            return null;

        if (intersectionRange.Length < smallestDisplacement.Item2.Length)
            smallestDisplacement = Tuple.Create(axisVector, intersectionRange);
    }

    return Tuple.Create(smallestDisplacement.Item1, smallestDisplacement.Item2.Length);
}

That should be it. And, to my surprise, it works. Well, at least it works for some sides of the object. Those that are most to the left and top. Why is that? Well, this obstacle I’m testing my code with is rectangle. This means there are parallel sides which in turn share the same normal axis (just with different sign, so on may point upward, while the second one will point downward). When creating axis vector it is converted into unit vector and this means it starts in point (0, 0). That is OK for detecting collisions, but since those axes may differ only in sign, it means that intersection size will be the same for both of them! True – ranges themlseves will be different, but length of intersection, used to verify if collison is smaller or larger at this axis, will be the same so the code will find first axis with collision (for example the top one), record that it has collision size for example 1 and then move to the right and finally bottom side (I’m building my polygons so that points are ordered clockwise). But since bottom side also has collison size of 1 collision axis will not get updated even though player comes from the bottom side of the rectangle. This means algorithm will try to push player to the top a little bit, actually pushing player inside obstacle, not outside! And this will repeat for every frame until object is ejected either from top of rectangle or from the sides (left side to be precise) if rectangle happens to be higher than wider.

This cannot stay that way. So to fix this I had to figure out where the mistake is. And after a while I got it – I cannot look just at the size of collision, but rather at distance of collision from beginning of obstacle’s side. Or, to put it in other words, I have to adjust intersection range by how far the side is, not keep it from axis origin (point 0, 0). How far is side form axes origin? Well, it is exactly axis dotProduct sideOriginPoint away!

Little update to my axis generator. Now it returns axis and numeric value saying how far polygon side is form 0,0 point. And this is how much I have to move my intersection region.

private IEnumerable<Tuple<Vector2d, double>> GetAxisVectors(Obstacle obstacle, IGameObject gameObject)
{
    var prevPoint = obstacle.Points[0];

    for (int i = 1; i <= obstacle.Points.Length; i++)
    {
        var currentPoint = obstacle.Points[i % obstacle.Points.Length];
        var sideVector = currentPoint.Subtract(prevPoint);
        var axisVector = sideVector.Unit().Normal();
        var displacementFromOrigin = axisVector.DotProduct(prevPoint);
        yield return Tuple.Create(axisVector, -displacementFromOrigin);
        prevPoint = currentPoint;
    }

    for (int i = 0; i < obstacle.Points.Length; i++)
    {
        var circleToPointVector = gameObject.Position.Subtract(obstacle.Points[i]).Unit();
        var displacementFromOrigin = circleToPointVector.DotProduct(obstacle.Points[i]);
        yield return Tuple.Create(circleToPointVector, -displacementFromOrigin);
    }
}

And finally adding logic to find smallest collision size possible, and in case sizes are the same, to find the one closer to the origin of the side (closer to the side itself):

private Tuple<Vector2d, double> ObstacleCollide(Obstacle obstacle, IGameObject gameObject)
{
    var smallestDisplacement = Tuple.Create(new Vector2d(0, 0), new Range(double.MinValue, double.MaxValue));

    foreach (var axisVector in GetAxisVectors(obstacle, gameObject))
    {
        var obstacleProjection = ProjectOntoAxis(axisVector.Item1, obstacle);
        var objectProjection = ProjectOntoAxis(axisVector.Item1, gameObject);

        var intersectionRange = obstacleProjection.Intersect(objectProjection);
        intersectionRange = intersectionRange.Add(axisVector.Item2);

        if (intersectionRange.Length < 0.0001)
            return null;

        if (intersectionRange.Length < smallestDisplacement.Item2.Length ||
            (Math.Abs(intersectionRange.Length - smallestDisplacement.Item2.Length) < 0.0001 && Math.Abs(intersectionRange.Start) < Math.Abs(smallestDisplacement.Item2.Start)))
            smallestDisplacement = Tuple.Create(axisVector.Item1, intersectionRange);
    }

    return Tuple.Create(smallestDisplacement.Item1, smallestDisplacement.Item2.Length);
}

The if condition seems bit large, but it is pretty simple: if collision size is smaller than the smallest one found until now – we have new smallest collison. But if it happenes to be the same (comparing doubles with small tolerance) – check if new collision intersection happens to be closer to axis origin, and if so – update smallest collision.

And now it works for all sides of the rectangle, never letting player inside obstacle.

circle to corner collision

Obstacle Collision pt 4 SAT corner cases

Last part finished with Separate Axis Theorem implemented for collisions between polygon and circle, with one exception left: when circle is next to one of the corners of polygon, it may produce false collisions.

False collision with SAT

False collision with SAT

To fix this there is only one way – check more axes. After all there has to be one that gives some distance between objects’ projections, if theory is correct. I’ve checked all reasonable axes form polygon object, but none of the potential axes of the circle. Problem is – circles, being as cools as they are, have infinite corners, so checking every axis based on “sides” of circle, so to say, is time consuming. But – we can get more clever than that! The circle is not colliding with polygon if there is space between circle and polygon sides (that was checked by polygon axes) and if every corner of polygon is outside of circle. Hmm, how about I check every corner’s position? That would do, but that wouldn’t be SAT to be precise. But What if I checked every axis build between circle’s center point and polygon corner? Well, there would certainly have to be some space if there is no collision!

circle to corner collision

circle to corner collision

What about the code? The difference is impressively small!

private bool ObstacleCollide(Obstacle obstacle, IGameObject gameObject)
{
    var prevPoint = obstacle.Points[0];

    foreach (var axisVector in GetAxisVectors(obstacle, gameObject))
    {
        var obstacleProjection = ProjectOntoAxis(axisVector, obstacle);
        var objectProjection = ProjectOntoAxis(axisVector, gameObject);

        var intersectionRange = obstacleProjection.Intersect(objectProjection);

        if (intersectionRange.Length < 0.0001)
            return false;
    }

    return true;
}

private IEnumerable<Vector2d> GetAxisVectors(Obstacle obstacle, IGameObject gameObject)
{
    var prevPoint = obstacle.Points[0];

    for (int i = 1; i < obstacle.Points.Length; i++)
    {
        var currentPoint = obstacle.Points[i];
        var sideVector = currentPoint.Subtract(prevPoint);
        yield return sideVector.Unit().Normal();
    }

    for (int i = 0; i < obstacle.Points.Length; i++)
    {
        var circleToPointVector = gameObject.Position.Subtract(obstacle.Points[i]);
        yield return circleToPointVector.Unit();
    }
}

So what I did is moved the axes extraction to separate method. In main method I can now just iterate over all possible axes that are returned from specialized piece of code that knows exactly what axes I have to check. In this method I first return all the usual cases for polygon sides, and later on, if all polygon axes reported collision, I build axes between every corner of polygon and circle center. Notice that there is no normalisation step involved in here – axis produced this way is already oriented correctly and will be perpendicular to posisbly separating line between two objects, like I want.

One possible optimisation here would be to just check one corner – the closes one to the circle. If this corner reports no collision – we’re good to go. If it reports collision, it must be because it lies inside the circle so the collision is definite and there is no point in checking other corners.

So there it is. SAT implemented. But system does not react to obstacle collisions at all. I will know what to do about this by the time I write next post, I hope!

Newton's cradle

Obstacle collisions pt 3 SAT implementation

In previous I’ve introduced the idea of separating axis theorem and how it is useful to find out if two objects collide. Today I will show the code, the interesting bits. You will be surprised how easy and neat it looks!

First high level – go through all obstacles and check with which my game object collides.

private void CalculateCollisions(IGameObject o1)
{
    foreach (var obstacle in Obstacles)
    {
        if (ObstacleCollide(obstacle, o1))
        {
            // handle collision
        }
    }
}

Then, for each object, check every possible side of obstacle and see if there is an intersection between obstacle projection onto normal axis for this side, and game object projection to onto tis axis. As you can see, my object representation is list of points, not sides, so I have to build side vector. Obvious optimization would be to just hold objects’s sides, not points, but points are good for now. Also see, that if there is any axis found where there is no intersection (common range of projections is less than small number I picked; remember those are doubles and hence may not always get precise values in decimal system we are used to so never compare two doubles by simple == if you want to avoid bugs) I escape collision checking at once – since there is an axis that objects do not have overlapping projections there is no collision happening for sure and I can save few microseconds by not checking remaining sides.

private bool ObstacleCollide(Obstacle obstacle, IGameObject gameObject)
{
    var prevPoint = obstacle.Points[0];

    for (int i = 1; i < obstacle.Points.Length; i++)
    {
        var currentPoint = obstacle.Points[i];
        var sideVector = currentPoint.Subtract(prevPoint);
        var axisVector = sideVector.Unit().Normal();

        var obstacleProjection = ProjectOntoAxis(axisVector, obstacle);
        var objectProjection = ProjectOntoAxis(axisVector, gameObject);

        var intersectionRange = obstacleProjection.Intersect(objectProjection);

        if (intersectionRange.Length < 0.0001)
            return false;
    }

    return true;
}

All operations above should be pretty self explanatory, except maybe for building normal vector (call to Normal() method in line 9). Normal vector is vector that is at 90 degrees to current vector. In 2D there are of course two such vectors (if original vector goes straight up, normal vectors would be one pointing to left and one pointing to right). How is this vector obtained? Extremely simple – it is just a vector with swapped X and Y coordinate, and one of those coordinates multiplied by -1 (which one will be multiplied determines if it will be left or right normal vector). Imagine vector [0, 1]. If you will swap coordinates, you will get [1, 0]. If you will multiply X by -1, you will get left normal vector [-1, 0]; if you will multiply Y you will get right normal vector [1, 0] (the same as vector just after swap, but that’s just because it is 0 coordinate, usually that won’t be the case).

public Vector2d Normal()
{
    return new Vector2d(Y, -X);
}

For SAT calculations, does it matter which one we will pick? For the moment – no. The difference will be – will the normal vector point inside or outside of the object. But that does not matter for collision verification, instead of positive numbers on axis I may get negative ones, but is still valid math, thank you very much :)

OK, next thing on the list is doing projections of object onto given axis. Visually – easy. Mathematically? Well… easy-if-not-easier! From high school math, vectors, remember dot product operation? For vectors A[X, Y] and B[X, Y], dot product is defined as AX * BX + AY * BY. How does that help? Turns out (thanks to some clever math) that this scalar value is equal to length of vector B projected onto vector A. Yea, that’s what I need. Since I have my object hold all points as vectors (which could be interpreted as vector from 0,0 coordinate to object’s vertex) I can project it onto axis vector and get distance from beginning of the axis. If done for all points in object, and recorded minimum and maximum value, the result would be set of two numbers that define from where to where objects projection goes.

private Range ProjectOntoAxis(Vector2d axisVector, Obstacle obstacle)
{
    double min = double.MaxValue;
    double max = double.MinValue;

    for (int i = 0; i < obstacle.Points.Length; i++)
    {
        var currentPoint = obstacle.Points[i];

        var projectionSize = axisVector.DotProduct(currentPoint);
        if (projectionSize < min)
            min = projectionSize;
        if (projectionSize > max)
            max = projectionSize;
    }

    return new Range(min, max);
}

Why do I return numbers as Ranges? To encapsulate some operations inside of it. Remember the line that calculates intersection of two ranges from two objects? It is neatly hidden behind Range abstraction.

public class Range
{
    public double Start { get; set; }
    public double End { get; set; }
    public double Length { get { return End - Start; } }

    public Range(double a, double b)
    {
        Start = a < b ? a : b;
        End = a < b ? b : a;
    }

    public Range Intersect(Range other)
    {
        var firstRange = Start < other.Start ? this : other;
        var secondRange = firstRange == this ? other : this;

        if (firstRange.End < secondRange.Start)
            return new Range(0, 0);

        return new Range(secondRange.Start, firstRange.End);
    }
}

Intersection is simply calculated by taking minimum value of range further to left on axis, and maximum value is end of range closer to the right end of axis. Unless of course those ranges are separated, in which case empty range is returned. Don’t believe me? Draw it on a piece of paper and you will see that it works.

And that’s it, right? We have projections, intersections, all done using very basic math on vectors. Collisions should be detected perfectly, right? Well, not so fast. One of the object is convex polygon, true, but the other is circle. Since iterating over all vertices of circle would take a while (like an infinite while), there must be a better way right?

Fortunately circles are extremely nice creatures and pure joy to work with. They always have the same size in any way you look at them (2 * cirle radius). So calculating projections will also be simple. If I was only interested in size it would just be one multiplication. But I need to have circle’s position in normal axis as well. The only point in circle that I know where is, is circle’s origin point, right there in the middle. Projecting it onto axis (again, dot product) gives center projection. From there add and subtract size once and there it is, projection done like a champ.

private Range ProjectOntoAxis(Vector2d axisVector, IGameObject gameObject)
{
    var centerProjection = axisVector.DotProduct(gameObject.Position);
    return new Range(centerProjection - gameObject.Size, centerProjection + gameObject.Size);
}

And you know what? That’s it! it will find collisions, it will work… except it won’t. In some cases it will find collisions that aren’t there. When? If circle is placed next to the corner of the rectangle, all projections from rectangle sides will show collision, but there is clearly a separation! Let’s work on that in next part.

False collision with SAT

False collision with SAT

SAT axis projections

Obstacle collisions, pt 2 Separating Axis Theorem

So there is a rectangle. And there is a circle. How to figure out if they are overlaping? Unfortunately there is no easy formula like for circles, or few ifs to do it (like for multiple rectangles). But this does not mean there is no way to do it at all. Meet Separating Axis Theorem.

It is really simple actually. Given two convex shapes (shapes where all internal angles are less or equal to 180 degrees), there will be at least one line you can draw that will not cross any of those shapes – you do not have collision. If there is no such line to be drawn, collision is certain.

SAT line separating objects

SAT line separating objects

What at first may seem very tricky is – how to find whether such line exists at all. Human eyes are extremely good at this, after all you can spot collision immediately (unles objects are really, really close to each other). But mathematically or algorithmically speaking this must be hard, right? No. In fact, it comes down just to few operations, none of them complex at all, to get the right answer.

SAT says that there will be a way to draw the line between two objects to exclude collision possibility. But checking every possible line will not be easy. Here comes axis part. If there is a line that goes between two objects without touching any one of them, it means that there must be axis (perpendicular to that line), onto which we could project our shapes and get a hole between both shapes’ projections.

SAT axis projections

SAT axis projections

But back to the issue. If I don’t know where to draw the line, it is basically the same problem – what axes to check? I can’t check every one of them (counting to infinity take a very long time). But there is no need to check every one. What has to be checked is only a set of axes related to set of shapes’ sides. But not the ones matching the sides, but rather the ones matching normal vectors shape’s side. Normal vector is vector pointing at 90 degrees angle from another vector (we can assume that shape’s side is a vector). Why normal vectors?

SAT false collision

SAT false collision

Check those two triangles. Clearly not colliding, and yet, if you were to check only the axes aligned with triangles’ sides, you will see that there is no spacing between them on any of those axis. And if there is overlaping area on every axis, there is a collision. That would be wrong result. But if there are separating lines, at least one of them will be parallel to one of the shapes’ side. Given this, I know I only need to check axes perpendicular to shapes’ sides (since resulting line is “represented” by empty space on axis with objects projections).

Hope this makes sense, since the idea is pretty smart and works really well. If you want to have a little bit of fun with interactive presentations of this problems, check out this tutorial where there is a great explenation of how this works in N game. Great game too!

Next time I will dive into code directly, so make sure you get the idea. Feel free to ask any question, I will clear things up as good as I can.