Seek, and you shall find your way to fun!

Seek, and you shall find your way to fun!

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!

Do you have a side project you love?

[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!

Who am I?

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.

Some terminology

First of all, let’s clear up some terminology.

1. In Belgium “Maes” is the name of a beer. In English, we say “maze” (meɪz).
2. This is corn, in fact, it’s a corn maze. In Spanish this is “maíz”. In English, we say “maze” (meɪz).
3. And this last one…well, that’s just a maze!

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!

Let's find our way!

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!

Graphs

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:

• Dependencies in the node_modules directory
• Web navigation
• The React component tree
• State management and data flow

Mazes as graphs

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!

Mazes as graphs

Now on to mazes. Maze generation involves creating and navigating a network of interconnected paths. That sounds like a graph.

Mazes as graphs

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.

Mazes as grids

For the purpose of creating mazes, it can be helpful for us to arrange our graph into more of a grid.

Mazes as grids

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.

Mazes as grids

Grid cells each have their own index number. They flow left to right, and then top row down to the bottom row.

Mazes as grids

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.

Mazes as grids

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.

Mazes as grids

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:

• Index numbers flow left to right, top row to the bottom row
• Of course, we also know the total number of columns. In this case it’s 3.

Mazes as grids

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!

Algorithms and State

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.

Algorithms and Statecharts

It can sometimes be helpful to see algorithms as statecharts for a few reasons:

1. To get a visual understanding of how the algorithm works
2. To view a breakdown of the discrete parts or steps of the algorithm (example: see the base case vs the recursive case)
3. To be able to spread out the implementation of an algorithm, over time, in a software program

Let’s dive deeper into an example from our maze generation…

Recursive Backtracker

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.

Recursive Backtracker

Here’s how the algorithm works:

1. With our grid of cells we begin in the Idle state, starting with one particular cell.
2. From there we move to the Seeking state in order to SEEK out a path. We represent that path using a stack, or a LIFO array (last in rst out).
3. When in the Seeking state we search in all 4 directions: Top, Right, Bottom, Left to randomly choose a neighbor that we’ve not yet visited before.
4. From there we move on to the Advancing state where we visit the chosen neighbor and mark it as visited.
5. We then add that cell to our path by pushing it onto the stack. We can now remove the walls between those two cells.

Recursive Backtracker

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.

Generative art - P5.js

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:

1. Purpose built models that generate mazes based on actual maze generation algorithms
2. Post generation validation where, after generating a maze, these can run a maze solving algorithm on the maze to determine whether it should be discarded or modifed.

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!

Conclusion

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!