Mazes: The data structures I went through

I made a little project based on a meme I saw that completely went over my head. The meme being a maze that when filled would show a pixelated version of the loss web comic meme. I went on a short journey learnt the basics of how mazes are generated and created my first Go CLI project so the code may be terrible but it works.

In this post I want to take you through my thought process behind the data structure choices I made.

I started with a terrible data structure that being

pixels := [][]int{}

Where each int was either a 0 or a 1 depending on whether the pixel in the mask image was fully white or fully black. This structure made what I was trying to do hellishly difficult but it was a stepping stone that taught me the basics of opening an image in Go. I also created a simple terminal visualizer for the current state of the data using the square emojis ⬜⬛🟦.

I realized that the structure was not going to work so I tried out the following structure

type Node struct {
	outsideMask bool
	visited bool
	openWalls [4]bool
}

type Plane struct {
	width int
	height int
	nodes map[int]Node
}

This is where I started to use maps and ints as keys where each int was a index of a pixel in the mask image. This structure could of worked for me but it had one problem I didn’t like, the amount of separate variables.

So I rewrote it to this

type Wall struct {
	cell1 int
	cell2 int
}

type Grid struct {
	// 0:base state can be moved to
	// 1:visited state
	// 2:outside of mask
	cellState map[int]int
	cellWalls map[Wall]bool
}

This ended up being the basic structure that I settled on after a few tweaks which I will get to. I came to this structure as the cellState field gave me more freedom as you can see in my comments I could store not only the mask but which pixels had been visited with one value. One trade off here is that if I want to allow the maze to have multiple separate paths between two points I couldn’t but that is solvable by adding another field cellVisited.

While writing the generation code I found a problem, after the image was transformed into a Grid I had no idea how wide the image was so had no way to tell when I went to the next row of pixels. To solve this problem I add two new values width and height. Height was a bit redundant as I could figure that out with just the width but it was nice to have.

Soon after this point I thought to myself that if for some reason down the line I were to create a new Wall with the cell indices in a different order I could not compare walls reliably so I decided to change the way I create walls using a function that would always order the indices from smallest in cell1 to biggest in cell2.

At this point I was almost happy but the rendering to an image was slower then I wanted so I made one more change.

type Wall struct {
	cell1 int
	cell2 int
}

type Grid struct {
	// 0:base state can be moved to
	// 1:visited state
	// 2:outside of mask
	cellState map[int]int
	// if value is true wall is open else closed
	openWalls map[Wall]bool
	
	width uint32
	height uint32
}

Changing from starting with walls on ever side of every pixel and removing walls as I generated to recording openings as the maze was generated made the entire program faster but especially the rendering step. In order to do the rendering process now I was not drawing the walls on the background I was drawing the background on the walls. The process looks like this:

1. fill the image in with the foreground color(aka the color used for the walls)
2. loop over each wall opening drawing the opening and the visited cells based on the cell indices stored in each wall. This simple change reduced the amount of draw calls I had to make as I was not drawing the border around the maze and the background color of the maze before drawing the walls.

I would have written this blog post sooner if I was not trying to get an animation of the generation working for large images. I still don’t know how I could do this as drawing a new image every “frame” takes a lot of resources. I tried to use one image that I passed around as a pointer and just saved the value of it every frame to a file but that was just barely faster so it didn’t make much of a difference. I tired go routines and that went very badly almost crashed my PC but that is probably because I am so new to go and have not learnt enough to use go routines correctly.

Although this was a small and simple project it was fun and made me think I should, even as someone who does not use AI, do what AI Bros do more often that being tear down the old and rebuild instead of trying to make a flawed data structure work. If you would like to look at my first go program check it out here.