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.

Advertisements

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 ;)

Move it soldier, or player to player collisions

There is a need to differentiate between collision types. There should be different behaviour when player collides with bullet and different if two players collide with each other. That is unless we assume players have bayonettes, which I don’t. With bullets it is pretty straightforward – bullet and player are eliminated from game. But what when two players meet? The idea itself is simple, players need to be moved back a little bit, just enough for them to no longer collide. But player’s move cannot be completly canceled – that would possibly take him too far out, leaving space between players and not making great user experience. Who likes invisible walls, right?

Fortunately the solution is not too complex. Again – circles make it so easy. We do have two circles that are colliding. This means that there is ceratin part of both circles that overlaps. What needs to be done is – I need to have distance at which the circles overlap and vector at pointing back from the collision direction to indicate how far player that caused collision needs to be moved back. And it is very similar to what I was doing in collisions already – I calculate distance between two objects using vector pointing from center of one object to center of the other. I also have distance between those objects – this is just a sum of ther radii. But how do I get vector pointing out of collision?

Circles colliding with each other and collision solution vector calculated

Circles colliding with each other and collision solution vector calculated

If I have distance between players and sizes of them – the difference between two values (distance – sum of radii) will be distance at which objects collide. Since I also have distance vector, all I need to do is to take unit vector of distance and scale it to the size of collision distance. But will the direction of vector be right? Sure it will. At first the vector is calculated to point from source object (say player A) to target object (player B that is). And since distance between players is smaller then sum of radii (that’s the only case in which collision is detected), subtracting those numbers will give negative value. Scale distance unit vector by this and in return you will get nice pointy vector pushing player out of player’s B personal space. Well, this explanation got long, but the idea presented in code is ultra simple. Just look:

private void HandleCollision(Player o1, Player o2)
{
    var distanceVector = new Vector2d(o2.Position.X - o1.Position.X, o2.Position.Y - o1.Position.Y);
    var distance = distanceVector.Length();
    var collisionLength = distance - (o1.Size + o2.Size);

    var collisionFixVector = distanceVector.Unit().Scale(collisionLength);

    o1.Position = o1.Position.Add(collisionFixVector);
}

And just one small piece – to figure out which collision handling method to use, and it is done.

private void CalculateCollisions(IGameObject o1)
{
    foreach (var o2 in GameObjects)
    {
        if (o1 == o2) continue;
        if (ObjectsCollide(o1, o2))
        {
            HandleCollision(o1, o2);
        }
    }
}

private bool ObjectsCollide(IGameObject o1, IGameObject o2)
{
    var distanceVector = new Vector2d(o2.Position.X - o1.Position.X, o2.Position.Y - o1.Position.Y);
    return distanceVector.Length() < o1.Size + o2.Size;
}

private void HandleCollision(IGameObject o1, IGameObject o2)
{
    if (o1 is Player && o2 is Bullet)
        HandleCollision(o1 as Player, o2 as Bullet);
    else if (o1 is Bullet && o2 is Player)
        HandleCollision(o2 as Player, o1 as Bullet);
    else if (o1 is Player && o2 is Player)
        HandleCollision(o1 as Player, o2 as Player);
}

private void HandleCollision(Player o1, Bullet o2)
{ ... }

private void HandleCollision(Player o1, Player o2)
{ ... }

Very simple, maybe will replace it with something smarter later on, but now it works like a charm.

Also note that I changed collision detection to take object as parameter. That is to change when collisions are calculated – now they are done immediately after the object moves. This is so that I can tell which object to move back – obviously this needs to be the one that caused collision by moving.

And that’s it – players won’t disappear after touching no more, but rather will slide around each other.

Collision detection

What fun would be the game where you can shoot but can’t hit anything? No fun at all. Therefore there has to be some mechanism to calculate collisions between objects in system.

private void CalculateCollisions()
{
    foreach (var o1 in GameObjects)
        foreach (var o2 in GameObjects)
        {
            if (o1 == o2) continue;
            if (ObjectsCollide(o1, o2))
            {
                if (o1 is IDestroyable)
                    ((IDestroyable)o1).IsDestroyed = true;

                if (o2 is IDestroyable)
                    ((IDestroyable)o2).IsDestroyed = true;
            }
        }
}

private bool ObjectsCollide(IGameObject o1, IGameObject o2)
{
    var distanceVector = new Vector2d(o2.Position.X - o1.Position.X, o2.Position.Y - o1.Position.Y);
    return distanceVector.Length() < o1.Size + o2.Size;
}

The code above is prety simple. Fortunately in my system all objects are round (what a genious design decision, right?), which makes collision detection extremly efficient and precise. What you do is – calculate distance between center points of both circles and compare them to sum of their radii (what a cool word, plural of radius, way cooller than radiuses). I don’t think it can get any simpler than that.

When I have collision, I do one thing – destroy each object that can be destroyed. For this I have marked player as destroyable as well – player would like to get some points after hitting other player, not just his or her bullets.

There are bunch of problems with this solution though. First it is O(n^2), I do iterate over objects twice to get my results. This also means I will detect collisions two times – after all if A collides with B – B will collide with A as well. I am also checking agains all objects all over the game arena, which may get quite big. That means a lot of collisions to check against, most of which seem ridiculous – what’s the point of checking collision with player who’s 200 units away from bullet.

It has one benefit though – it works and it is like 20 lines of code, works as starting point.