Press enter or click to view image in full size
This post is about the video game Sleeping Dogs, released in 2012 and published by Square-Enix. As a member of the UI team on that project I spent a lot of time working on the in-game navigation system. The minimap (“mini map”) in particular took up a lot of my time, so here are some fun facts to the best that I can recall them. If you ever find yourself teleported back to 2009–10 with this information, you should take it to the United Front Games office at 1110 Hamilton St. in Vancouver, British Columbia. I’d find it very interesting.
A few definitions before we start:
- The Minimap is what appears in the corner of the screen during gameplay.
- The World Map is what you see when pausing the game and looking the “big map.”
- Pips are little icons that appear on the map.
- A Chase Radius is the semi-transparent circle that shows the range of something on the map, usually how far you have to get away to escape from the cops.
The Minimap Uses Three Coordinate Systems
One of the major functions of the minimap is to show the player the locations of things. Pips are typically they are either attached to a game object or spawned using a mission script function. This means that minimap pips have an in-game world 3-D coordinate (represented as a Vector3f ) which may or may not move over time, and that needs to get translated into a 2-D screen coordinate (pixel space, in the UI render plane.)
There’s a stage in-between those coordinate spaces, which can be thought of as “map texture space” or the UV coordinates of stuff from the world map texture’s perspective. The three coordinate systems are world coordinates, map coordinates, and screen coordinates. Translating from world space to map space is straightforward since they align: north in the game world is “up” on on the map. You can drop the vertical world axis (probably y), scale the other two (x and z) by a constant factor, and offset by the difference between the map texture’s origin and the world origin. As long as the map texture doesn’t change dimensions or configuration, these parameters are constant.
The relationship between map coordinates and screen coordinates is less simple because the minimap scales, rotates, and pans. Still, those are common geometry operations and figuring them out is game dev 101 type stuff. An interesting wrinkle is that minimap pips get bounded to the circumference of the on-screen map, which is a circle. So if a pip would be drawn somewhere nearby outside of the map, it gets drawn on the map edge instead.
Early minimap implementations used functions that work on Vector3f point data, but at some point I realized that keeping track of all of this was confusing enough to warrant creating custom types for map coordinates and screen coordinates. They were simple point types under the hood, but had conversion methods and type-checking to ensure that a world coordinate wasn’t getting passed around as a map coordinate, or a map coordinate passed around as a screen coordinate. Where conversions needed to happen, IDE auto-completion would easily be able to suggest the appropriate method to use. For me this because a formative experience in building an understanding of the Primitive Obsession code smell by seeing how easy it was to avoid.
Map Chunks Are Streamed From Disk
Sleeping Dogs was really tight on memory. When you pause the game to look at the map, it actually unloads all of the textures used by the in-game HUD to make room for that map texture, then it swaps that main map back out again when you return to game. During gameplay, when the minimap is showing, that unified map texture is not loaded all at once.
The world geometry in Sleeping Dogs is loaded in as hexagonal chunks as you move around. If you’ve ever noticed the game hitching while you drive at high speed, that’s probably because you crossed a boundary where one world geo chunk is being freed up and a new one is being streamed in from disk. This data streaming happens asynchronously and it’s difficult (if not impossible, on most hardware) for the player to outrun it.
I wrote a tool (in C#, I think?) called something like the “minimap chopper” that read in the world map texture and spit out a square tile for each chunk of the world. This tool ran as part of the build pipeline and its output got packed up as textures. At runtime these textures got streamed in and out in lockstep with the streaming world geometry, so whatever chunks of the world were currently loaded, those tiles of the minimap were also loaded.
If you were to remove the circular mask around the minimap render area (something that you could actually do in debug builds of the game), you would see that rather than an entire map under there, the minimap was just five or six tiles that abruptly ended not too far outside of the extents of the map border. Their corners overlap because the underlying world geo is in hexagonal chunks.
A fun wrinkle is that the minimap also shows layouts for some interior areas. These were defined by world trigger box volumes where, while the player is inside, it streams the interior map from disk and changes the minimap geometry to match the new texture coordinates.
Navigation Routes Use a Fat Line Mesh
I’m not sure what graphics experts call it these days, but back around 2010 a lot of game engines had a “fat line mesh” class that would take a sequence of points and return a line of a given thickness. Handling bends and elbows without creating weird looking artifacts was a common problem.
I didn’t have to think about this particular problem too hard since the rendering team owned the line rendering code. The minimap system basically just ferried navigation points from a GIS-like system into a FatLineMesh and rendered the result like any other map element.
I believe there was a bit of extra masking done by the UI to make the navigation line disappear behind the player while driving over it. Using the player’s current position as the starting point doesn’t work, because the resulting line segment doesn’t necessarily follow a road.
The Zoom Level Uses Careful Smoothing
At some point I started working on having the minimap zoom out as the player picks up speed and pull back in as the player slows down. This is a very useful feature for driving, and you can see it in Rockstar’s open world games like Grand Theft Auto V and Red Dead Redemption 2.
The first version that I committed tied the minimap zoom level directly to the magnitude of the player’s velocity. It didn’t take long for me to realize that, although this works fine when the player’s movement is smooth, it looks jittery and glitchy when the player’s acceleration is uneven. This happens a lot in Sleeping Dogs.
I added code to limit the rate at which the minimap’s zoom could change. When there was an abrupt start or stop, the zoom level could take several frames to adjust, which was less jarring. This was somewhat effective but not good enough. It did not solve cases where, for example, the player’s velocity was increasing and decreasing quickly in small, jittery steps, such as when driving over rough terrain.
A smoothing function was needed. I quickly coded up a ZoomCalc object that kept a history of the player’s speed over a rolling window of 10 frames. This was implemented an an array like float32[10] with a starting index that incremented and wrapped around (mod 10) every time a new frame was added. It calculated the desired zoom for any given frame by discarding the two highest and two lowest values in the current history, and then taking the mean value of the remaining six values. The end result was pleasingly smooth.
Police Blip Animations are Hand-Coded
Before Sleeping Dogs, I’d worked on some Need for Speed games for Electronic Arts, and having the “cop flashers” look good on the minimap was one of my responsibilities. It was a matter of professional pride for me to ensure that Sleeping Dogs hit at least that same quality bar.
Most of the minimap elements do not animate, and I believe only the border around the map was rendered in Scaleform GFx (where our visual designer could use Flash animations), the rest of it was custom rendering. I wrote up a C++ function to cycle the colour of the minimap police icons by frame count.
I spent a few hours trying different combinations of transitioning between red, blue, and white in sequence. For example, I could tween (interpolate) smoothly from red to blue and back to red, but that doesn’t look like a police car flasher — it spends a lot of it’s time looking purple in that configuration. Similarly, blinking back and forth between red and blue tends to look more like some kind of blinking LED than a cop car.
I believe that the sequence I landed on was two frames of red, one frame of white, two frames of blue, and one frame of white. It was something along those lines. You can try getting into a cop chase in Sleeping Dogs and see if that tracks.
Blips and Chase Radii are Scriptable
Some minimap blips and chase radius indicators are automatically created and destroyed by gameplay systems such as the scripts that handle police chases. Mission designers want as much flexibility as possible, so there are also open-ended SkookumScript functions that simply request the game to spawn a minimap blip at a given point, change a blip with a given ID, or remove a blip. The same goes for chase radii.
There are a few subtleties to minimap blips. We adjust the pip’s alpha to fade it out as it gets further from a certain range outside the map edge. As an optimization, we want to avoid making a draw call at all for blips that aren’t visible. It’s also useful to remember that you can avoid taking a square root when comparing distances if you just compare the square distance between two points against some squared threshold. A custom sqrt call can be fast (eg. using a lookup table) but it’s nice to avoid.
We also draw little up and down arrows if the pip is outside of a certain range within the player’s own altitude, to give more info about where the indicated location is. The player might be standing on an overpass over the map destination, for example. The practical upshot of that is that map blips do need to know their full 3-D world position. Not a big deal.
With hundreds of these things flying around at any given time, I ended up implementing a debug feature that would draw a table (the kind with rows and columns) of each minimap blip currently defined with some state information about it. There was even an option to filter the table by blip type and/or sort by distance from the camera, to help narrow down troubleshooting any minimap blip that was misbehaving.
One day I discovered that mission designers were animating the chase radius by changing its size frame-by-frame in script. That was not something that the UI team had designed the chase radius to do, but it worked well enough. That did give me a lot to think about regarding API design and how you often can’t anticipate how your interface will be used.
The Minimap and World Map Share Code
This may sound obvious, but a lot of the underlying C++ code used by the minimap is also used by the world map that you see when the game is paused. How this actually came about is somewhat crude because the minimap was pretty far into development before we started working on the world map.
I did something very lazy and typical for a C++ developer at the time, which was to create a base class to hold any code that was useful for both features, and then have WorldMap and Minimap classes inherit from it. This is not an ideal way to share code, but when you’re moving fast it’s a quick way to get things working. I was aware at the time that “is-a” inheritance tends to be a worse pattern than composing by “has-a” class members.
C++ build times are also very slow. Most of the big C++ projects that I worked on took about 20 minutes for a simple incremental build (you change some code and rebuild) and 4+ hours for a full rebuild. Sleeping Dogs was no exception here. This warrants a whole other post, but working on big-budget games back then was totally different from the code cleanliness and REPL iteration that I take for granted when working on, say, a back-end Python service with helpful unit tests.
All of that is to say that a lot of things happened in a quick and dirty way because the pace of development (both the rapid deadline pressure on one end, and the slow incremental builds on the other) made it too costly to do much refactoring. On the plus side, living with the problems that this caused gave me a thorough education in the value of clean code, which has served me well since.