Graph Theory Applications in Video Games

Maze Generation is an element in games that can give players a unique
experience every time they play. Doing them efficiently can be
accomplished via Graph Theory. If you attended
my previous talk, you will know
how powerful the Disjoint-Set data structure is for object detection.
In this talk, however, we’re going to use it to generate mazes…
the right way.

Observing Properties of Mazes

Let’s see what we got here… There are a few things about mazes that
we should pay attention to prior to making one ourselves:

• Cells are “matched” with a select few adjacent ones. Cells that
  have been matched do not have a wall between them.
• All cell pairs that are not “matched” have a wall separating
  them.
• Mazes can be represented as graphs. Depending on the properties
  of the maze, it can be a minimum spanning tree.
• We can use typical graph algorithms to find solutions to mazes.
  Popular choices include DFS (Depth-First Search) and BFS
  (Breadth-First Search). We can use them to find a solution from
  any S to any T, easily.

Now then, let’s talk about Disjoint-Sets…

The Disjoint-Set Data Structure

Initially, treat this data structure as if we have n disjoint
sets (hence the name), not connected to each other at all. When
thinking about a maze, treat this as a maze where all walls are
up, and you can’t go from any cell to any other cell. Then, we can use
operations to manipulate this data structure and connect cells
together.

We have two operations we can use: union and find

• Union: Join two disjoint sets together.
• Find: Get the vertex that is at the “root” of a disjoint
  set. This is the “ID” of that set.

Let’s discuss them… For now, let’s only talk about Union.
Find has a neat optimisation that’ll come in handy later.

Union Operation

This one is trivial. Join two disjoint sets together. For this
part, I’m going to notate it as union(i, j) where
S_i = S_i ⋃ S_j. In
plain English: we merge the two sets S_i and
S_j into S_i. Then, S_j is
obliterated.

Let’s show a visual example of this… It might make some things
click more easily.

Example: Assume a graph M where n = 16 (there
are 16 vertices) and m = 0 (there are 0 edges). Each
separate vertex is part of its own set S_i(
v₀ ∈ S₀,
v₁ ∈ S₁,
…,
v_{n – 1} ∈ S_{n – 1},
). Shown as a 4 × 4 grid, we have the following:

Maze with all walls up.

Now let’s say we performed union(1, 2). The figures below
show the selection of 1 and 2 (left) as well as the result of the
union operation (right), visually:

Highlighting of 1 and 2 for union()

Post-union(). Wall between 1 and 2 is broken.

Post-union(), S₁ = { 1, 2 }. S₂ is empty and
obliterated. How about we try a union(2, 6) now?

Highlighting of 2 and 6 for union()

Post-union(). Wall between 2 and 6 is broken.

To properly generate a maze, we can just keep repeating this
procedure until there is only one set left.

Maze with no disjoint sets left.

At this point, the only remaining set is S₀ = {
v₀,
v₁,
…,
v_{n – 1}
}.

We are unable to merge anymore sets (and break anymore walls)
because they all belong in the same set already. Any other walls
being broken down will force a cycle to appear in the
graph. Let’s break down the kind of graph we have just created:

• The maze generation algorithm we just used is known as
  Randomised Kruskal’s Algorithm.
• There are no cycles in this graph.
• There is exactly one path from every S to every
  T.
• If drawn as a graph, it is a minimal spanning tree.
• It tends to generate mazes with patterns that are easy to
  solve.

Though, this wouldn’t be a talk by me though if I didn’t say we can
do better, now would it? Let’s expand on this concept:

A simple square maze is boring. We can do better.

We can connect 2 mazes together by breaking down a wall between
them. We can even add a “hallway” between them if we wanted. This
is only possible because there exists a path from every S to
every T.

Thus, if we broke down a wall on the outer end of the maze and
merged two together, there will always exist a path from one maze
to the other, as there will always be a path to the cell with the
outer wall we broke. Here’s what I mean:

Two copies of M, with a hallway connecting
v₇ and v₂₀ together.

This kind of “horizontal expansion” is possible with mazes.
We can also do this vertically. Notice, though, that there is a
valid path from anywhere in the left maze to anywhere in the right
maze. To take this to the extreme, we can still do better,
and expand the maze by an entire dimension (or a few, if we
really wanted to). Let’s give it a second floor…

Two copies of M, with an “elevator” connecting
v₆ and v₂₂ together.

We can go on, but I think this gets the point across. We can also
combine the horizontal/vertical expansion with this “elevator” to
make some pretty unique (but also tedious) puzzles!

Find Operation

The “find” operation is used to find the ID of the set a vertex
belongs in. I’ll denote it as find(i). If S₀ = {
v₀, v₁ } and I call find(1), it’ll
return 0, because v₁ ∈ S₀. By the time the
maze generation algorithm above is done, calling find() on
any vertex will return 0, as they are all in S₀.

Since the union(i, j) of two sets, in a graph theory sense,
is simply connecting an edge between two points, the find(i)
operation is simply going up to the root of the tree and
returning that value. Let’s go though the previous maze generation
example once more. This time, let’s see how a graph is built
from all of this.

Maze with all walls up.

Graphical representation.

Maze post-union(1, 2).

Graphical representation.

Maze post-union(2, 6).

Graphical representation.

Maze fully processed.

Graphical representation.

Now that we’ve constructed the graph, let’s order it to where the
coloured node (the root) is at the top. It’ll look like this:

Maze drawn as a “tree”-like graph.

There’s something bad about this… Take a look at the deepest node
in that tree. Since find just goes up to the top and returns
the root node, it has to go through 6 vertices before it
returns. That’s an O(n) operation right there.

Now, I’m not going to make a huge deal out of a linear-time lookup.
A maze of size 2048 × 2048 would speak for itself. But, like
I said, we can do better… much better.

Improving “find(i)”

There are two techniques we can apply to our operations to make
find() perform much better: Union by rank and Path
compression…

• Union by rank – When merging two sets, attach the
  shorter tree to the taller one. This forces minimal (or no)
  growth of the tree. In fact, at most, the tree can only
  grow in height by 1 from this.
• Path compression – Make every node point straight to
  the root node.

The visuals of these two would get messy quite quickly, so I
decided to not draw them out. But I think those explanations make
it obvious how these improve on what we had before.

Now then… with these optimisations in place, our O(n) lookup time
suddenly becomes lg^* n (iterated logarithm base 2). In
the world of Computer Science, this is essentially constant
time. For the record, if x = 2⁶⁵⁵³⁶, then
lg^*(x) = 5. Here’s a table of values just to show
how slow the equation grows…

Values of lg^* x.

For the record, ⁿa is not a typo. It’s known as
tetration,
and is a step up from exponents. If I said ³2, that’s
the same as 2²². ⁴2 =
2²²². You get the idea.

Keep your files stored safely and securely with the SanDisk 2TB Extreme Portable SSD. With over 69,505 ratings and an impressive 4.6 out of 5 stars, this product has been purchased over 8K+ times in the past month. At only $129.99, this Amazon’s Choice product is a must-have for secure file storage.

Help keep private content private with the included password protection featuring 256-bit AES hardware encryption. Order now for just $129.99 on Amazon!

Help Power Techcratic’s Future – Scan To Support

If Techcratic’s content and insights have helped you, consider giving back by supporting the platform with crypto. Every contribution makes a difference, whether it’s for high-quality content, server maintenance, or future updates. Techcratic is constantly evolving, and your support helps drive that progress.

As a solo operator who wears all the hats, creating content, managing the tech, and running the site, your support allows me to stay focused on delivering valuable resources. Your support keeps everything running smoothly and enables me to continue creating the content you love. I’m deeply grateful for your support, it truly means the world to me! Thank you!

BITCOIN bc1qlszw7elx2qahjwvaryh0tkgg8y68enw30gpvge Scan the QR code with your crypto wallet app

DOGECOIN D64GwvvYQxFXYyan3oQCrmWfidf6T3JpBA Scan the QR code with your crypto wallet app

ETHEREUM 0xe9BC980DF3d985730dA827996B43E4A62CCBAA7a Scan the QR code with your crypto wallet app