pwmarcz.pl

Making Grass, part 5: Field of Vision


Part of a series about Grass, a real-time roguelike engine with pretty graphics.

FOV and memory

Compare the following three screenshots.

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:

FOV transitions

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

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:

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:

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


Part of a series about Grass, a real-time roguelike engine with pretty graphics.

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:

straight path diagonal path

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:

unstable path

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.

stable path

Making Grass, part 3: Scene graph and performance


Part of a series about Grass, a real-time roguelike engine with pretty graphics.

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:

Walking animation

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?

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:

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


Part of a series about Grass, a real-time roguelike engine with pretty graphics.

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:

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.

VS Code completion

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


Part of a series about Grass, a real-time roguelike engine with pretty graphics.

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:

Grass

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.

Walking animation

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:

Fight with goblins