Making Grass, part 5: Field of Vision

2019-05-09

FOV and memory

Compare the following three screenshots.

• In the first one, we show everything to the player. This is the easiest to implement, but a bit boring.

• The second screenshot implements field of vision (FOV). I calculate which squares are visible to the player, and render everything else in a darker shade. We're also not going to show monsters outside the FOV (for instance, behind closed doors). There is an element of surprise. Still, we know the whole map from the beginning.

• Finally, the third screenshot shows player memory (also known as "fog of war"). In addition to darkening unseen squares, I'm also not showing the squares the player has never seen. (Here, the right part of the map is explored, but the left part is completely unknown for the player, except for the part at the bottom that they glanced from across the river). Now you can go out and explore the map!

Once I had the FOV code, adding memory was pretty easy. It took me about 15 minutes to go "what if I added this array of booleans… now it works".

Smooth transitions

Since I wanted to keep smooth animation, FOV presented an additional challenge. I couldn't just show new fields entering the FOV. I have to add a smooth animation:

This is harder than it looks. Each square can have one of three states:

• unknown (alpha = 0)
• known but unseen (alpha = 0.4)
• seen (alpha = 1)

In addition, the state depends on your position. So when the player is moving between source and destination, I'm taking the "old" state (seen from the source square) and "new" state (seen from the destination square) and interpolate between them.

In addition, there can be monsters coming into your field of view or leaving it, and they are also smoothly animated! So for monsters, I might have to interpolate based on 4 values (player source, player destination, monster source, monster destination).

The good news is that if I ever implement teleportation, all this code should still work the same.

Implications about player knowledge

The visibility has to actually do something, instead of just making the screen slightly darker. This means patching a lot of things:

• As mentioned before, I need to hide monsters that the player cannot see. This is easy but has additional implications.

• I can highlight squares with mouse cursor, and get more information about them. This should be also disabled for unseen squares, and for unknown ones. Wait, I can still describe unseen-but-remembered squares… but I have to be careful not to mention anything about monsters.

• What about pathfinding? I can trace a path through remembered squares, but not unknown ones. Still, I shouldn't take unseen monsters into account. This produces a funny-looking effect when the player character tries to follow a path, enters the room with a monster, sees that the path is blocked and decides to go the other way. Then, when it stops seeing the monster, it wants to go back, and so keeps going back-and-forth between the two paths. I haven't solved this one yet.

The game still "cheats" a bit by showing the current level state for the "remembered" squares. This means we immediately notice if someone opens a door, picks up an item, or (in principle) digs out a corridor in the rock or changes the level in some other way. A more correct implementation would store a "last seen tile" in the player memory, not just a single boolean.

FOV implementation

There are many different methods of computing the FOV for a square grid like the one in roguelikes. Some more interesting properties:

• A more permissive algorithm will allow player to basically peek around the corners. This makes for an easier game but might be slightly unrealistic. It also has some implications for targeting and shooting.

• Some of the algorithms are asymmetric. This means you can see position A from position B but not vice versa. I though I didn't care until I got shot at from the dark.

I chose recursive shadowcasting because it had a short snippet of code, and after reading the description I think I understand it.

If you want to read more about FOV algorithms, there is a very interesting comparative study by Jice and a page by Adam Milazzo. Red Blob Games also has a page about 2D visibility in a more general setting (without grid).

What about all the monsters?

Then I thought, what if I want to calculate FOV for the monsters as well? This gets pretty expensive if I calculate this whole field for every single monster. If I only want to determine whether a monster can see the player, maybe I can just trace a line of sight.

However, I didn't know if the line of sight algorithm will be compatible with my FOV algorithm. I decided to go looking at how other solved it. I have a lot of respect for Dungeon Crawl Stone Soup, and it's being actively developed, so I dove into their code.

Surprisingly, I found that there is no compatibility issue because everything uses the same FOV algorithm, and in fact, all the visibility fields are cached! That is, for every (x, y) on the map, we store a separate 2D map (of size LOS_MAX_RANGE) that specifies which cells are visible.

And come to think of it, this is not a bad idea. If I have, say, a 50 by 50 map, and my field of view is 12 squares long in one direction, I need a 50 x 50 array of 25 x 25 arrays, or 1,562,500 cells in total. If I use one byte per cell (which is doable with ArrayBuffer), that means 1.5 megabytes for the whole level. Not so expensive these days, and I guess I could get it down to 1 bit per cell if I ever needed to.

One subtle corner case, that I also picked up from Crawl, is cache invalidation. If you open or close a door, that will change what squares are visible around that door, so you need to mark all squares in the vicinity (in the FOV radius) for recalculation.

Making Grass, part 4: Pathfinding

2019-05-08

Pathfinding

I want to control my character using mouse (or touchscreen) by just pointing to the destination. To do that, I need to compute the path around obstacles: walls, trees, or even enemies.

I implemented Dijkstra's algorithm and then A*. I won't be explaining these in detail, but Red Blob Games does it very well.

A* vs. Dijkstra

I wanted to see the difference between Dijkstra's algorithm and A*, so I added a visualisation. The algorithms find out a "previous" cell for each cell visited, so I drew a line to the previous cell. Here is how it looks like:

As you can see, Dijkstra's algorithm explores every reachable cell before it reaches the destination. The A* algorithm uses a distance heuristic that allows it to go "in the direction" of the target, so while it still explores a fair amount of cells in the vicinity, it doesn't even touch the left part of the map.

(The above pictures show a somewhat more difficult case because we have to go around the trees. If there is a straight path to the target, A* doesn't explore almost any unnecessary cells).

The downside is that A* is basically one-off: you compute it for a single source and destination. For the Dijkstra algorithm, you could compute a Dijkstra map for a single source and all possible destinations, and then read any path you want from it. The paths work both ways, so you could compute a Dijkstra map for the player's position, and use it for all monsters that want to find their way to the player.

A Dijkstra map be used for all kind of clever behavior. For more information, read The Incredible Power of Dijkstra Maps over at RogueBasin, and take a look at some pretty visualisations.

Tweaking the algorithm

In my game, diagonal movement takes the same amount of time as going horizontally and vertically. You might say that the game uses the maximum distance instead of the standard Euclidean distance:

function distance(a, b) {
  return Math.max(a.x - b.x, a.y - b.y);
}

The pathfinding code uses the same metric. One consequence is that a straight-line path has the same cost as one using diagonals:

While the second path is just as good according to game rules, it doesn't look like it's the best one. What's worse, because there are many equivalent paths, the algorithm is not stable:

The game recalculates the remaining path after every move. This looks great when your character reacts to changes in environment. However, recalculating (and displaying) the path makes the instability much more visible.

The solution to both problems (weird diagonal paths, and instability) is to break the equivalence between paths. I do that by imposing a small penalty for the diagonal movement:

const eps = 1 / 16;

const NEIGHBORS = [
    // horizontal and vertical movement cost: 1
    [1, 0, 1],
    [-1, 0, 1],
    [0, 1, 1],
    [0, -1, 1],
    // diagonal movement cost: 1 + eps
    [-1, -1, 1 + eps],
    [-1, 1, 1 + eps],
    [1, -1, 1 + eps],
    [1, 1, 1 + eps]
]

This makes the path stay in place.

Making Grass, part 3: Scene graph and performance

2019-05-06

Updating scene graph

As I said, the PixiJS graphics library makes it easy to draw things on a screen. It maintains a scene graph pretty similar to DOM, with Containers containing smaller objects, Sprites, as well as Graphics and Text elements. In the beginning, this was pretty convenient: I could just create a sprite for every map square, a sprite for every mob, and keep updating them when the world changed.

But then more and more changes came. The mobs (monsters) are moving, so I want to update their position in every frame. This is simple:

update() {
  for (const mob of world.mobs) {
    const sprite = this.mobSprites[mob.id];
    sprite.x = mob.x * TILE_SIZE;
    sprite.y = mob.y * TILE_SIZE;
    // (Do something more clever if the mob is currently moving,
    // i.e. between two positions.)
  }
}

But then, what if I want to allow opening a door? The terrain tile will also change. Should I loop over all the tiles?

for (let y = 0; y < h; y++) {
  for (let x= 0; x < w; x++) {
    const terrain = world.map[y][x];
    const sprite = this.terrainSprites[y][x];
    sprite.texture = textureFor(terrain);
  }
}

But it's terribly inefficient to loop over a large map in each frame, even if only one tile has changed. So maybe I should listen for changes by adding a callback?

changeTerrain(x, y, terrain) { ... }

world.onTerrainChanged(this.changeTerrain.bind(this));

Also, remember the pretty alpha-blending effect? I need to fade in and out the terrain tiles someone walks over:

So I added some more callbacks from world back to the renderer code. And fixed some bugs related to them. But it wasn't very fun. And I hadn't even covered creating and destroying mobs and items, which would require more creating/destroying sprites.

Then I wanted to add a marker for the "highlighted" square under the mouse cursor. I created a Graphics object, showed it when it was necessary, and hid it when the mouse was not over the cursor:

// init:
highlightPos = new Graphics();
highlightPos.rectangle(...);

// update:
if (highlightPos) {
  highlight.visible = true;
  highlight.x = highlightPos.x * TILE_SIZE;
  highlight.y = highlightPos.y * TILE_SIZE;
} else {
  highlight.visible = false;
}

I had a bunch of code like this for many objects on the screen.

Things started to look really familiar…

Making it declarative

I recognized where I saw this pattern and all these problems. Having a data model, and manually updating the view when it changes? Hiding and showing objects? Sounds like bad old days of jQuery soup!

And what weapon do I have against jQuery soup? React? Well… maybe not React directly, but the pattern of one-way updates and specifying the components declaratively.

I decided that while I don't want to recreate the whole scene every frame, I'm going to act like I am recreating the whole scene every frame. So the above examples become:

// draw mob:
const sprite = renderer.make(`mob.${mob.id}`, PIXI.Sprite);
sprite.x = ...
sprite.y = ...
sprite.texture = ...

// draw terrain:
for x, y in "visible portion of the map" {
  if (map[y][x] != 'EMPTY') {
    const sprite = renderer.make(`map.${x}.${y}`, PIXI.Sprite);
    sprite.x = ...
    sprite.y = ...
    sprite.texture = ...
  }
}

// draw highlight:
if (highlightPos) {
  const highlight = renderer.make('highlight', PIXI.Graphics);
  ...
}

// remove all the objects we didn't ask for in this frame
renderer.flush();

What's happening here?

• The renderer is a class I wrote that keeps a cache of all objects in the scene, referred to by name like 'mob.goblin2' or 'map.5.7'.

• When I ask for the object using renderer.make(), it either retrieves existing object from the cache, or creates a new one if I haven't yet. (The function even has an optional init callback for all the things that we only need to specify once).

• Finally, renderer.flush() removes all the "stale" objects that we didn't ask for in this frame.

This solution does have an obvious cost. I have to iterate over the entire scene in every frame, and keep the mapping between names and objects. However, once you accept the performance hit, the upsides are enormous:

• No more two-way binding, "on changed" callbacks and horrors of cache invalidation! No more manually adding or removing objects when something changes! The code is simpler and I'm free to make the scene as complicated as I want. If I want to draw something, or not draw it, I just write an if statement, not think about all the places where it might change.

• The scene graph only contains the objects I want to draw. PixiJS doesn't spend time trying to render something outside of screen (even if it does recognize that immediately, this adds some overhead). So the full map can be as big as I want.

• I do create and destroy objects, but only where I need to. For instance, if I move around the map, there will be some tiles coming into view, and some going out of view. However, most of the objects will stay on screen, so I will just update their properties.

I will be keeping a close eye on the performance, but for now the overhead isn't so big. This is definitely worth the price.

By the way, TypeScript generics are pretty nice. The above function is actually make<T> where T is any kind of PIXI.DisplayObject (sprite, text, "graphics", container…)

Profiling

Speaking of performance, both Chrome and Firefox have excellent profilers in their developer tools. I'm able to check how many frames per second are rendered, how much time is spent on graphics vs. any particular function.

A few times, the profiler "called my bluff" and forced me to replace a naive O(n**2) solution with a better one, or add some caching where I always computed something on the fly. Sometimes I did the opposite and decided I could afford to have simpler code.

Strangely enough, of the few machines I'm testing on, my desktop computer is the fastest, laptop is the slowest, and my phone falls in the middle.

Making Grass, part 2: TypeScript

2019-05-05

TypeScript

At some point Kos suggested I try TypeScript. Initially I was happy hacking away at the project in plain JS, but as the code became bigger and started spilling into multiple files, I decided to try it out.

It turns out TypeScript is pretty easy to introduce, because legal JavaScript code just works. Then you can start introducing some types to your functions and variables, and the compiler will tell you if anything doesn't match. Unless you're doing something weird, most of your JavaScript should be easy to annotate.

Here is where it helped:

• The obvious first place is enums. Instead of 'ATTACK' and 'MOVE' I can do ActionType.ATTACK and ActionType.MOVE. Well, this I can do in plain JavaScript, but thanks to TypeScript a typo is a compilation error. I can also expect an ActionType and not a plain string. And more importantly, if I want to make sure my switch statement covers all the options, the compiler is able to verify that.

• Union types are fun. Suppose I wanted to have an object that describes an action: I can ATTACK a mob, MOVE to a position, or OPEN_DOOR at a given position. I could define a type with optional mob and pos fields:

    interface Action {
      type: ActionType;
      mob?: Mob;
      pos?: Position;
    }
  

  However, this is not 100% safe. I could access action.pos for an action that doesn't have a position attached. Instead, I can define a union of interfaces, with type field acting as a tag:

    interface MobAction {
      type: ActionType.ATTACK;
      mob: Mob;
    }
  
    interface PosAction {
      type: ActionType.MOVE | ActionType.OPEN_DOOR;
      pos: Pos;
    }
  
    type Action = MobAction | PosAction;
  

  The compiler will recognize that I'm checking the type of an action:

    // Invalid: action.pos can be undefined
    console.log(action.pos.x, action.pos.y);
  
    if (action.type === ActionType.ATTACK) {
      // Valid: we know that action is of type MobAction here
      console.log(action.pos.x, action.pos.y);
    }
  

  It's slightly more verbose than in languages like Haskell (where I would just write Attack(Mob) | Move(Pos), but still pretty convenient. And while the OOP solution to the problem would be to give the control to the Action class (and perhaps use a Visitor pattern), so far treating actions as data is working out well. It's nice to have that option.

• Finally, once you have everything nicely set up, strict mode and strict null checks are where TypeScript really shines. Suddenly, variables of a given type (say, Pos) cannot be null or undefined! You have to use Pos | null and Pos | undefined for that. TypeScript will not allow you to pass a null value as a Pos, and will require you to check for null (for instance, by adding if (pos)).

  If you really want to, escaping the system is simple: there is an assertion operator (exclamation mark: x!) that tells the compiler you know what you are doing (although without adding a run-time check).

  This is similar to Optional<X> types in various languages, but again, without any additional syntax. What's nice is that it already makes the type system stronger than in traditional languages like Java, where even if you are using Optional, nothing is stopping you from passing a null anyway; and moves it closer to more water-tight systems like Haskell or Rust.

  I know that nowadays C# allows you to enable a similar option (Nullable Reference Types). I haven't tried it out but it looks like a similar idea.

It's sometimes noticeable that TypeScript is a bolted-on type system, and not a language in itself. There are ways to shoot yourself in the foot. Also, it's still JavaScript, so some things are awkward and you have to make compromises. But TypeScript gets you to that place of "if your code compiles with no errors/warnings, it probably works" usually associated with statically typed languages.

Also, I have to say that writing TypeScript with Visual Studio Code is really pleasant. The editor is relatively lightweight (if you can say that about an Electron-based application), but you get instant error checking, accurate auto-completion (thanks to the typing annotations) and automatically added imports.

Parcel

Since I'm using TypeScript now, I have a compilation step and can't just serve the files directly anymore. I have some experience with Webpack for packaging my JavaScript, but it's not the simplest to set up. Even a small project (like my Minefield) involves ~60 lines of configuration, and installing several plugin packages.

So I decided to try out Parcel which advertises itself as zero-configuration. The start is really smooth: just say parcel index.html and it will examine your file, bundle all the JavaScript and CSS, and set up a dev server. TypeScript will also magically work. Other asset types are also supported out of the box (well, you need to have the appropriate compiler installed). And it's pretty fast, although the auto-reloading tends to break randomly.

The dark side is that Parcel is not very flexible. It doesn't have a configuration file on principle (probably as a reaction to community's painful experiences with Webpack), with developers basically treating it as a slippery slope. You can of course customize TypeScript, or other tools used by Parcel, but once you want to have to customize Parcel itself, you're on your own.

So far I cut myself once: I wanted Parcel to stop trying to "package" links like ?map=2 (instead of index.html?map=2) and complain they will not work. Since there is no configuration file, as far as I know this would require (1) not using the Parcel CLI script and writing my own entry point, or (2) writing a separate Node package with a plugin for Parcel. I decided I didn't want it that badly and instead added a dirty hack that modifies the DOM.

Making Grass

2019-05-05

Initial idea: a sandbox for bots

There is a fascinating story of Rog-O-Matic, a bot written to play (and win!) Rogue. It evolved along with the game. I can't find the source for that, but I remember reading that in every new version, the Rogue authors tried to include a feature that broke Rog-O-Matic – and then Rog-O-Matic authors tried to keep up.

There are other projects like that. Famously, Angband has its Angband Borg, which also serves as an automated test of sorts, and can be even used as a screensaver. There are also many projects for NetHack. I think the concept is really interesting: you have a bot trying to play a game that is pretty difficult for humans, and involves imperfect information and a lot of risk assessment.

So I thought, maybe I could write a "sandbox" roguelike for bots like that? Then I thought that a client-server architecture would be perfect for this: your bot would be a custom-written client that can talk with the server over a specific protocol. The server could be even on another computer.

From there, it kind of naturally evolved into a multiplayer game. Because if you connect one bot, why not connect ten? And why not allow people to play on the server as well? Also, making the game in-browser seemed natural: not only it's a reatively friction-less platform because you don't have to install anything, but also there is already a scripting engine (JavaScript) included, if you want to run your bots.

Not much came out of that idea. I thought a lot about architecture for such a game, about how to make it turn-based but in real time, what should be the communication protocol, and even had some initial ideas of using event sourcing to store the game state as series of updates. I wrote some very early prototypes, but couldn't bring myself to follow through on any of them. My ideas for architecture didn't feel solid enough.

So I set the idea aside and tried to start from the other end. The Front end!

Starting with a mockup

Instead spending a lot of time on backend, and getting to the graphics and UI afterwards, I decided to first draw what my game would look like. I thought it would help me motivate myself if I could already see the game in some shape.

I wanted the interface to be more-or-less ASCII but maybe with some additions. I fired up Inkscape, a vector graphics editor, to draw a few different tiles, then used Tiled to create a map out of them. Then I added some more tiles (different kinds of walls, stairs…) and iterated on the design a few times:

As you can see, the concept moved away quite a bit from ASCII. One reason is that I wanted to have square tiles rather than rectangular. It feels more right to me to present the game world in a "uniform scale", so to speak. However, usually pure-ASCII square fonts don't look so well (and when you try to use the font for text, it becomes really bad).

Still, I tried to keep the symbols to be simple and instantly understandable. Minimalistic shapes, or universally recognized symbols. A few symbols (the trees, and of course @ and $) were taken from a font. The rest was surprisingly easy to draw! The graphics are vector based, but since the tiles are intended to be 32x32, I set up a suitable grid in Inkscape and made the shapes snap-to-grid.

And I'm still keeping @, letters for monsters, $ for gold and so on.

One thing I learned about ASCII and (ASCII-like) graphics is that black background is really important. I started out trying to have colored floors, with gray squares for the stone floor and green ones for grass. It didn't look good because there were sharp transitions between the squares. I could add some transitional tiles for "seams", but it meant a lot of additional work.

Instead, I went with the traditional ASCII solution, which is to have the floor be dots. Easy to implement, looks good, doesn't distract from the rest of the scene.

Prototype

Now that I had a mockup, making it come to life was pretty easy.

I did not want to use a heavy game engine that would make me follow some kind of architecture for everything from the start. I went with PixiJS. It's a pretty neat library that basically allows you to create a few new Sprite()s, add them to the scene, and throw everything at the screen.

Then I added movement. I always wanted to try animation in a roguelike - your movements can be quantified to full squares, but why not make the transitions smooth? To make it look better, I added alpha-blending to the tiles. If your character is standing somewhere, the ground tile below you should be hidden, and when you move, you can make the ground fade into view, and make the destination tile fade out at the same time.

Making it real-time

I originally wanted the game to be "real-time turn-based" with a turn happening every 1s or every 0.5s. This is how other multiplayer roguelikes (like TOMEnet and MAngband) work.

However, looking at my prototype, this felt really awkward. There was always an input lag after pressing a key, and what's worse, the lag felt random because it depended on when the turn is going to begin. So I decided to go the rest of the way to real-time and make the character respond immediately.

Now the game has a 60 FPS turn cycle. For each character, I have a "current action" field with information about timing. For example, for an attack animation that lasts for 3/4ths of a second:

player.action = {
  type: 'ATTACK',
  timeStart: now,
  timeEnd: now + 45,
  timeEffect: now + 13,
};

As you can see, there is a difference between time of the animation (timeEnd, after 45 frames) and time when the actual damage is applied (timeEffect, in 13 frames). The rest of the time is "cooldown", so that attacks cannot be repeated too fast. I animate it as a slow return of the attacker to the starting position: