A presentation at React Alicante in in Alicante, Spain by Kevin Maes
Hola React Alicante! I’m so excited to be here. First, a big thanks to you and to the organizers and sponsors for having me! This talk is “Seek, and you shall finnd your way to fun!” So let’s see about that!
[Audience Question] Does anybody here have a side project they’re passionate about? Well I have a small side project and I’m excited to share that with you today!
My name is Kevin Maes and I’m a software engineer from the US. For the past 2 decades I’ve worked in NYC and, for the last 2 years, in Philadelphia. I’m super excited because I recently moved to Spain where my family and I now live in Malaga!
Perhaps you’ve all seen this Malaga photo by now. It’s amazing what AI image generation can do these days (more on that later).
I work at Stately where I get to build software that helps developers like you to collaborate and model software flows using diagrams and state machines.
First of all, let’s clear up some terminology.
And that’s what we’re going to talk about today! But since this is a lightning talk, we don’t have any more time for puns!
So why mazes? A few years ago I started playing with mazes, specifically, maze generation, and I discovered that the topic is built on whole foundation of interesting concepts, some of which I work with every day. Today, I’m going to take you with me, down this path towards discovering mazes So vamanos, let’s go!
Our starting point is a little bit of graph theory. Graph theory is the study of entities and the relationships between them, represented by connected paths. Graphs are like networks, made up of nodes. These nodes are connected by edges. Graphs affect us, as engineers, all the time.
Examples:
Graph theory can also help us chart the most direct or fastest way to travel between points on a map. Here we have our beloved Spain.
I mentioned that live in Malaga. But in order to fly to Alicante, I had to travel through Madrid. But what I really want to do was take a direct flight to this conference! At least there’s no jet lag!
Now on to mazes. Maze generation involves creating and navigating a network of interconnected paths. That sounds like a graph.
Consider the start and end of a maze and all of the steps it takes to travel between these two points. We can use graph traversal techniques to both create and solve mazes.
Today we’ll talk about maze generation so the technique we need is Depth-First Search (DFS) That involves diving as deep as possible into the graph from a starting node/vertex until you can’t go any further. Then we need to backtrack before being able to explore new paths. More on that in a bit.
For the purpose of creating mazes, it can be helpful for us to arrange our graph into more of a grid.
We can convert graph nodes into grid cells. The grid has its own columns and rows. Columns and rows are given index numbers like 0, 1, 2. One key change is that grid lines, separating each cell, do not represent the edges connecting our graph nodes. In fact, those lines represent the absence of edges between nodes as cell walls block these connections. At least for now.
Grid cells each have their own index number. They flow left to right, and then top row down to the bottom row.
And now we’ve converted our graph to a grid! Most regular looking mazes with shapes like squares, rectangles, triangles, even hexagons are built on top of this grid system. However, some mazes are more irregular, organic looking, or naturally occurring, and those do not strictly conform to a grid. But, they can still be said to function as a graph.
One common way to code a grid is by creating a so-called “2D array” That’s an array where elements might represent rows of the grid and each element contains its own array of the column cells, for that row.
However, it would be easier to flatten this out into a single array of cells. Yet, it’s crucial to be able to access any cell we want, quickly. So how can we do this?
Here’s what we know:
So we can just use some math to figure this out. Tip1: Get a cell’s rowIndex or columnIndex using its index and numberOfColumns. Tip: 2: Get any cell’s index by using its the rowIndex, columnIndex, and numberOfColumns.
So, if your grid array is huge, there’s no more need for nested arrays or O(n) array iteration. If you want to work with grids remember these tips to make it easier for yourself!
We all use algorithms to some extent in our work. Algorithms are often implemented with functions, loops, or recursion. State is often temporarily stored, almost implicitly, in variable values.
At Stately, we use statecharts which are like flows, built upon state machines. They’re also a representation of directed graphs, graphs whose paths have a specified direction. From the Stately, you can model software, and export JavaScript or Typescript code to XState, which is a state orchestration library.
It can sometimes be helpful to see algorithms as statecharts for a few reasons:
Let’s dive deeper into an example from our maze generation…
The most basic path nding algorithm for maze generation is the Recursive Backtracker, which is a version of depth first search (DFS). In this statechart we have states like Idle, Seeking, Advancing, Backtracking, and Finished We also have events like Start, always, after (waits for certain amount of time). We also check for conditions like whether we’ve reached a dead end or are back at the start.
Here’s how the algorithm works:
This algorithm is recursive because we keep repeating this over and over until we hit a dead end. At that point we backtrack to the last cell that still has unvisited neighbors. Backtracking causes us to pop off cells from the stack. We then proceed to find a path in a new direction. Eventually all cells will have been visited and we’ll be back at the start, finished.
The example I just showed uses P5.js. This library is used for creating interactive graphics and animations for the browser and was inspired by Processing, a language used to create generative art. All of the initial maze prototypes I created were done with P5.js. But another option we have for the web is HTML5 Canvas. So for my current side project, I combined React, Canvas, and statecharts using XState, to create a new version of a maze generator. Let’s have a look now.
App: mazes.vercel.app GitHub: https://github.com/kevinmaes/maze Stately Studio: https://stately.ai/registry/editor/e1573b28-f815-4571-8017-6e4743a0f370
Here’s the state machine for the overall application. All of this is mostly for the UI and the UI controls Moving the levers for FPS, num rows/columns sends events to the machine to store those preferences. In the middle we can see a big Generating state which invokes the Recursive Backtracker machine we saw before.
There are many other algorithms for generating mazes. These can vary by visual style, difficulty in solving, and algorithmic complexity. Keeping the parent application machine separate from the algorithm machine allows us to potentially swap out the recursive backtracker for a different generation algorithm. I just need more time in the day!
All of these statecharts and flows were created with Stately Studio - You can visit state.new to try them out for your own applications. Or follow @statelyai on Twitter!
By now, I know the one question you’re maybe asking yourselves is, “Where does AI fit into all of this?” AI image generation, like Dall-E, Mid Journey, Dream Studio, etc. can produce some very beautiful and convincing looking mazes. I personally really love the 3d mazes.
However, they can’t really ensure that these mazes are solvable based solely on the visual training data they rely on. There are a couple of potential workarounds:
So, the good news is…If your full-time job is generating solvable mazes then I don’t foresee AI taking away your job anytime soon!
GPT-4 Breaking News! It is actually possible for Chat GPT-4 to create maze generation code using the recursive backtracker algorithm, written in TypeScript with React, XState, and Canvas! Oh well!
So, what can we do to beat the AI? We can focus on the unique qualities we humans have enjoyed since childhood: our Innate curiosity, our drive for learning and discovery, and our creativity and sense of Adventure. And while you’re at it, maybe add a splash of color to your work or even bring back some sounds to the web! In a world of structure and rules, I love mazes because they allow us to wander, explore, and even get a bit lost. I encourage you to seek out your own passions and get lost in your own side projects. If anything you’re like me, you may never see them through to the end. But you’ll be so grateful for the fun they bring you, every step of the way!
This lightning talk, delivered at React Alicante 2023, is about fun with maze generation, including graphs, algorithms, statecharts, generative art, and sounds.
mazes.vercel.app
The following resources were mentioned during the presentation or are useful additional information.
View the working maze generation app online!
View the source code for the maze generation app. Or contribute by creating an issue for a feature you’d like to see or by making a pull request!
Model your own software flows as statecharts!
Here’s what was said about this presentation on social media.
for free. You
can too.