Neo Cab

In Neo Cab, we need interesting background scenery for Lina to travel through as she interacts with the pax. The fictional city of Los Ojos is a massive place, drawing inspiration from real world cities such as Mexico City, San Diego, and Dubai. We needed Lina’s routes to cover many miles of game-world, without repeating in a way that would be distracting to the player.

In an open-world game such as GTA, a real-world scale city is built and can be freely explored by the player. But this is not only a huge technical challenge, its takes a small army of artists and designers to create and populate every street and avenue. And in reality, we didn’t need to build the whole city, even though Lina may travel anywhere in Los Ojos, once she starts a ride her route is mostly predetermined (with some exceptions for gameplay choices that may affect her route).

We decided to take a procedural generation approach, generating routes that were informed by the length, character, and neighborhoods that Lina would need to pass through on the city map, but not worrying about matching every twist and turn exactly.

Chunks

The route is created by assembling a set of prefab models we call “chunks.” Each chunk represents roughly one city block or so, and can be straight sections, turns, forks, etc. Most of the chunks are square but they can be any shape to allow for curves and create more variety in the route.

Here are a few of the chunks used to build the city.

First Attempt

The first attempt to assemble the chunks was a kind of “What’s the simplest thing that could possibly work?” approach. We treat the chunks as a deck of cards, and simply picked the next one at random out of all the possibilities that would avoid overlapping. By weighting the probability that each chunk is chosen, we can favor chunks that would make a route with more distance or more compactness, and have some control over the overall characteristics of the route.

However, this simple approach didn’t offer enough control. Routes were too zig-zaggy, and often in an illogical way. If we increased the weighting on the “straight” tiles, it would begin to look reasonable in some areas, but we’d end up with miles of straight road in other places. Worse, even though we checked for overlapping tiles at each step, a route could easily “spiral in” on itself and get to a dead end where nothing would fit. Of course, there are ways around this — typically you’d backtrack or use a charming algorithm called “rip-up-and-replace.” We could have kept adding rules and conditions like this, but at some point we would lose the simplicity that made this approach appealing in the first place.

The L-System Prototype

In order to be able to iterate quickly and test ideas, I created a prototype to test the system with a simple 2D version of the route generation, using simple shapes instead of the full 3D chunks. The prototype enabled quick iteration on the algorithm and is still useful to try out new ideas for chunk shapes or route rules.

I implemented a simplified 2D version of the original route generation algorithm but the real breakthrough was using an L-System approach to generate the whole route. Instead of checking for collisions or overlaps at each step, and somehow rewinding and regenerating, we can simply define our rules to avoid overlaps.

An L-System is a procedural system that works by starting with a very simple pattern, called a “Start Rule,” and then replacing parts of that with slightly more complicated ones. By repeating this over and over, you end up with a complex pattern, and have a high degree of control over the results through your choices of which symbols to replace and what to replace them with.

For example, here is very simple L-System that starts with a single line segment, and then replaces each line segment in the figure with a line with a pointy part in it. That replacement is itself built of four line segments, so this can be repeated on all of those line segments until you have an arbitrarily detailed figure. (This is called a Koch Snowflake.)

In our system, there are two types of symbols: terminal rules, which are not expanded any further but represent a chunk of city geometry, and a non-terminal, which will be expanded.

Here’s a simple example: By convention, non-terminals are lower case and terminals are upper-case. In this case we have a non-terminal “s” that generates a straight section that is one, two, or three chunks long (and might have an intersection, the “+” symbol). We also have a terminal “L” and “R” which generate chunks that turn left and right. The turns might be a curve or an intersection, but that doesn’t affect the route shape. The non-terminal “a” simply generates a sequence of “straight, left, straight, right” or “straight, right, straight, left.” We stick a few of these together and get a route that contains turns and a mix of short- and long-straights, but always ultimately proceeds forward and will never wrap back to overlap itself.

Generating the Routes

The system used to generate the routes takes the list of chunks as a starting point and loads detailed geometry for each chunk along the way. It also assembles a road spline for Lina’s car to follow from smaller splines defined as part of each chunk.

Some of the chunks are intersections or have open turns, and so we have special chunks that we call “end-caps” that will extend or close off unused road sections. Finally, to add a layer of mid-ground geometry and block any open holes between buildings, we add geometry we call “mid-caps,” these are blocks of shadowy, lower-detail buildings and are simply added by attempting to place them along every edge of every chunk we’ve already placed, and skipping it if it would overlap existing geometry. These mid-caps are the green boxes you see on the right.

Final Touches — Decorators

To add even more variety, each chunk can have a bunch of “decorators,” which are spots where we can randomly place extra-detail objects such as signs, parked cars, trash cans, trees, or anything to spice up the route. I was expecting to have something like two or three of these for each chunk but it turns out our 3D artist, Lisa, is some kind of superhero and she defined, like, thirty of them for each chunk. In the screenshot above, each magenta cube is a location to possibly spawn a decorator, and the bottom shows one possible result.

Results

Conclusion and Next Steps

The basic system is in place and working well. Next we want to give the route more character and variety based on which neighborhoods of Los Ojos you’re traveling through, including having neighborhood-specific chunks and decorators, and even L-System rule-sets to pick from when you are travelling through a distinct neighborhood.

With too much randomness, procedural generation be wildly unpredictable. With too many constraints, it can build levels that are technically unique but all feel the same. It’s all about tuning the algorithm and the inputs to strike the right balance. In our case, the procedural elements form the backdrop and having some randomness helps prevent the routes from feeling identical or distractingly repetitive. But at the same time, this isn’t a racing sim and the gameplay comes from the human-authored stories that Lina experiences. So the goal for our procedural system is to reflect and enhance the narrative experience that’s the core of the gameplay.