Random maze possible with batari Basic?

[SeaGtGruff]

You're welcome, but be sure to download the fixed version that I just posted, since there was a bug in the other one after all.

After running both, I haven't seen one complete path with an entrance and exit so far, but I'm more interested in the 'braid' maze now anyway since that will be more useful for making all kinds of games.

 

I could see people making treasure laden adventure games and things similar to Tutankham and Dark Cavern and Pac-Man-ish games and more with your 'braid' maze.

 

I think many people will use your 'braid' maze to make some cool games. I hope it will be easy to adjust the 'braid' maze so it will have a complete border around it or have an exit or two depending on the kind of game people want to make.

934147[/snapback]

Just to be clear, the second one I posted last night (draw_maze_1a) is still the perfect maze generator. Today I added the code to join the dead ends to nearby passages, but when I run it I get a blank screen, so I've got some debugging to so!

 

Michael Rideout

[+batari]

Just to be clear, the second one I posted last night (draw_maze_1a) is still the perfect maze generator. Today I added the code to join the dead ends to nearby passages, but when I run it I get a blank screen, so I've got some debugging to so!

934662[/snapback]

Could be another bug in bB. If you post the source code I can look at the asm it generates to make sure.

[SeaGtGruff]

Just to be clear, the second one I posted last night (draw_maze_1a) is still the perfect maze generator. Today I added the code to join the dead ends to nearby passages, but when I run it I get a blank screen, so I've got some debugging to so!

934662[/snapback]

Could be another bug in bB. If you post the source code I can look at the asm it generates to make sure.

934715[/snapback]

No, it was a bug in my logic! I've got it working now. But I don't know how good it will be for generating mazes in a game, because there's very little free memory left. I'm sure it could be optimized-- I was more intent on getting it working than squeezing everything together as much as possible. Also, the compiled .asm code could be optimized, and then it might be possible to add it to another program as an include file, as long as the maze is generated first (since it uses 29 variables).

 

Alternately, another algorithm (like the "hunt and kill" method) might take up less memory and use fewer variables, but I'm going to call it quits on mazes for now, so I can get back to working on my tutorial. I'm sure I'll revisit this soon, because I'd like to try making a maze game with it, which means optimizing it first, or else using a different algorithm than the "recursive backtracker."

 

Michael Rideout

draw_maze_2.zip

[SeaGtGruff]

After running both, I haven't seen one complete path with an entrance and exit so far,

934147[/snapback]

I'm not sure I understand what you mean, but I was just thinking that the maze entrance and exit could be used to warp from one side to the other, as in Pac Man, and then it dawned on me that this might be what you meant? That is, are you referring to the entrance and exit being on the same row as each other? In the random mazes, they can be on different rows-- which wouldn't preclude letting the player warp from one to the other, anyway-- but the program could be modified so the entrance and exit are always on the same row.

 

Michael Rideout

[+Random Terrain]

Just to be clear, the second one I posted last night (draw_maze_1a) is still the perfect maze generator.

934662[/snapback]

Oh yeah, I know. I just wanted to let you know that I tried both versions of the same program and didn't see a complete path, but maybe I wasn't looking at it right.

 

 

After running both, I haven't seen one complete path with an entrance and exit so far,

934147[/snapback]

I'm not sure I understand what you mean, but I was just thinking that the maze entrance and exit could be used to warp from one side to the other, as in Pac Man, and then it dawned on me that this might be what you meant? That is, are you referring to the entrance and exit being on the same row as each other? In the random mazes, they can be on different rows-- which wouldn't preclude letting the player warp from one to the other, anyway-- but the program could be modified so the entrance and exit are always on the same row.

934832[/snapback]

A perfect Maze Craze type of maze has a starting position and a complete path to an exit. I was just saying that I didn't see a perfect path from one point to the other, but I'm not too interested in that much anymore if we can have a more open maze that could be used for many types of games.

[vdub_bobby]

I think this is really cool! Good job SeaGtGruff!

 

Here's a couple screenshots.

[supercat]

Alternately, another algorithm (like the "hunt and kill" method) might take up less memory and use fewer variables, but I'm going to call it quits on mazes for now, so I can get back to working on my tutorial. I'm sure I'll revisit this soon, because I'd like to try making a maze game with it, which means optimizing it first, or else using a different algorithm than the "recursive backtracker."

934823[/snapback]

 

Could one use a 'left-hand-rule wander' routine instead of a recursive backtracker? Might be a bit slow, but would save storage. The terminating condition will be the number of line segments drawn.

 

Alternatively, if one regards nodes as being points with X and Y both even, and edges as points where X or Y is odd [points where X and Y are both odd are unused], then if there are 'n' nodes each of which is 'visited' or not, one can start with one node 'visited' and then, iteratively, randomly pick a visited node which is adjacent to at least one unvisited node, connect that node to one of the unvisited nodes (adding the appropriate 'edge'), and repeat. As above, terminate based on the number of line segments drawn.

 

One speedup for the above, btw, is to add a new node classification "boring". A visited node becomes boring if it is randomly selected but there are no unvisited nodes adjacent to it. Boring nodes should be removed from further consideration. Note that because the pixel below and to the right of a node isn't used for anything, that pixel could be used to mark nodes as boring.

[+batari]

Could one use a 'left-hand-rule wander' routine instead of a recursive backtracker?  Might be a bit slow, but would save storage.  The terminating condition will be the number of line segments drawn.

935235[/snapback]

I think it might even be cool to call drawscreen all throughout the generation algorithm so you can see the 2600 working to generate the maze. I don't think it matters even if it takes 10 seconds, as long as we have something to look at during the whole process.

 

That said, the above algorithm, even if very slow, might be a good way to save memory and allow much more time to generate the maze at the same time while giving the player something to watch instead of a blank screen (or flashing colors, a la Maze Craze.)

[SeaGtGruff]

I think this is really cool!  Good job SeaGtGruff!

 

Here's a couple screenshots.

934977[/snapback]

Thanks, I'm glad you like it! And thanks for posting some screenshots, too! I hope other people try out some ideas about how to improve it, like squeezing it down so there'll be enough space left to add some sprites and move them around.

 

Michael Rideout

[SeaGtGruff]

Alternately, another algorithm (like the "hunt and kill" method) might take up less memory and use fewer variables, but I'm going to call it quits on mazes for now, so I can get back to working on my tutorial. I'm sure I'll revisit this soon, because I'd like to try making a maze game with it, which means optimizing it first, or else using a different algorithm than the "recursive backtracker."

934823[/snapback]

 

Could one use a 'left-hand-rule wander' routine instead of a recursive backtracker? Might be a bit slow, but would save storage. The terminating condition will be the number of line segments drawn.

 

Alternatively, if one regards nodes as being points with X and Y both even, and edges as points where X or Y is odd [points where X and Y are both odd are unused], then if there are 'n' nodes each of which is 'visited' or not, one can start with one node 'visited' and then, iteratively, randomly pick a visited node which is adjacent to at least one unvisited node, connect that node to one of the unvisited nodes (adding the appropriate 'edge'), and repeat. As above, terminate based on the number of line segments drawn.

 

One speedup for the above, btw, is to add a new node classification "boring". A visited node becomes boring if it is randomly selected but there are no unvisited nodes adjacent to it. Boring nodes should be removed from further consideration. Note that because the pixel below and to the right of a node isn't used for anything, that pixel could be used to mark nodes as boring.

935235[/snapback]

Go for it! I need to take a break from mazes right now, but now that we see it can be done with bB, other people can find ways to improve it.

 

Michael Rideout

[SeaGtGruff]

Could one use a 'left-hand-rule wander' routine instead of a recursive backtracker?  Might be a bit slow, but would save storage.  The terminating condition will be the number of line segments drawn.

935235[/snapback]

I think it might even be cool to call drawscreen all throughout the generation algorithm so you can see the 2600 working to generate the maze. I don't think it matters even if it takes 10 seconds, as long as we have something to look at during the whole process.

 

That said, the above algorithm, even if very slow, might be a good way to save memory and allow much more time to generate the maze at the same time while giving the player something to watch instead of a blank screen (or flashing colors, a la Maze Craze.)

935265[/snapback]

Well, the mazes are generated pretty quickly-- when I press the left joystick's fire button or the console's reset switch, a new maze pops up in less than a second, and I'm not using a very fast PC. And even the ideas that supercat mentioned will probably run quickly.

 

But what you suggested about drawing the maze as it's being generated is actually part of how I had to debug the program. The other part was using the score to display specific variables while the program was running. For example, while the program was wandering around to unvisited adjacent cells, I was displaying v, x, y, and w at the same time-- v being the first two digits of the score, x being the third digit, y being the fourth digit, and w being the last two digits. Then, when I hit a dead end (no more unvisited adjacent cells), and I had to pop the cell stack and backtrack, I was displaying a (two digits), b (one digit), and c[a] (three digits). Of course, I had to put the display in a loop, and use the fire button to exit the loop and resume the program. It was actually kind of fun.

 

Michael Rideout

[+Random Terrain]

I'm almost done making my own random maze type of thing. Does anyone know the minimum bytes I should have left if I want to add a player sprite and maybe treasure and a monster or some other type of enemy? I'm still crunching the code the best I can. So far I have around 2015 bytes left.

[SeaGtGruff]

I'm almost done making my own random maze type of thing. Does anyone know the minimum bytes I should have left if I want to add a player sprite and maybe treasure and a monster or some other type of enemy? I'm still crunching the code the best I can. So far I have around 2015 bytes left.

937450[/snapback]

Depends on your sprite graphics and what kind of routines you'll be using to move them around, check for and process collisions, etc. I suggest you make a simple test program with the sprites and movement/collision routines you intend to use, and use a simple playfield instead of a maze (i.e., a mesh of horizontal/vertical lines), then you can get that working and see how much memory it will require. Once you have it all debugged and working as desired, make note of how much memory is left, then remove the playfield-drawing routines and recompile it to see how much memory it takes without the playfield (since you'll be doing that part with your maze generator).

 

What kind of algorithm are you using to generate your mazes? Can't wait to see your game!

 

Michael Rideout

[+Random Terrain]

I'm almost done making my own random maze type of thing. Does anyone know the minimum bytes I should have left if I want to add a player sprite and maybe treasure and a monster or some other type of enemy? I'm still crunching the code the best I can. So far I have around 2015 bytes left.

937450[/snapback]

Depends on your sprite graphics and what kind of routines you'll be using to move them around, check for and process collisions, etc. I suggest you make a simple test program with the sprites and movement/collision routines you intend to use, and use a simple playfield instead of a maze (i.e., a mesh of horizontal/vertical lines), then you can get that working and see how much memory it will require. Once you have it all debugged and working as desired, make note of how much memory is left, then remove the playfield-drawing routines and recompile it to see how much memory it takes without the playfield (since you'll be doing that part with your maze generator).

 

What kind of algorithm are you using to generate your mazes? Can't wait to see your game!

937508[/snapback]

Thanks, that's a good idea. My random 'maze' isn't a true maze, so it doesn't really use a special algorithm or anything. I hope to have it cleaned up enough for people to see by tomorrow. I'll throw in a sprite you can move around so it won't be so boring. Since it might turn into a game called 'RUINS' I'll create a new thread for it tomorrow.

[+Random Terrain]

OK, I now have a small sprite that you can move around the 'maze.' It doesn't go through walls anymore or move diagonally, so that nightmare is over. Do you want me to post what I have or should I wait a little longer so that I have time to smooth out the movement and add some type of treasure, an enemy, and sound?

 

And whatever the answer, can we post .bas and .bin files directly or do we have to zip them?

[SeaGtGruff]

OK, I now have a small sprite that you can move around the 'maze.' It doesn't go through walls anymore or move diagonally, so that nightmare is over. Do you want me to post what I have or should I wait a little longer so that I have time to smooth out the movement and add some type of treasure, an enemy, and sound?

 

And whatever the answer, can we post .bas and .bin files directly or do we have to zip them?

938550[/snapback]

 

(1) If you think you might get some comments that could give you ideas for your game, then I'd say go ahead and post what you've got so far.

 

(2) I don't know if there's any "rules," but I like to zip the .bas and .bin together, since it makes it easier for people to download both of them in one shot, and takes up less memory.

 

Michael Rideout

[+Random Terrain]

(1) If you think you might get some comments that could give you ideas for your game, then I'd say go ahead and post what you've got so far.

I think I will wait until the next part is done first since a few people might like the surprise. I hope I will be done with that part today. I can't believe how hard it was to figure out how to move a sprite around a maze. Now that hard part is over, the rest might be a little easier.

 

 

(2) I don't know if there's any "rules," but I like to zip the .bas and .bin together, since it makes it easier for people to download both of them in one shot, and takes up less memory.

If the forum accepts them, I think I'll do them individually since these files are small anyway. It will be easier for me and on the other side of it, I always like to download files that are not zipped because zipping creates one more step to slow me down.