2600 Random Maze Generator

[+Atarius Maximus]

Here's my tribute to Random Terrain.

 

I created a 7800 maze generator a few weeks ago with the intention of creating one for batari Basic too, and I just finished it up. It will generate a random playfield maze every time it's run. Once it's complete press the fire button to generate a new maze. It uses the standard kernel and superchip RAM for a 32x32 playfield.

 

The maze is created using the Binary Tree algorithm. Each playfield block is analyzed from left to right line by line, checking the blocks directly to the south and the east. If one of them already has an opening, the block is skipped. If there are no openings to the south or west, one block is randomly cleared, and we move on to the next. It could be changed to use any combination of adjacent directions (NE, NW, SE, or SW) which will change the layout.

 

It's not a perfect implementation of the algorithm as I add a border around the outside, as well as clearing a path in the top right and lower left due to the fact that this algorighm tends to favor diagonals and inaccessible areas would otherwise be created in the top right and bottom left. There's plenty of code tweaking that could be done to change up how the resulting mazes appear.

 

The code is pretty short and efficient and it should be fairly easy to adapt this into a game. Anyone that wants to use this code as the basis for a new game is free to do so. I just haven't come up with a good game idea to use this code with yet.

2600MazeGen.bas

2600MazeGen.bas.bin

[+Karl G]

It's awesome. It just needs orcs.

 

(I'm picturing a 2600 Rogue-like game).

[Keatah]

On stella, pressing the fire button generates the same maze again and again.

[+Atarius Maximus]

On stella, pressing the fire button generates the same maze again and again.

 

I'm not sure why that's happening for you. I'm running Stella 5.0.1 and it's different for me every time.

[+Atarius Maximus]

It's awesome. It just needs orcs.

 

(I'm picturing a 2600 Rogue-like game).

 

Yes! Orcs!

[+Atarius Maximus]

I added a "player" to the game that you can move around the maze. It's a blue dot.

2600MazeGen3.bas

2600MazeGen3.bas.bin

[Keatah]

I'm not sure why that's happening for you. I'm running Stella 5.0.1 and it's different for me every time.

 

No worries. It's probably some bug or something in stella.

[+Random Terrain]

What did they use for Maze Craze to get that more of a perfect maze type of look and less of the diagonal jagged look?

 

[+Atarius Maximus]

What did they use for Maze Craze to get that more of a perfect maze type of look and less of the diagonal jagged look?

 

 

They used a different maze generation algorithm. Recursive backtracking would generate a maze just like that one. I tried that this afternoon, but couldn't quickly come up with an easy way to do it, as you need to keep track of each block that's been visited.

 

Here's the logic behind recursive backtracking:

1. Choose a starting point in the maze.
2. Randomly choose a wall at that point and carve a passage through to the adjacent cell, but only if the adjacent cell has not been visited yet. This becomes the new current cell.
3. If all adjacent cells have been visited, back up to the last cell that has uncarved walls and repeat.
4. The algorithm ends when the process has backed all the way up to the starting point.

[+Random Terrain]

Is this guy doing something different on an Atari computer that doesn't need to keep track of each block that's been visited?

 

youtube.com/watch?v=wFeb3OGRHMg

https://www.youtube.com/watch?v=wFeb3OGRHMg

 

Looks like when it has no where left to go, it takes a ride on blocks that are already there until it finds an open spot, then it goes back to work.

[+Atarius Maximus]

Is this guy doing something different on an Atari computer that doesn't need to keep track of each block that's been visited?

 

youtube.com/watch?v=wFeb3OGRHMg

https://www.youtube.com/watch?v=wFeb3OGRHMg

 

Looks like when it has no where left to go, it takes a ride on blocks that are already there until it finds an open spot, then it goes back to work.

 

I read the description and I'm sure you saw that he does use recursive backtracking, and mentions using "breadcrumbs", by which I assume he means he marks the cells that have been visited. I don't think that particular algorithm can be done any other way. A better programmer than me could probably lay out how it could be done with bB, but in my trial and error testing today I was unable to come up with a way to make it work. Using an 8-bit PC would definitely be easier because of all the extra RAM that would be available, I'm not sure how to mark a playfield block as on or off and visited/not visited without using at least 2 bits per maze block, or 2K of RAM with a 32x32 maze grid.

[Mr SQL]

 

I read the description and I'm sure you saw that he does use recursive backtracking, and mentions using "breadcrumbs", by which I assume he means he marks the cells that have been visited. I don't think that particular algorithm can be done any other way. A better programmer than me could probably lay out how it could be done with bB, but in my trial and error testing today I was unable to come up with a way to make it work. Using an 8-bit PC would definitely be easier because of all the extra RAM that would be available, I'm not sure how to mark a playfield block as on or off and visited/not visited without using at least 2 bits per maze block, or 2K of RAM with a 32x32 maze grid.

 

Awesome Maze generator Maximus!

 

2K, but 2K bits​ - the 32x32 maze grid fits in 128 bytes so a second copy could be held in RAM if bB has an option to work with the CBS RAM 2K bit chip. I don't think bB supports this chip but Flashback BASIC does - you could use 1/2 of the virtualworld to hold visited/not visited bits and the other half for the bitmap.

[+Atarius Maximus]

 

Awesome Maze generator Maximus!

 

2K, but 2K bits​ - the 32x32 maze grid fits in 128 bytes so a second copy could be held in RAM if bB has an option to work with the CBS RAM 2K bit chip. I don't think bB supports this chip but Flashback BASIC does - you could use 1/2 of the virtualworld to hold visited/not visited bits and the other half for the bitmap.

 

Yep, you're of course correct on the math, I stated it incorrectly. I'd need 256 bytes of RAM for a 32x32 maze grid. Reducing the size of the maze could of course make it possible, but that makes the results a little less interesting to me. Mike Rideout created a random maze generator in batari basic years ago that can generate a perfect maze with the stanard kernel, but I think it uses all of the available RAM. Flashback BASIC does look interesting, and if I was to make an actual game out of this I'd probably go that route. It could also be possible using the DPC+ stack.

[Mr SQL]

 

Yep, you're of course correct on the math, I stated it incorrectly. I'd need 256 bytes of RAM for a 32x32 maze grid. Reducing the size of the maze could of course make it possible, but that makes the results a little less interesting to me. Mike Rideout created a random maze generator in batari basic years ago that can generate a perfect maze with the stanard kernel, but I think it uses all of the available RAM. Flashback BASIC does look interesting, and if I was to make an actual game out of this I'd probably go that route. It could also be possible using the DPC+ stack.

 

Awesome! It would be cool to see a random maze generating game in Flashback BASIC or DPC+

 

X2 on making a Rogue-like RPG or Adventure game out of this!