Key Hunt

Key Hunt is a multiplayer game for up to 32 players at once. Everyone runs around the same top-down map of grass, sand, ice, water and conveyor belts, picking up the keys scattered over it and knocking them out of each other's hands. It runs on Gamehoster, my realtime game server, which runs the game's small JavaScript and JSON files, keeps the players in step, and streams the game to every browser.

This page goes through the game, then the server half of it, then the front end and the bots, and then the binary messages that go between the server and the browser.

The game

The map is 50 tiles by 50, each 32 pixels square, and it wraps at the edges, so walking off one side brings you in at the other. The camera follows you, and the view is zoomed in so that only 16 tiles fit across the longer side of the window.

Every tile has a height, and the ground you're on changes how you move. Grass is easy going. Sand is lower than grass and slows you right down. Ice is slippery: you're slow to get going, and you slide when you let go. Conveyor belts sit lower still and carry you along. Walls stand up above everything and can't be climbed. Water is deep, and if both your feet are over it, you sink, lose all your keys, and come back somewhere else on the map.

There are always about 60 keys on the map, one on each of 60 tiles. Walk over one to pick it up. Your score is the number of keys you're holding, and the ten highest are on the leaderboard.

Press space, or click, to swing at whoever is nearby. A hit knocks them up into the air and away from you, and 70% of their keys spill onto the ground around them, for anyone to grab, including you. You can swing once a second, and not while you're in the air.

There are three characters, a King, a Queen and a Monk, and you're given one at random. They look different, and they swing differently: the King's swing is wide, the Monk's reaches a long way in front of him, and the Queen's goes all round her.

The map is never empty. When there are only a few people playing, the server adds bots, which walk the map looking for keys and pick fights with people who have some.

Built on Gamehoster

A Gamehoster game is a folder, and the name of each file in it says what it is: a schema for part of the state, or a body of JavaScript that runs at a particular moment. Key Hunt is 25 files:

keyhunt/
├── gamehoster-game.json                    # The rates, the capacity and the bots
├── gamehoster-instance/
│   ├── gamehoster-instance-schema.json     # The map, the arena's size, the view and the leaderboard
│   ├── gamehoster-instance-create.js       # Reads the map and puts out the first keys
│   └── gamehoster-instance-update.js       # The arena's tick: swings, keys and the leaderboard
├── gamehoster-player/
│   ├── gamehoster-player-schema.json       # A character
│   ├── gamehoster-player-join-schema.json  # What a player sends to join: a name
│   ├── gamehoster-player-join.js           # Seats a player and sets up their character
│   ├── gamehoster-player-update.js         # A character's tick: walking, heights, belts and water
│   ├── gamehoster-player-view.js           # Which objects each player is sent
│   └── gamehoster-player-smooth.js         # In the browser: snapping a character that respawns
├── gamehoster-commands/
│   ├── move/                               # Which arrow keys are held
│   └── attack/                             # Swing
├── gamehoster-entities/
│   └── key/                                # A key on the ground
├── gamehoster-frontend/                    # The setup, the inputs and the drawing
└── gamehoster-bots/
    └── hunter/                             # The bot

The bodies that run on the server are the authority: they're the only place the game is simulated. The ones in gamehoster-frontend/, and the smooth body, run only in the browser. Gamehoster builds a client from the folder, with the schemas, the browser bodies and the binary codec built in, and that's all the page has to load. Gamehoster has its own article, which goes into how the engine runs all of this.

The game's settings are in gamehoster-game.json:

{
  "gamehoster-game-title": "Key Hunt",
  "gamehoster-game-browse": "none",
  "gamehoster-game-create": "none",
  "gamehoster-game-tickRate": 10,
  "gamehoster-game-sendRate": 10,
  "gamehoster-game-capacity": 32,
  "gamehoster-game-botRate": 10,
  "gamehoster-game-botsMax": 16,
  "gamehoster-game-botsZeroAt": 32
}

Ten ticks a second is enough for people walking about, where Asteroids, with ships and bullets flying at speed, needs 30. Players don't choose an arena: the join body puts each new player into the first arena with room, and opens a new one when they're all full.

The server

Each arena is an instance, and the server moves every instance on by one tick ten times a second. A tick has three steps: the commands that have arrived since the last tick, then each character's own update, and then the instance update, which does everything that involves more than one player.

The map

The map is written in the instance's create body as 50 strings of 50 characters, one character for each tile, so it can be edited by eye. When an arena opens, the strings are read into a grid of tile numbers, which stays on the server in the instance's persistent state, and the strings themselves are put in the instance's state so that they're sent to each player once, when they join:

const SYM = { "~": 0, " ": 1, "#": 2, "<": 3, ">": 4, "v": 5, "^": 6, "S": 7, "I": 8 }
const TILE = 32

let cols = 0
const tiles = LEVEL.map(function (line) {
  if (line.length > cols) cols = line.length
  return line.split("").map(function (ch) { return SYM[ch] === undefined ? 1 : SYM[ch] })
})
const W = cols * TILE
const H = LEVEL.length * TILE

Gamehoster.Instance.Persistent.Set({ tiles: tiles, W: W, H: H, tile: TILE })
Gamehoster.Instance.State.Set(here, "map", LEVEL.join("\n"))
Gamehoster.Instance.State.Set(here, "arenaW", W)
Gamehoster.Instance.State.Set(here, "arenaH", H)

"###  ##  ##    ~        v~    #     SSSSSSv   ####",
"###  ##  ##    ~        v~    #     SSSSSSv   ####",
"               ~    ~   v~          SSSSSSv    ###",
"    ~~~~  SSS  ~            SSS  S  >>>>>>v     ##",
"    ~~~~  SSS  ~>>>>>>      SSS           v     ~~",
"    ~     SSS  ~~~~~~~      SSS             S   ~~",
...

The state

Everything that's sent to players is declared in a schema, field by field, with a type and, for a number, its range and how many decimal places matter. This is the state, and what's kept on the server and never sent:

A character's x and y are where its feet are, and z is its height above the ground. The arrow keys are part of the public state because every player's browser uses them to pick the right walking animation for that character. The swing tick is public for the same reason, so that everyone sees the swing.

Heights

Each kind of tile has a height. Where a character stands is decided by both of its feet, ten pixels either side of its x, and it's held up by whichever is higher, so you can stand on the edge of a drop with one foot over it:

function tileZ(t) {
  if (t === 2) return 13
  if (t === 0) return WATER_Z
  if (t === 7 || t === 8) return -8
  if (t >= 3 && t <= 6) return -12
  return 0
}
// the height the feet are supported at: the higher of the two foot tiles
function support(px, py) { return Math.max(tileZ(tileAt(px - FOOT, py)), tileZ(tileAt(px + FOOT, py))) }

A character can step straight up by as much as 12, which is just enough to climb out of a conveyor belt onto grass, but a wall is 13 above grass, so it can't be climbed. Water is -128, so there's nothing to stand on, and gravity pulls a character down into it a little more each tick until it reaches the bottom and drowns.

Moving

The move command only sets which arrow keys are held. Each tick, the character's update turns them into movement, and how depends on the ground under its feet. The velocity is kept from tick to tick, but cut down first by the ground's friction, and then each key held adds a push in its direction:

if (grounded) {
  const g = tileAt(x, y)
  if (g === 7) { vx *= 0.01; vy *= 0.01 }
  else if (g === 8) { vx *= 0.9; vy *= 0.9 }
  else { vx *= 0.2; vy *= 0.2 }
  let vc = 88
  if (g === 7) vc = 44; else if (g === 8) vc = 14
  if (Gamehoster.Player.State.Get(me, "up")) vy -= vc
  if (Gamehoster.Player.State.Get(me, "left")) vx -= vc
  if (Gamehoster.Player.State.Get(me, "right")) vx += vc
  if (Gamehoster.Player.State.Get(me, "down")) vy += vc
} else {
  vx *= 0.9; vy *= 0.9
}

Those two numbers settle on a top speed. On grass, keeping a fifth of the speed and adding 88 settles at 110 pixels a second almost at once. Sand keeps almost nothing and adds 44, so you trudge. Ice keeps nine tenths and adds only 14, so it takes a couple of seconds to build up to 140, and when you let go you keep sliding.

The character then moves in steps of at most 5 pixels, one axis at a time, so it can't pass through the corner of a wall. A step onto a tile more than 12 higher stops a character that's on the ground. One that's in the air bounces off instead, losing some of its speed:

const steps = Math.ceil(Math.max(Math.abs(vx / TPS), Math.abs(vy / TPS)) / 5)
for (let i = 0; i < steps; i++) {
  const nx = wrapX(x + (vx / steps) / TPS)
  const sxp = support(nx, y)
  if (sxp - z > STEP) { if (grounded) vx = 0; else vx = -vx * BOUNCE } else { x = nx; if (grounded && sxp > z) z = sxp }
  const ny = wrapY(y + (vy / steps) / TPS)
  const syp = support(x, ny)
  if (syp - z > STEP) { if (grounded) vy = 0; else vy = -vy * BOUNCE } else { y = ny; if (grounded && syp > z) z = syp }
}

A conveyor belt moves a character that's standing on it 5 pixels along each tick, as well as anything it's doing itself. That's a change of position, not of speed, so you stop as soon as you're off the end. A belt that runs into water carries you in, and one that runs up against grass lets you step off. Then gravity pulls the character down towards whatever it's standing on, and if it has sunk to the bottom of the water, it comes back on open ground with its score reset to zero, and its count of drownings goes up by one.

Swinging

A command can only change the state of the player who sent it. A swing changes other players, so the attack command just records that it was asked for, on this tick:

const me = Gamehoster.Context.playerId
Gamehoster.Player.Persistent.Get(me).attackRequested = Gamehoster.Tick()

The instance update can change everyone, so that's where the swing happens. It checks that the player is on the ground, hasn't swung in the last second, and wasn't hit in the last three ticks. Then it finds the swing's hit area, which depends on the character and the way it's facing:

Anyone whose body overlaps that area is hit. They're thrown away from the swinger at 500 pixels a second, and up into the air, so they fly on an arc and can't steer or swing until they land. They lose 70% of their keys, rounded up, and each one is dropped on a free tile within 96 pixels:

const om = Gamehoster.Player.Persistent.Get(oid)
const len = Math.sqrt(rx * rx + ry * ry) || 1
if (om) {
  om.lastHitTime = tick
  om.vx = (rx / len) * KNOCK
  om.vy = (ry / len) * KNOCK
  om.vz = KNOCK_UP
}
const lost = Math.ceil((o.score || 0) * KEYS_LOST_IN_ATTACK)
const os = (o.score || 0) - lost
o.score = os
Gamehoster.Player.State.Set(oid, "score", os)
for (let i = 0; i < lost; i++) spawnKey(o.x, o.y, KEY_DROP_RADIUS)

The knockback speed is set, not added, so every hit is the same shove, and the air has its own drag, so a thrown player comes down about half a second later, a few tiles away.

Keys

A key always sits in the middle of a tile you can walk on, never on water or a wall, and never two to a tile. After the swings, the instance update tops the map back up to 60 keys, at random free tiles. Then it looks for players standing on keys. Only a player on the ground can pick one up, so you can't collect keys while you're flying through the air from a hit:

for (const [kid, k] of Gamehoster.Entity.All("key")) {
  const kx = k.state.x, ky = k.state.y
  for (const [pid, p] of players) {
    if ((p.z || 0) > 4) continue
    const dx = wrapDelta(kx - p.x, W), dy = wrapDelta(ky - p.y, H)
    if (dx * dx + dy * dy <= KEY_PICK2) {
      Gamehoster.Entity.Destroy(kid)
      const ns = (p.score || 0) + 1
      p.score = ns
      Gamehoster.Player.State.Set(pid, "score", ns)
      break
    }
  }
}

The pickup comes after the swings and the top-up on purpose: a key that's dropped onto someone standing still is picked up on the same tick.

The leaderboard works the same way as in Asteroids. It's worked out every 3 to 8 ticks, a random gap each time, and only the names and scores that have moved are written, so the players are sent just the slots that changed.

What each player is sent

Each player can only see a small part of the map, so each is sent only the characters and keys within 480 pixels, which covers the view with a little to spare. That's under a third of the map:

const meState = Gamehoster.Player.All().get(me)
if (!meState) return
const cx = meState.x, cy = meState.y

for (const [pid, p] of Gamehoster.Player.All()) {
  const dx = wrapDelta(p.x - cx, W), dy = wrapDelta(p.y - cy, H)
  if (dx * dx + dy * dy <= r2) Gamehoster.View.Include(pid)
}
for (const [kid, k] of Gamehoster.Entity.All("key")) {
  const dx = wrapDelta(k.state.x - cx, W), dy = wrapDelta(k.state.y - cy, H)
  if (dx * dx + dy * dy <= r2) Gamehoster.View.Include(kid)
}

There's no need for the spatial grids that Asteroids uses. With at most 32 players and about 60 keys, which don't move, simply measuring the distance to each one is quick, and the tile grid itself answers every question about walls, water and belts with a single lookup.

The front end

The page

keyhunt.com is a single page with a canvas that fills the window. It loads the game's client from the game server and starts it, with the canvas and a name:

var local = /^(localhost$|127\.|\[?::1|$)/.test(location.hostname)
if (!local) window.GAMEHOSTER_SERVER = 'wss://game.keyhunt.com'
var httpBase = local ? '' : 'https://game.keyhunt.com'
...
load(httpBase + '/keyhunt/gamehoster.client.js', function () {
  Gamehoster.start('game', { name: 'Hunter' + Math.floor(Math.random() * 1000) })
  ...
})

The setup body loads the three sprite sheets, for the tiles, the scenery and the characters, from the game's own site. The join body on the server makes sure the name is unique in the arena, and changes the number on the end until it is.

What it sends

A browser sends the server two commands. The key bodies keep track of which arrow keys, or WASD, are held, and send all four together whenever one of them changes. Space, or a click, sends a swing, unless you're in the air:

var k = Gamehoster.Event.key
var held = Gamehoster.Persistent.Get('held')
var dir = (k === 'ArrowUp' || k === 'w' || k === 'W') ? 'up'
  : (k === 'ArrowDown' || k === 's' || k === 'S') ? 'down'
  : (k === 'ArrowLeft' || k === 'a' || k === 'A') ? 'left'
  : (k === 'ArrowRight' || k === 'd' || k === 'D') ? 'right' : null
if (dir) {
  if (!held[dir]) { held[dir] = true; Gamehoster.Command('move', { up: held.up, down: held.down, left: held.left, right: held.right }) }
} else if (k === ' ' || k === 'Spacebar') {
  if (!Gamehoster.Persistent.Get('airborne')) {
    Gamehoster.Command('attack', {})
    Gamehoster.Persistent.Set('myAttackStart', (typeof performance !== 'undefined' ? performance.now() : Date.now()))
  }
}

Holding a key down doesn't send anything more: the server keeps each key's state until it changes. So walking across the map in a straight line is one command when you start and one when you stop. Your own swing starts its animation the moment you press, without waiting for the server.

What it receives

Updates arrive ten times a second, and the client keeps a store of every object it can see. It draws a little behind the newest update, so there's normally a later one to move towards, and eases each character's position between the updates either side. The schema says x and y wrap, so a character crossing the edge of the map is eased the short way, across the edge.

Your own character is drawn the same way, from the server's updates. There's no prediction of your own movement as there is in Asteroids: a walking pace is forgiving enough that the short delay doesn't show.

A character that drowns comes back somewhere else, and easing it across that jump would slide it across the map. So the smooth body watches the count of drownings, and snaps the character to its new place until the eased count has caught up:

if (Gamehoster.Smooth("deaths") !== Gamehoster.Latest("deaths")) {
  Gamehoster.Set("x", Gamehoster.Latest("x"))
  Gamehoster.Set("y", Gamehoster.Latest("y"))
  Gamehoster.Set("z", Gamehoster.Latest("z"))
}

The camera follows your character on a heavily damped spring, worked out in steps of 5 milliseconds so it moves the same whatever the frame rate, and it doesn't move at all while you're near the middle of the screen. It jumps straight to you when you respawn.

Drawing

Everything is drawn from three sprite sheets, with image smoothing turned off, so the pixel art stays sharp however far it's scaled up. Each tile's corners are worked out in whole screen pixels from the world position of the corner, and neighbouring tiles share the same corners, so there are never any gaps between tiles, whatever the scale:

var fx = function (wx) { var v = gridX[wx]; if (v === undefined) v = gridX[wx] = Math.floor((wx - CAM.x) * S + VW / 2); return v }
var fy = function (wy) { var v = gridY[wy]; if (v === undefined) v = gridY[wy] = Math.floor((wy - CAM.y) * S + VH / 2); return v }
...
function tileCell (clipX, clipY, col, row) {
  var L = fx(col * 32), R = fx((col + 1) * 32), T = fy(row * 32 - 16), B = fy(row * 32 + 48) + 1
  ctx.drawImage(sheetTiles, clipX, clipY, 32, 64, L, T, R - L, B - T)
}

A tile's picture is 32 pixels wide and 64 high, and it's drawn reaching up over the tile behind it, which is how a wall shows its front face. So the map is drawn in rows from top to bottom, and in each row the tiles go first, then the keys, then the characters whose feet are in that row. Something further down the screen is always drawn over what's behind it, and a character walking behind a wall disappears behind it.

Grass, water, sand and ice each have eight slightly different tiles, and which one goes where is picked by a hash of the tile's position, so the map looks varied but stays the same every time. The conveyor belts are drawn in two pieces that slide along as time passes, so the belts look as if they're moving. A character sinking into water is cut off at the surface, and the keys bob up and down, each at its own pace.

A character has an idle animation, six frames of walking in each direction, and four frames of swinging. Its direction comes from the arrow keys it's holding, which is why they're part of its public state.

Bots

An arena is never empty, because the players are padded out with bots. A bot is a player without a socket: it has a character like anyone else, and it plays by sending the same move and attack commands that a person's keyboard sends.

How many bots

Gamehoster works out how many bots an arena should have in the same way as for Asteroids, but with Key Hunt's settings. There are 16 bots with nobody or one person playing, and one fewer for every two people who join, down to none once 32 people are playing. Bots never take a place a person could have.

There's only one kind of bot, the hunter, but each one is given slightly different settings when it joins, for how far away it notices keys and how ready it is to pick a fight, so they don't all play the same way:

Gamehoster.Bot.Persistent.Set({
  mode: "wander",
  tx: null, ty: null,
  keyId: null,
  attackId: null,
  lastMove: null,
  lastAttackTick: -1000,
  keyView: 260 + Gamehoster.Entropy() * 180,
  attackChance: 0.008 + Gamehoster.Entropy() * 0.04
})

How a bot plays

A bot runs ten times a second, reads the arena the same way the server's own updates do, and acts only by sending commands. It's always in one of three modes: chasing a player, going for a key, or wandering.

Walking in a straight line towards a key doesn't work on this map, because there's so much water and wall in the way. So a bot finds its way with a breadth-first search over the tiles it can walk on, spreading out from its own tile one step at a time and remembering which tile it reached each one from:

function bfsFrom(sc, sr, budget) {
  const prev = new Map(), dist = new Map()
  const NB = [[1, 0], [-1, 0], [0, 1], [0, -1]]
  const s0 = keyOf(sc, sr); prev.set(s0, -1); dist.set(s0, 0)
  let frontier = [[((sc % cols) + cols) % cols, ((sr % rows) + rows) % rows, 0]], count = 0
  while (frontier.length && count < budget) {
    const next = []
    for (let i = 0; i < frontier.length; i++) {
      const cx = frontier[i][0], cy = frontier[i][1], dd = frontier[i][2], ck = keyOf(cx, cy)
      for (let n = 0; n < 4; n++) {
        const nc = ((cx + NB[n][0]) % cols + cols) % cols, nr = ((cy + NB[n][1]) % rows + rows) % rows
        const k = keyOf(nc, nr)
        if (prev.has(k) || !standable(nc, nr)) continue
        prev.set(k, ck); dist.set(k, dd + 1); next.push([nc, nr, dd + 1])
        if (++count >= budget) break
      }
      if (count >= budget) break
    }
    frontier = next
  }
  return { prev: prev, dist: dist }
}

One search does two jobs. It gives the walking distance to every tile the bot can reach, so the bot picks the nearest key it can actually get to, rather than one across a lake. And following the tiles back from the key gives the route. With no key in sight, the bot picks a random tile it can reach, 3 to 10 steps away, and wanders there instead.

To walk the route, the bot aims at a tile on it, and when it gets there, it looks ahead along the route for the furthest tile it can walk to in a straight line, so it cuts corners instead of zigzagging from tile to tile. It steers in eight directions, picking the closest to where it wants to go that doesn't put a foot in the water, and it sticks with its direction while that's still roughly right, so it doesn't twitch. Like a person, it only sends the move command when the keys it's holding change:

function commit(p) {
  const lm = mem.lastMove
  if (!lm || lm.up !== p.up || lm.down !== p.down || lm.left !== p.left || lm.right !== p.right) { Gamehoster.Bot.Send("move", p); mem.lastMove = p }
  return p
}

It plans again when it arrives, when its key is taken, when a key comes into view while it's wandering, and every 5 to 13 seconds anyway, so it changes its mind now and then. If it has barely moved in a second, it's stuck, so it throws the route away and, if it was after a key, ignores that key for a while.

Each time it runs, there's a small chance that a bot picks a fight with the nearest player within 240 pixels who has keys. Someone with no keys is very unlikely to be picked, as there's nothing to gain. Chasing, it heads straight for them and swings whenever they're within reach:

if (t && !far && !bored && !robbed) {
  commit(steer(t.x, t.y))
  if (dist2(fx, fy, t.x, t.y) < ATTACK_RANGE2 && tick - (mem.lastAttackTick || -1000) >= 10) { Gamehoster.Bot.Send("attack", {}); mem.lastAttackTick = tick }
  Gamehoster.Bot.Persistent.Set(mem); return
}

It gives up the chase if they get more than 560 pixels away, sometimes once their keys are gone, and sometimes just out of boredom after six seconds.

The protocol

The server and the client talk over one WebSocket, in binary. Every message is a single stream of bits, and every value takes exactly as many bits as its range needs. The Gamehoster article explains the protocol in general, and Gamehoster's protocol reference has every message in full. Here's what it carries for Key Hunt.

A key coming into view is 29 bits, under 4 bytes. That's 1 bit to say it's an entity rather than a player, and then its x and y. There's only one kind of entity in the game, so no bits are needed to say which kind it is. A key never moves, so it's never sent again while it's in view.

A character's x, y and z are written every tick, so a character in view is sent in every update: its number in the player's list of objects, 12 bits saying which of its 12 fields are included, and the 40 bits of its position. That's about 7 bytes, plus a bit for each arrow key whenever its keys change. The score, the swing tick and the count of drownings only go out when they change. The count of drownings is only there to show that a character has respawned, so all that matters is that it changes: it goes back round to 0 after 255, and fits in a byte.

A move command is 1 bit to say which of the two commands it is and 4 bits for the keys, so it fits in a single byte, and so does a swing. The map is sent once, when you join, as part of the arena's state: 2,549 characters, so about two and a half kilobytes.