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

Advertisements
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.

Overcoming obstacles, or more about collisions, pt 1

I don’t know if shooting game could be that much fun without something to hide behind and catch a breath. I will put some obstacles onto the map. What I imagine them to do is first, block all player movement through the obstacle, block all incoming bullets that hit obstacle, and, in future, block player’s view of the part of arena hidden behind obstacle.

I will start ith easy part first. I need obstacles to be visible on the screen. Invisible walls never really suited me, I’m shy guy after all. First, I extended my Arena class to hold list of obstacles. What is obstacle? Well, basicaly a thingy with list of points that define obstacle shape. It works for now, mybe will have something more in future to prove even more useful. But we like list of points, right?

public class Obstacle
{
    public Vector2d[] Points { get; set; }

    public Obstacle()
    {
        Points = new Vector2d[4]
        {
            new Vector2d(50, 100),
            new Vector2d(100, 75),
            new Vector2d(50, 0),
            new Vector2d(0, 25)
        };
    }
}

Since there are four points in this sample obstacle, you know it is going to be quadrilateral (yay for fancy words!, I’m not native speaker as you probably could’ve guessed ;)). I can tell you even more – it is going to be rectangle at an angle (see what I did here?).

And Arena looks pretty much the same but with a twist;

public class Arena
{
    ...
    public List<Obstacle> Obstacles = new List<Obstacle>() { new Obstacle() };
    ...
}

And this gets returned to the player once he signs into the game.

// RaimHub
public void Register(string name)
{
    name = HttpUtility.HtmlEncode(name);

    var player = arena.RegisterPlayer(name);
    players.Add(Context.ConnectionId, player);

    Clients.Caller.SignedIn(player.Id);
    Clients.Caller.SetupArena(arena);
    Clients.All.Registered(player);
    Clients.Caller.OtherPlayers(players.Values.Where(p => p.Name != name));
}

On a client this arena object is available for graphics “engine” to a) draw arena border, and b) draw all the obstacles. See the code, it is pretty simple:

var drawArena = function (gameObjects) {
    drawingContext.clearRect(0, 0, canvas.width, canvas.height);

    drawArenaBorders();
    drawObstacles();

    ...
};

function drawArenaBorders() {
    if (args.arena() == undefined) return;

    drawRectangle([
        { X: 0, Y: 0 },
        { X: 0, Y: args.arena().ArenaSize.Y },
        { X: args.arena().ArenaSize.X, Y: args.arena().ArenaSize.Y },
        { X: args.arena().ArenaSize.X, Y: 0 }]);
}

function drawObstacles() {
    if (args.arena() == undefined) return;

    var obstacles = args.arena().Obstacles;
    for (var i = 0; i < obstacles.length; i++) {
        drawRectangle(obstacles[i].Points);
    }
}

function drawRectangle(points) {
    if (points.length < 2) return;

    drawingContext.beginPath();

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

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

    drawingContext.strokeStyle = "rgba(0, 0, 0, 1)";
    drawingContext.stroke();
    drawingContext.closePath();
}

The same function draws borders and obstacles. All are rectangles, just one limits you from escaping and the other blocks you from going in. Well, sort-of. It will in future. I promise.

Master of time, or about benefits of server updates

As pointed out in some previous post, there are some disadvantages to calculating newarena state on server only when some client sends update. There is also a disadvantage to sending server updates on every client action – this puts a lot of stress on server (10 players, sending 10 updates a second, would mean server has to send 10×10=100 updates to server per second; 10 updates from client a second is really low number).

First I thought that I will address this simply by having arena raise event every time it thinks update is needed (so 30-60 times per second). After solving initial problem with events in SignalR hubs, it got to me – since there is no hub, there can be a time (and that will often be the case) when there is no one to handle event. Well, that’s easy – I will create my own hub. Well, not so fast – you can’t just do that. Hubs need to be created by hub pipeline, and it is not something I want to mess with. Well, that’s a pity. What should I do?

Thankfully SignalR creators thought about such use case and came up with possible solution. What is required is to create class that will take over some of the hub possibilites, like communicating with clients, make it singleton (well, not necessarily, but it works for me at this point), and subscribe to timer events in this class. This class will always be in memory (at least when I want it to handle my timer request), it will do what it needs and then send updates to clients like normal hub. From client point of view nothing really changes – they will all get normal updates in javascript like before.

Show me the code you say:

public class ArenaTicker
{
    private readonly static ArenaTicker _instance = new ArenaTicker(GlobalHost.ConnectionManager.GetHubContext<RaimHub>().Clients);
    private const int _updateInterval = 1000 / 60;

    private readonly IHubConnectionContext<dynamic> _clients;
    private readonly Timer _timer;

    public static ArenaTicker Instance {  get { return _instance; } }

    private ArenaTicker(IHubConnectionContext<dynamic> clients)
    {
        _clients = clients;
        _timer = new Timer(UpdateArena, null, _updateInterval, _updateInterval);
    }

    private void UpdateArena(object state)
    {
        var go = RaimHub.arena.UpdatePositions(DateTime.Now);
        _clients.All.PlayerMoved(go);
    }
}

What is going on is – there is private constructor so there will be guaranteed only one instance of this class. In it, it takes hub context. As you can see when creating this instance I’m hooking up to GlobalHost.ConnectionManager to get the context. It is slow operation so it should be done rarely, possibly just once per application runtime (or maybe one for each arena I need to update maybe?). This context will get updated with every client that connects, disconnects etc., just like in normal hub. Then there is a timer, that ticks 60 times per second (but easly adjustable to any other frame rate). It will call update on arena and then notify all clients on new arena state.
Please forgive the little ugliness of the code around getting arena – there is a static instance of this class in hub, I did not move it anywhere else since for a moment it does its job.

One more thing – notice that the code that returns objects to client changed a little bit. Before it looked like this;

_clients.All.PlayerMoved(RaimHub.arena.GameObjects);

This however resulted in issues with collection being changed when iterated over. That’s not good, I can’t have server crushing every time new player registers or some player shoots. This is now changed to return set of objects that were returned from update method. And it takes care of returning immutable collection when inside lock (to avoid changing collections when doing update to arena state).

public IEnumerable<IGameObject> UpdatePositions(DateTime? updateTimestamp)
{
    ...
    lock (_lock)
    {
        ...
        return GameObjects.ToArray();
    }
}

And now server is running 60 “frames” every second, always having pretty actual state, limitting number of updates to clients and improving on collision detection.

We are counting scores here

One useful info in any game that promotes rivalry of any kind is score each player gets. How else do you decide who is actualy better? In Raim, stuff is pretty simple – you get one point for any other player you hit with your bullet. Clear rules are the best.

Actual implementation? Well, that’s a simple one this time:

private void HandleCollision(Player o1, Bullet o2)
{
    o1.IsDestroyed = true;
    o2.IsDestroyed = true;
    o2.KilledPlayer();
}
public void KilledPlayer()
{
    Player.KilledEnemy();
}
public void KilledEnemy()
{
    Score++;
}

Bullet knows what to do in case it hit the other player. This time it only notifies player it belongs to that something like that happened so player can update internal score. In future maybe this will do something more.

Score is property of player so it will notify all players when the next update from server will be sent to clients. And what clients should do is to update leaderboard.

var playerMoved = function (gameObjectsFromServer) {
    gameObjects = gameObjectsFromServer;
    players.updateLeaderboard(gameObjects);
};
var updateLeaderboard = function (gameObjects) {
    for (var i = 0; i < _players.length; i++) {
        _players[i] = gameObjects.find(function (g) { return g.Id == _players[i].Id; });
        var playersList = document.getElementById(playersListElementId);
        var playerListElement = playersList.getElementsByTagName("span")[i];
        playerListElement.textContent = _players[i].Name + " " + _players[i].Score;
        playerListElement.id = _players[i].Id;
    }

    for (var i = _player.length; i < playerListElements.length; i++) {
        playersList.removeChild(playerListElements[i]);
    }
};

That is one ugly piece of code, but it will do for now :)

Death by thousand updates, or events in with SignalR

You know what’s weird? When no one moves, server does nothing. Well, that’s not exactly weird, servers are known for being lazy. But that’s not the point. It starts to mess things up when you think about bigger picture. First – client still updates positions of objects in every frame, but server does this only when inputs change. What else it does is – it moves one object, checks for collisions, moves another, checks for collisions, it goes on until all objects are updated.

Now think about this case: player shoots bullet in some direction and does nothing more. The server gets notified, updates objects and all, notifies all other players and everyone is good, and no one moves any more. Until few seconds pass, then one player decides it is time to move. This action of course causes server notification, server updates objects one at the time. But – few seconds have passed, so increments in bullet position will be significant. Big enough to, say, materialize behind player it would normally hit. Or, in other case, player may move in position when server last recognized bullet’s position and server will find collision with bullet that’s no longer there.

Well, I could certainly mess a little bit with how positions are updated on server, come up with algorithm to update positions a fraction of a second at time until longer range is covered. Sure. But this would bring other problems – what if collision happened two seconds ago? That would seriously make players mad – to die two seconds after you thought you’ve survived, who would like that in any game?

I think it is time to move to more proactive server position. My server side Arena object will be the one telling when updates are going to be happening. But first – it needs to have a way to say – yo!, hub, go tell players we’ve updated their position!

Events you say? Why, yes, events seems to be exactly what I want too. And I did this, removed all client updates from hub code, created event in Arena, decided when updates should be triggered (stayed with the same actions as before, just handled in arena, this will not solve the time difference between updates yet), and fired the event. In hub it is handled and notifies client.

public RaimHub()
{
    arena.ArenaChanged += Arena_ArenaChanged;
}

private void Arena_ArenaChanged(object sender, EventArgs e)
{
    Clients.All.PlayerMoved(arena.GameObjects);
}
public class Arena
{
    ...

    public event EventHandler ArenaChanged;

    public Player RegisterPlayer(string name)
    {
        ...
        OnArenaChanged();
        return player;
    }

    public void UnregisterPlayer(Player player)
    {
        ...
        OnArenaChanged();
    }

    private DateTime _lastUpdateTime = DateTime.Now;
    public void UpdatePositions(DateTime? updateTimestamp)
    {
        ...
        OnArenaChanged();
    }

    internal void ProcessInput(PlayerInput input, Player player)
    {
        ...
        OnArenaChanged();
    }

    private void OnArenaChanged()
    {
        ArenaChanged(this, EventArgs.Empty);
    }
}

Seems alright? Of course not, if this would be that easy I wouldn’t write about it. What started happening is – server was sending hundreds, and then thousands of notifications to clients. Every action on client caused even more notification callbacks. This was crazy!

Fortunately it didn’t take me long to notice what is going on. Notice how I initialize event handler in constructor. This would be perfectly fine if there was only one instance of hub ever, and with hub disappearing game would finish. But that is not the case. SignalR will manage hubs as it likes. What does it mean? Well, for example new hub may be created for each message from clients. Or two. Or fifteen. Why? I am not entirely sure. But that’s what was going on. Lots of hubs being created, each subscribing to event, and then being removed. But not completly – they are still subscribed to event, this not only causes memory leakage, but also my strange behaviour – hundreds and thousands of hubs being in memory of process, each gets notified about arena change, each sends update to player. Nice way to kill a server.

There are two possible solutions here. First – remove event handler subscription before removing object from memory. That could be done in finializer if there was no better way, but there is fortunately – IDisposable, ready to be overriden in each hub implementation.

public RaimHub()
{
    arena.ArenaChanged += Arena_ArenaChanged;
}

protected override void Dispose(bool disposing)
{
    arena.ArenaChanged -= Arena_ArenaChanged;
    base.Dispose(disposing);
}

And that’s what I did. Now it works as I hoped for.

And what is the second solution you ask? Weak event pattern. Where you create event which does not count as reference to an object durign garbage collection. It has one problem though – it may still be called as long as the object is in memory. And object not reachable during GC does not mean object is out of memory – it will only be removed when garbage collection happens, which may be very long time since SignalR assumes hub was removed. So IDisposable is a winner here.

You’re the center of my universe, or few words about viewport

The arena is big. Bigger than the screen. Well, at this point arena is infinitely big, but that’s gonna change at some point. It will be big though. You wanna know what is the problem with big arena? Player can get lost. More. Player can get out of screen. Try to aim when you can’t see your rifle! This is about to change.

Fortunately I already have viewport in place. Until now it served one purpose only – to flip around the Y axis and move the screen down so that player is visible, up is up and down is down. But in my mind I had already an idea of how it was supposed to work with scrolling visible game area so that player can see his or her representation at all times. The target is simple: I want player to always be in the center of the screen. It kind-of gives the impression that player does not move but rather all the world around him or her is being moved. And that’s fine – this way player is never lost, it is easy to rotate the player, mouse will always be rotated around center of the screen. The implementation is simple as well.

var processFrame = function (timestamp) {
    ...

    var currentPlayer = getCurrentPlayer();
    if (currentPlayer !== undefined) {
        viewport.x = canvas.width / 2 - currentPlayer.Position.X;
        viewport.y = -canvas.height / 2 - currentPlayer.Position.Y;
    }

    ...
}

Before each frame is being processed, I calculate new viewport size. In case of X axis it is straightforward – since I want player to be in the middle of the screen, I calculate how far of the screen center the player is (screen center being half the width of canvas; if I subtract player position from it I will get how many units I need to move my screen to get player centered).

For Y axis things are tiny bit different. Remember that Y axis is flipped (since Y in geometry goes up the higher we get, but on screen Y gets larger when we go down the screen), so I need to flip canvas height as well to get the correct number of units to correct my screen position.

Now it is time for graphics rendering:

function drawBullet(bullet) {
    drawingContext.beginPath();

    drawingContext.fillStyle = "rgba(0, 0, 0, 1)";
    x = bullet.Position.X + args.viewport().x;
    y = bullet.Position.Y + args.viewport().y;

    drawingContext.arc(x, -y, bullet.Size, 0, 2 * Math.PI);
    drawingContext.fill();
    drawingContext.closePath();
}

This is bullet drawing, but the same actions were completed in player rendering, skipped here for brevity. Since I have viewport which tells how far of the screen center player is, I need to add this value to all positions on the screen to translate those objects into correct position regarding to viewport. This is simple – just add viewport to position vector. Notice that y variable is still being flipped when being drawn – viewport does not change that, it only gets transition calculated in flipped units, but then the actual drawn point needs to still be flipped.

Is that all? No – there is one more place where viewport is being used. User input handling – where I calculate player mouse position in game arena coordinates:

function mouseMove(e) {
    var targetRect = document.getElementById("arena").children[0].getBoundingClientRect();
    mouseCoordinates = { x: e.clientX - targetRect.left, y: e.clientY - targetRect.top };
    mouseCoordinates.x = mouseCoordinates.x - args.viewport().x;
    mouseCoordinates.y = -mouseCoordinates.y - args.viewport().y;

    notifyKeysChanged();
}

Two things here. First – y axis mouse coordinates stay flipped, like when drawing. And second – here I do not add viewport but subtract it. This is simple – Since I’ve added it to move the world to screen coordinates, I need to reverse the operation to move screen coordinates into world coordinates.

And with those few simple changes player is now in the center of game and everything moves relative to him or her. And every player is certain he is the center of the universe. This proves Einstein’s theory that everything is relative nicely ;)