NIMBY Rails — A development retrospective

My new game, NIMBY Rails, is now public. I’ve been working on it for the past 18 months and I kept a development diary. Here’s an abridged version.

It all started with a tweet

I saw @paniq tweet about paper which involved a very smooth, very natural curve interpolation, and I was immediately intrigued. To me it looked like a series of circle arcs linked by line segments at their tangents, and I quickly produced a bézier approximation of the same idea, drawing the arcs using cubic béziers with the often used coefficient of 0.55191502449.

I also had been, for some time, thinking about doing a game about railroads, with the twist of making it based on real world maps, trying to approximate real track networks. But the various games I tried that had vector-based tracks had either a too complicated interface for laying them, or tried to simplify too much and the curves seemed unnatural and quite different from real world track layouts. I was truly enamored with this way of smoothly interpolating a polyline into a curve, which was new to me, and seemed much more usable than the splines I knew. The idea of doing the railroad game with a track design based on this line interpolation started taking shape. So, barely a month before my finals, I started working on the idea for way too many hours every day.

November-December 2018 — I hope you like maps

I mentioned real world maps earlier. I really wanted to have the real world maps as the map of my game, the canvas for the player to build their track networks, but doing so would require using actual GIS data. The obvious place to start was OpenStreetMap. I like programming way too much for my own good sometimes, so I decided to start from raw OSM PBF dump files. These contain an optimized protobuffer dump of the OSM database, and can be found already pre-cut down into countries or regions. They are not database, being more like a serialization of the OSM data. In particular they lack any indexing. My idea was to load these PBF files and transform them into my own database format, with heavy lifting of processing ways and relations into triangulated shapes and generating indexes as a preprocessed step. I ignored MapBox, PostGIS and other ready-made solutions. My own map format would be stored as a series of tables in a SQLite database, with proper indexing.

In parallel to the OSM map preprocessor (which was alarmingly growing in complexity very fast), I started developing a map renderer. This would the prototype of my game. It calls into the underlying graphics API of the system via the excellent bgfx, and it would be all in C++, with me having been reconciled with the language after a years long detour into various Lisp dialects. This would be low level coding with no game engine and using libraries only for things like image loading.

This was the first time my rough prototype map renderer drew a recognizable map, processed by my OSM preprocessor. It is the street grid of my city, Barcelona, and it’s just doing polylines using GPU lines, with no real shape processing yet happening. But it was proof I could get somewhere.

I decided to iterate on increasingly complex and larger maps, switching to Andorra as an initial target. Here it is with the same prototype renderer. If it’s not clear enough, the left side is my renderer, the right side is the OSM.org render.

And here it is with quite a bit of work in just a couple days later. This is handling simple filled shapes already, as for example building footprints, which was a lot of work on the preprocessor side, since it needed to start triangulating ways and relations. I decided to triangulate on the preprocessor and not on the game, and take the extra storage hit. This would haunt me later on, but it was the right call in the end. Also not visible in this map is the fact all the vector data is in full precision longitude-latitude, not missing a single bit. This involves storing the coordinates as a pair of 32 bit floats and using vector shader tricks when doing the view transform to keep the full precision without ever using 64 bit floats, which are terrible in consumer GPUs.

Larger shapes are now triangulated, stored and drawn. At this point I was starting to battle with the concepts of relations, in/out ways, and how OSM stores them. A huge headache.

I switch to Luxembourg, looking for more complexity and a varied and larger urban grid. The preprocessor is now tagging and including more kinds of shapes based on the OSM metadata and the proto renderer is using more colors now.

There are two kinds of graphical entities in my processed database: line ways and filled shapes. Up until now the line ways were drawn using GPU lines, but I wanted more features than these simple lines. So I started my own line drawing code, with a reasonable amount of features like proper extruding modes and sane stitching. This took a solid week of work but it was very much worth it in the end, even if the results at this time didn’t look too good.

Luxembourg using the new custom line code.

And the same image with shapes enabled, and some shape textures. This image right here was the one that convinced me I had to finish this game. I had started programming less than 3 weeks earlier and I now had my own OSM preprocessing pipeline and custom map renderer. And my maps were actual shape data, that the game code could peek and poke as needed, instead of a static image backdrop. The maps still required a ton of work, specially to make them faster to draw and smaller to store, but it was time to start working on the other side of the idea, the tracks.

The first prototype code for tracks, as drawn using a very simple editor. It was using the initial idea of arcs plus segments at tangents, but it was still not maximizing the curve radius.

As I mentioned earlier, the game maps are data, not images. It is a central feature of the game that the tracks interact with the map as real tracks would. They cannot cross a street at just any angle. A surface track cannot go over a river. They cannot just go over a building. As seen in this gif the code was now in place for hit testing with map entities, starting with buildings (those were removed later on as worthy sacrifice, alas).

January 2019 — Track work

And in the same vein the game was now hit testing tracks with streets, and with other tracks.

I started iterating on this idea of “track conflicts”, the in-game name on the restrictions to build tracks. New textures and user interface was introduced for them.

I mention user interface since the track editor, while still being a prototype UI/UX wise, was already gaining all the required logic to make it sound.

Track branches are introduced for the first time. Being restricted to simple 2-ended runs of track, even if being allowed to build more than once, would be very limiting. Real world tracks branch and merge all the time, so the game has to support that too.

This is the first time I attempted to replicate a real world track layout, and it came out quite well and easy to do.

New track textures were introduced, with the idea to replicate the look of a double track build in an abstract way.

Several kinds of tracks were now supported, and these 4 made it to the current alpha build, although with tweaked textures and rendering. From top to bottom: viaduct, ground, tram and tunnel/subway.

Seas are in! The original OSM data either didn’t include seas or I couldn’t parse them. Instead I found an alternative sea shapes database, and I added them to my map preprocessor.

The first station data model and drawing. The idea was to make them as intuitive and easy as possible. They are an independent track segment with a bounding rectangle that surrounds them, called platforms, since they are intended to model a real 2 track platform in a station. Some stations just need one of those. But when the bounds touch another station bounds, they fuse together into the same station, giving you a 2 (4) platform station. And as long as you are in blueprint mode you can also move away a platform to get two separate stations. Or use a third to bridge over two existing ones. Or introduce a subway connection for a surface station by just drawing a tunnel station underneath.

First half of 2019 — Prototype ideas and trains

I somehow managed not to fail my finals in January, but I needed to focus more on my degree, so I didn’t devote so much time to the game at this point. I mostly hacked on an idea for multiplayer and managed to get it working, but it still needs a lot of work. It helped me to clean up the data model code a lot, as the later work on the editor undo stack did, and I now have plenty of design notes for a proper new data model that will support multiplayer, full undo/redo stacks, forward compatible saves, potential for parallel simulation code, and all the other goodies that come from being able to express your game state in terms of immutable, copy-able state plus discrete transactions you can apply or rollback at will.

I also played with a population density idea based on the density of certain map data. Namely the vertex density of certain kinds of roads and (at this point in time) building shapes. This is still an unexplored area of the game that needs a lot of work.

As part of that effort I introduced areas of influence for stations, the idea being that stations “capture” certain amount of population inside their radius of influence, and that population would later produce and demand travelers.

Another important idea was prototyped and implemented, track max speed. Each kind of track would have a max speed, and the shape of the track could lower that max speed. If the track is bent into a small radius curve then the speed is severely decreased.

What is a rails game without trains? There had to be trains! A first prototype dealt with very simple entities randomly circulating in a track network. Go forward while there is track to go, bounce back when it ends, randomly pick a branch if one is available.

Pathfinding came next. The same dumb train as before is now capable of picking a random point in the track network and attempts to trace a path using the A* search algorithm. It keeps into account the track speed and the track length to pick the shortest time possible between two points.

Next came making the trains look like more like trains. They are now composed of actual 1D entities which map on to segments of tracks, with several linked elements, one for each car.

At this point Max had also produced textures for the trains, with a variety of long distance, commuter and high speed models, and a full set of customizable decals for each.

Hit testing is not so straightforward as it looked like initially. While the non-branch case is an easy 1D check, the branching case requires a full 2D test. So trains are checked as 2D entities with generous bounding boxes when in the proximities of branched tracks.

A massive rework of the map processing pipeline and data format was also started, to culminate months later in summer. The idea was to optimize as much as possible the data format for a very lofty goal. At this point I decided I needed vector tiles. I would still be able to access all the map geometry as shapes, but those would be stored inside highly compressed, delta coded, quantized tiles, per LOD-level. I needed an order of magnitude decrease in the map file sizes. Because…

June 2019 — It’s the whole world or nothing. Also I will never get hired again.

I decided I wanted to include a map of the whole world, to make the game playable offline, with as much data as possible, in 20GB or less.

And thus started the big adventure of indexing the entirety of the worldwide OSM ways and relations database, triangulating and bound finding all of it, stitching every single way and relation, and distilling this entire thing into a highly compressed, highly optimized multi LOD vector tile database for drawing in a single file at or under 20GB. Again, I ignored MapBox or any other solution, and did my own thing. And what thing it was.

It was time to throw away everything I had learned about databases and scaling. I don’t have the money for horizontal scaling and doing things “by the book”. The prospect of indexing the OSM master PBF file is straightforward enough with a RDBMS, as PostGIS and the various OSM importers show, but I wanted to do it faster and cheaper. Much faster and much cheaper.

The first step of this process is turning the OSM PBF, a linear dump of unindexed, unlinked data into an indexed, stitched, and denormalized intermediate database. I picked LMBD since its write speed is legendary and it’s basically the fastest on-disk database you can get, while still having proper indexing. This first processing step involved renting a 1.4TB of RAM cloud instance for 8 hours. Quick FAQ:

Q: What?
A: I later optimized it down to just 800GB. It needs all of that memory to first build an in-memory index of the OSM PBF file, then dump it all as fast as possible into the LMDB file, saturating the disk link.

Q: Why not just stream insert it into the LMDB file as you read from the PBF?
A: As fast as LMDB indexing is, it’s still slower than a RAM heap-based hash map, for example. This way was faster, as in hours vs days. That kind of insertion is also the reason it takes days or weeks to do this with PostGIS.

Q: You don’t know anything about databases and scaling, I would never hire you.
A: It’s much cheaper and much faster to rent a 1TB+ RAM spot instance for 6-8 hours than say a 128GB regular instance for a week, or a cluster of them because itshowsitsdone. And this wasn’t the best part of what I did that makes me un-hire-able forever, keep reading!

The second step of the process is to use the indexed OSM data to build the game map tiles database. This involves indexing all the shape and line bounds in-memory in a R-tree. And since I like fast, it also involves loading all the data in RAM.

This time I knew the process was going to be much slower because it involved real CPU wrangling rather than some light data translation. But I was still determined to not use a database. So I load the entirety of the LMDB file as plain variety of C++ structs and objects and collections of them, and work with them as just in-memory data, rather than performing reads into the database. It turned out I ended up using the LMDB file as a preprocessed step for loading the OSM data. It’s still worth it since it’s much faster than querying the database on demand, caches or not.

But I was going to be over the 24h spot instance limit this time, the CPU cost of building the tiles is too high. So I decided I was going to hit the disk. As swap. This process runs on a rock bottom priced bare metal server provided by Hetzner. I used a 32 core Threadripper with 128GB of RAM and crucially, a couple of fast NVME drives in RAID0. I set up most of the drive space as a multi-TB swap space, and I let the map processor allocate as much heap memory it needs, in excess of 1TB.

Q: The hell?
A: The swapfile is my database, you could say. Also modern C++ libraries are a wonder and it handles a 1TB heap like a boss.

Q: I vanish you and your next 20 generations from the work force forever.
A: Have fun with kubernetes and spending two months and five figures doing what I did in five days and 100 bucks, I guess.

The first sight of my success was not much, but it meant it worked. And I wasn’t done. I could now process the entire world as many times as I wanted without having to ask for a line of credit in the bank, but file sizes were still too large. The next task was to kill buildings.

Before I removed buildings I made one last test and prototype of what eminent domain could have looked like. This track segment is forcibly demolishing buildings that conflict with it. It would be an interesting gameplay element, but it has a fatal flaw: while road and street coverage is good in OSM, building contours are limited. That means that some cities are only partly mapped and some are not at all. This, coupled with the extra space required from what is there, meant it was the first obvious thing to cut from the map data. I have not given up on buildings, but they will need to be procedurally generated, to cover the entire world and to not use valuable disk space.

After killing buildings I used many other tricks and ideas to bring down file sizes, but one of the most powerful ones was quantization coupled with delta coding. The previous image is the data as-is in OSM.

And this is what it looks like after shaving off the lower 8 bits of data, which is a form of quantization. This allows to express coordinates as smaller sized integers, which in turns allows them to be delta coded more efficiently. Delta coding is basically storing a sequence of values as the differences between them. If those values are close enough, the difference is a small integer that can be encoded in a few bits, compared to the original values.

I settled for 6 bits quantization. Looks much better than 8 bits and offers almost the same amount of delta coding opportunities. This quantization is equivalent to having a max map resolution of 32 centimeters at the equator, which is acceptable for a video game, if I may say so.

July 2019 — Adding some raster

I overshot my goal of a 20GB map. The map, covering the entire world, almost every road and street in OSM, indexed and ready to draw, was now 16GB. Oooops. And it also looked very poor at lower LOD levels. The shapes were too small, the roads and rivers irrelevant at the continental scale. OSM is not a topographical map. I needed some topography to make the game look nicer at these low zoom levels, so I decided to go hunting for some elevation tiles from NASA.

The result after a plain mapping of elevation to color.

And after doing a basic light projection. This is going more for the aesthetics than any rigor, and the result looks very good. It improves the map immensely for the medium and low zoom levels.

At higher zoom levels it’s allowed to blend in with the flat shape textures for a nice effect. A bicubic interpolation shader is being applied for magnification.

The relief mapping looks good, but it’s still a gray map. So another dataset was applied: a land usage texture provided by ESA. Again this is stored only for low and medium LODs, and progressively made transparent at higher zooms. This is the world overview without land usage:

And with the land textures:

The combined improvement of these two new raster layers is dramatic for some areas at medium zoom:

At the time I had already picked nuklear as the UI library for the game. I was at a point where the capabilities of the library were limiting me so I forked it and added 9-patch support to the skin system. But the main limitation was the lack of a sophisticated layout system capable of autosizing controls and windows. To this end I completely wrapped the subset of the nuklear API I was using with my own abstraction, and implemented a layout pass based on randrew/layout. I could now autosize every element of the UI with resolution independence, adapting to the available space and to the intrinsic sizes of elements like images and text labels.

August 2019 — Lines

Lines are the concept of having a sequence of stations to be visited in order by scheduled trains. The scheduling part is not done yet, but the lines themselves are in.

A lines editor with a visualization for them was added to the game. It is vital to make this aspect of the game as flexible as possible, so there are no limitations to the number of stations or their ordering. They also take into account the direction of travel. This aspect may be made more flexible in the future.

November 2019 — Visualization and UI improvements

I was now in the middle of the most difficult semester of my degree, but I still found the time to develop the game.

Track drawing was made to scale with real dimensions after certain level of zoom, just like it was already done with the trains. Some texture filtering tricks made it possible to draw everything as plain textures rather than having to use polygons and still look sharp.

A train editor was going to be required at some point so it was time to adapt the custom train shader into the UI drawing. Thankfully I had this task in mind when I originally implemented the map train drawing so it was relatively easy and the results look very good.

I hadn’t made a larger build in awhile so I tried a 50Km one, copying a real world train line I was familiar with.

December 2019 — SVG based UI

PC games often have terrible support for high density displays and their resolution independence usually boils down to either making everything tiny or making everything blurry. I was determined to keep everything as sharp as possible, and I decided to have (almost) every graphical UI element as a SVG file that would be scaled with the same factor as the underlying native UI from the OS. To this end I layered nanosvg on top of vg-renderer. The resulting combination is very limited compared to say Cairo, but extremely lightweight. I was already using vg-renderer for a few on-map UI elements and for the map labels so it was a no brainier. For the UI skin I preferred to pre-render the 9-patches and icons on load with the right scaling factor, using the also dead simple nanosvgrast.h rasterizer included with nanosvg. These elements are drawn very often and internally managed as bitmaps, so it was only natural to keep them that way.

January 2020 — New vector UI skin, train editor

Thanks to the new SVG support for the UI I replaced the provisional skin with a final one based in SVG files. It has a retro look with bevels and super clear styles on what is clickable and what is informative text. I guess I won’t ever get a job as a designer either. The UI is now perfectly scalable to any zoom level, keeping everything sharp and rendered in the native DPI of the display.

One last major milestone was required to declare the alpha version of the game complete. A provisional train editor was required, to be able to create and configure trains as desired, and to assign them to lines.

February 2020 — Polishing for the public reveal

The UI was functional but still very prototype looking. A major cleanup was done, to unify the way different tools worked, how listings were presented, and to finally decide how to present the main blocks of the interface. I decided to use fixed panels, not quite to the border, and embrace the modality of the existing editors. This may change in the future, but for now it was more reasonable to polish what existed than start a new interaction model from scratch.

I needed to make a trailer and do some big builds, and that meant traveling the world. To make it easier for me, and because it’s a really important feature when the game map is the entire world, I implemented a search engine for the map. This also made it clear that I was leaving out way too much information about places in my map preprocessor, so I fixed it to include 10x more town, city and area names.

A new visualization for lines was implemented. Unlike the first one, this is capable of stacking any number of lines on top of each other when they share a track segment, like real train line maps do.

The bézier based approximation for arcs is no more, and track tracing is now using real circle arcs. The result is virtually the same, with small radius curves being the most noticeable (but barely so). This was implemented by finding the intersection point of the lines that have the same direction as the normals at the start and end point of the arcs. That point is the circle center. Then the circle arc is traced using slerp.

March 2020 — Trailer and public reveal

I set myself the deadline of mid-March for the public reveal of the game. Most of late February and early March was devoted to the production of the game trailer.

Doing these large builds highlighted some flaws in the game. I fixed some of them as I went, and some others are scheduled for later. And after 18 months of working in secret, I was ready to show my game in Steam and start preparing for the future Early Access release.