Crafting Mazes for the ZX81

Something I’d been itching to do is write a maze generator. Even though they seem simple enough, for some reason, I struggled to code one. With so many different algorithms out there, the sheer number of choices can be overwhelming. It wasn't until I took a vacation that my mind settled down enough for me to finally tackle the task.

# Taking Some BASIC Steps.

As usual, I didn’t follow a linear path. My journey began with a search for existing solutions. While I found a few, none of them quite hit the mark. However, I stumbled upon an intriguing one in an old BASIC book and thought it might be fun to adapt it for the ZX81.

Although I successfully converted it, there were times when it just didn’t work. No matter how hard I tried, I couldn’t figure out why. It seemed to function occasionally, leading me to conclude that there was a bug in the program. Despite investing hours in reviewing the code, I couldn’t pinpoint the issue. The lack of structure in the BASIC code made it even more challenging to trace its logic.

# Trying Something New.

Despite appreciating the maze generation technique used in the BASIC program, I decided to start fresh. Recognizing that the BASIC implementation relied on a randomized depth-first search algorithm, I began drafting some pseudocode to guide my new approach.

As I delved into coding, I quickly realized that using BASIC was not only slow but also counterproductive. So, I made the bold decision to start from scratch and code the entire thing in z80 assembly language. While this promised greater speed, it also meant grappling with more complex code. Challenge accepted.

# Coding the Maze.

Utilizing similar data structures from the BASIC program, coding wasn’t as tough as I had anticipated. Due to memory constraints, I opted not to rely on a stack. Instead, I used two array structures—one to track visited cells and another to track removed walls.

For context, here’s the pseudocode I followed:

1. Get a list of unvisited neighbors of the current cell.
2. If there are no unvisited neighbors, backtrack to the previous cell.
3. Choose a random unvisited neighbor and remove the wall between it and the current cell.
4. Mark the neighbor as visited and make it the current cell.

Though I rearranged this slightly in the assembly code, the essence of the algorithm remained the same. With determination, I set to work hacking up some code to generate the maze.

# Debugging and Printing.

Much of this coding happened while I was on vacation, cruising back to New York at sea. With plenty of free time on my hands, I found solace in writing code. It might sound strange, but it was my way of chilling out. The upside was that I had ample time for debugging.

And debug I did. Armed with a memory map, I meticulously followed the code’s execution. While it wasn’t overly challenging to track its progress, I made sure everything unfolded as expected. Once satisfied with the code’s integrity, I tackled two crucial tasks.

Firstly, I displayed the maze. Given my experience with the maze generation in the BASIC program, I decided to reuse it. However, I recoded it in assembly language for efficiency during testing.

Maze Generator, Maze Display, ZX81 Screenshot, 2024 by Steven Reid

Secondly, I introduced features to allow for controlled adjustment of the maze size. This involved adding titles, text, a customized prompt, and an exit mechanism to the program. Additionally, I included a progress icon to alleviate the wait while generating large mazes. Despite being written in assembly language, traversing all the cells still required some time.

Maze Generator, Starting Screen, ZX81 Screenshot, 2024 by Steven Reid

# Maze Wrap-Up.

With these enhancements in place, I finally had a working maze program. I was genuinely excited about it. While my wife found it cool, she couldn't help but shake her head at my childlike enthusiasm. Sure, it's just a maze, but for me, it represented the fulfillment of a long-standing goal.

Maze Generator, Building Screen, ZX81 Screenshot, 2024 by Steven Reid

However, my work isn't quite finished yet. The display routine needs some tweaking, which I plan to address in next month's article. Additionally, I have ideas for further enhancing the generator, but for now, life might throw a few curveballs my way.