This is a pared-down transcript of the video, with important bits highlighted and separated so it may be skimmed more easily.
The problem of location is often relevant during the course of any game, and it’s not always obvious how to insert gameplay significance to how the player traverses the game world. Not all games provide meaningful choices (or any choice) when transitioning between stages, levels, rooms or maps, and there’s often an opportunity for an interesting gameplay mechanic in that aspect of gameplay.
One of my goals for my game development has been to expand the gameplay Loop. Previously I’ve been mainly focussing on a turn-based loop, involving the basics of drawing cards, combat, and positioning, but I haven’t expanded it too far past the level of individual turns. I designated each of these procedurally generated eight by eight blocks a single room and mostly been keeping on with what happens in each room but I haven’t put much thought into what happens between rooms.
A Hierarchy of Location
While it’s easy at-a-glance to locate yourself inside a room, it can be difficult to understand your location in the game world as a whole, so the use of a hierarchy of location is helpful. At the very top, we have the game world, which is a collection of rooms. Each room is mechanically different, some having enemies of varying difficulty, others with treasure, traps, and bosses. If we want to add stylistic variety we could split the rooms into sectors, a level where the difference between sectors is thematic - different Sprites for enemies different environments a different isolated system.
Orientations for the Game World
1.5 Dimensional Maps
So there are many ways of organizing the game world. Like a lot of games, we can orient them linearly. For example in the mines of Stardew valley, adjacent floors are linked by ladders - if you are on level 99 you can only go to level 100 from there. Other games introduce some more complexity to this model where we can break from the linearity somewhat and instead use shortcuts between rooms. While you’re still limited to one direction of travel, you still have the option of your destination in some cases. Some also introduced Loops like Risk of Rain, where you can travel through the levels in a linear fashion, right before the last one where the player faces the final boss. From there, you can choose to go right back to the start to build up your arsenal and level up your gear.
2 Dimensional Maps
Yet other games have a different model. In many open-world games, your choice between spaces is no longer linear it’s two dimensional. If I want to get from point x to point y in Grand Theft Auto I have a lot of choices on how to get there. So when weighing the two options of a linear world map, a predefined sequence of levels, or a world graph, a 2D network of interconnected points there are a couple of things to consider.
Comparison of Map Architectures
A linear map is easy enough to implement. A lot of data structures are designed to work with one-dimensional data, arrays, linked lists, queues and more. It also puts the player on a predictable path so they can anticipate and plan for what comes ahead. On the other hand, it offers the player a little choice and for an entirely linear map, you may as well just use cutscenes. Like in the first Mario games you go from level 1-1 to 1-2. The gameplay significance of your game world becomes trivial.
A two-dimensional map is much more complicated. It creates an immense amount of uncertainty and complexity but it offers the luxury of choice. You can allow for many different routes throughout a game world in as non-linear a fashion as you like. Now moving between rooms becomes important, you can have trade-offs, do you rush towards the final boss, and lower your risk of taking lots of damage before you get there, or do you slowly and methodically pick through every room to make sure you have as many weapons and items to give you the best chance of beating the boss? There are few data structures designed specifically for 2 dimensions, beyond 2D arrays. Once you get past lists, the world of computer science opens up to data structures that span an arbitrarily high amount of dimensions.
Gameplay Implementation
I’ve chosen the latter design, and I’m going to be implementing similar to FTL’s map system, and with the background out of the way - here’s how I designed a procedurally generated world map, with the technical and design problems I encountered, and some solutions I came up with to solve them.
My system implements a Graph Data Structure - it’s a series of rooms, which I’ll call nodes, though they’re technically called Vertices, and they’re connected by lines called “edges”. Specifically, it’s an undirected, and unweighted graph - meaning that edges are bidirectional - you can travel in either direction, and we’re not storing the distance between edges - every edge is identical, except for where it starts and where it ends.
The Node
Even if you’re unfamiliar with CS, the high-level concept is quite simple: The whole system revolves around the Node. These are objects or containers for data, and in our case, they store only three* important things.
RoomType - You could make this a string, like “Treasure”, but Unity has this cool feature called Enumerations, which let you define a set of unified constants. So, I’m using something called RoomType.Treasure and Roomtype.enemy, but you can imagine these as arbitrary strings, or even numbers.
Adjacency List (The Self-Referential Magic Behind Datastructures!) - Each node stores a list of nodes, called “Adjacents”, or “Neighbours”. This self-referencing feature of nodes storing nodes is the magic behind the Graph, where we don’t need** an overarching structure telling us which element is where. Instead, we have a bunch of self-contained nodes that are linked to other self-contained nodes, and you could travel through the whole graph just by going from node to the node’s neighbours.
Nodes also have a position, an ordered pair of coordinates telling us “where” nodes are in space.
Each node also has gameobject, telling Unity how to show the node in the game - eg. sprites, but those aren’t too important to the generation aspect.
Graph Theory
With the data structure defined, let me walk you through how you generate a map, using Graph Theory.
Generating the Nodes in Code
So, when creating nodes - which point to rooms - I want to generate their position first, to avoid a pretty big technical challenge of procedurally drawing the graph when I was done, and also to have something that could be easily seen.
Position Generation
My first instinct was to place nodes randomly throughout the game window. It’s very easy to generate random coordinates within a range, and Unity has a way to get the screen width/height quite easily.
float height = Camera.main.orthographicSize * 2.0f - 1f;
float width = height * Screen.width / Screen.height - 1f;
And here we run into our first design problem - Purely random coordinates make it pretty improbable to get a nice looking graph. Often, they cluster or even overlap, and they’re never evenly distributed across the screen.
I’m sure you could think of a few solutions for this - every time you generate a node, ping every other node in the graph and check if they’re some minimum distance away, or you can pick a random existing node, add some random distance to it, and generate your new node there. The solution I chose to implement was actually to take a bit of a different approach.
Method of Screen Subdivisions (Making an Even, but Random Distribution)
First, you can divide the screen into cells, and then randomly set each cell to be ON or OFF. For the cells that are ON, place a node randomly inside the cell. I found this method to be pretty elegant, basically ensuring that nodes are generated evenly, but it has the disadvantage of not knowing for sure how many nodes get generated. Finally, we can store all the created nodes into a list of nodes. Their order doesn’t matter, but there’s a really neat trick we can do with them in a moment and it gives us a lot of advantages.
Linking Nodes
Now that the nodes are randomly placed throughout the map, we’ll have to link them somehow.
First, the mechanics of linking. One thing to note is that since we’re making an undirected graph if we connect A to B by putting B into A’s neighbouring node list, we need to also add A into B’s adjacency list.
We could try linking up all the nodes with the purely random approach. If we place them into our node list as soon as we have a position (think of it as a list of locations tied to ID’s), we can pick them out one by one and connect them to other random nodes, but another problem emerges - disconnection.
Dis/Connected Graphs
A connected Graph is one where each node can, by walking along the edges, get to every other node. Another way to think of this is that there are no isolated node clusters. You probably imagined this by default, but it’s actually not at all obvious how we can do this. I tried connecting nodes to three of their nearest neighbours, but that doesn’t actually guarantee that they’ll be all connected, so I’d still get islands of rooms that were unreachable.
The elegant solution to this relies on our list of nodes - which I’ll call the World List. We’ll add our first node to the list as soon as we figure out where it is, and then for every other node, we’ll generate a position, and then link it to a random node from our World List and finally add the linked node to the World List, rather than adding every node to our World List upon position generation and then creating connections afterwards.
We can eliminate the problem of clustering and edges that cross the map by modulating the randomness somewhat, where we’ll pick a node from the world list that minimizes Distance to the Current Node and Number of Existing Connections.
Gameplay
Remember at the beginning how I said each node also stored the type of room it was? I decided to put this part of the node generation last, and the challenges involved here are some of the most technically difficult.
There are several room types to generate - for example, TREASURE and SHOP rooms provide ways to amass and use resources, while some more challenging (MINIBOSS, TRAP, CHALLENGE) rooms offer unique rewards if the player is good enough at the game to not die. The most important two, are the starting point (The head) and the Boss Room (The tail). The goal here is to assign each node a RoomType in a random but interesting way, given a few objectives and constraints:
- The head and tail rooms should be far apart. It makes no sense for the boss room to be the second level, as it’s an unfair challenge at that level.
- Rooms should have varying rarity, based on their potential value to the player - particularly those who have a high reward with little risk, should be very rare.
- The map should go from left to right, so the player has some sense of what direction to go in.
- The critical path between the head and tail rooms should be normal rooms. I should guarantee that path between them is fair and doesn’t force the player to go into a miniboss room, and treasure/shops shouldn’t be spawned close to the player - they must find them.
Pathfinding with BFS
The first problem is a problem of Pathfinding, which many beginner game developers find poses a pretty big technical issue. It’s one of the first significant programming tasks that come up, and to be honest, I’ve had a fear of it for a long time. But it’s actually not that bad and I’ll try to introduce it in an approachable way.
Now, we first pick two nodes that are reasonably far apart to fulfil (1), in terms of numbers of connections. Since nodes are typically connected to ones adjacent to them, we can say that the distance between nodes is a reasonable proxy of how many nodes needed to get between them. The furthest distance between items in a rectangle is the diagonal, so I’ll pick the start node closest to either the upper/lower left of the screen, and the end node as the lower/upper right, respectively. Technically, this is done by sorting our WorldList by distance to the corners of the page.
With a head and tail in mind, we’ll have to figure out how to get from one to another, and store all the nodes in between as a “critical path”. This will be the one guaranteed path from start to end, and we know there must be at least one, because our graph was generated as a connected graph.
Dictionaries
A bit of background about Dictionaries - these are a data structure that store arbitrarily typed Keys and links them to arbitrarily typed values. To compare to a list - in order to get a value from a list, you need to know it’s index, an integer telling you where in the list it is. A dictionary doesn’t have an “order” per-se, but rather is a collection of keys of any type that map to a collection of values.
How it Works
The pathfinding algorithm I’ll be using is called BFS, or Breadth-First Search. I’m aware there are more complex and efficient ones, but most of them build on BFS and I really don’t care much for efficiency here. BFS is actually not that complicated of an explanation, and I found that Red Blob Games had a great explanation of how it works, and you’ll find a great Pythonic implementation there.
Please refer to the video, or the link for this. It will be much easier to understand.
Drawing the Graph
Drawing the Graph can be a serious challenge, but I sidestepped it by generating nodes with a position as their priority and deriving pretty much everything else from it. If I didn’t do that and generated nodes, then connections, it’s very difficult to draw them and establish a path through them.
There’s a really cool, but technically complex idea, called Force-Directed Graph Drawing, which, given a set of nodes and connections, you can treat connections as springs and nodes as masses and physically simulate the system, finally locking their positions once they found a physical equilibrium, but I haven’t the slightest idea how to implement that without literally writing a physics engine, so I didn’t bother.
Since I had positions already defined for the nodes, I just had to tell Unity to create (instantiate in the lingo) a GameObject with a basic circle sprite attached to it at the defined position. Easy. But how do you create links?
Drawing Connections
The final bit of mathematics I’ll be exploring here is about geometric manipulation to draw straight, dotted lines between points in Unity.
Here’s the problem:
Given node A and B, at positions (x,y) and (u,v), how do draw a straight line connecting them? (Answer: Clever use of vector manipulation comes in handy.)
The basic idea here is to tell Unity to draw a square sprite on the screen, then stretch and rotate it until it looks like a line connecting the two points. The position of the square and this is a Unity thing, locates its centre.
Let’s do this in a few steps:
Create a vector AB, going from point A to B. A vector is simply a mathematical object that has both a magnitude and direction, which you can think of as a length and an angle. We can describe it in many equivalent ways, but the easiest is with a pair of coordinates - one for the rise, and one for the run.
We’ll scale the square on the X axis, to be the magnitude of the vector, (Via Pythagorean length calculation) and on the Y axis, to be the thickness of the line - this is pretty arbitrary, I just wanted a thin line. We can rotate the square to align with the vector’s direction - note that rotations are done around the origin. This is done by matrix multiplication against a special transform matrix (Talked about in my isometric video), but Unity’s Rotate function can be used to abstract that complexity away.
We can position the transformed square at A so it’s now halfway towards B and halfway away from it.
Finally, we can offset the transformed square by pushing it towards B, by a factor of half the distance between them (half its magnitude). You can do this with highschool level Sin/Cos manipulation, or if you’re observative, divide the vector AB by two and add it to the position of the line.
Conclusion
I hope this tutorial was interesting and useful! If you found it helpful, subscribe on my Youtube channel: Wintermute Digital to be notified when I post something new. I have a lot of interesting articles up, primarily about making cool things in Blender, so check those out.
I will have a subscribe-to-this-website form up someday, though I do plan on rebuilding this website in React someday so perhaps it will wait until then.