Random maze possible with batari Basic?

[+Random Terrain]

I promise that I will try to make something semi-original one of these days, but while I'm still learning and scraping the rust off of what little BASIC skills I still have left, it would be cool to have a Maze Craze-type random maze I could play with using batari Basic.

 

Most of the old BASIC code I have in books and magazines and have seen on the Internet for creating random mazes looks kind of long and too hard to convert. Do one of you math geniuses know how to make a Maze Craze-type random maze using Playfield Pixels? If you do, I'd like to use it for making a couple of test programs.

 

Thanks.

[SeaGtGruff]

I promise that I will try to make something semi-original one of these days, but while I'm still learning and scraping the rust off of what little BASIC skills I still have left, it would be cool to have a Maze Craze-type random maze I could play with using batari Basic.

 

Most of the old BASIC code I have in books and magazines and have seen on the Internet for creating random mazes looks kind of long and too hard to convert. Do one of you math geniuses know how to make a Maze Craze-type random maze using Playfield Pixels? If you do, I'd like to use it for making a couple of test programs.

 

Thanks.

928793[/snapback]

 

I don't know anything about the routine that does it, but the "A.D.O.M." adventure game has a great random maze generator. If the code it's based on is in the public domain, perhaps it could be adapted for bB. (I don't mean the code for A.D.O.M., which I don't think is in the public domain, but the random maze generation logic that the A.D.O.M. programmer used as a starting point.)

 

Michael Rideout

[+Random Terrain]

I don't know anything about the routine that does it, but the "A.D.O.M." adventure game has a great random maze generator. If the code it's based on is in the public domain, perhaps it could be adapted for bB. (I don't mean the code for A.D.O.M., which I don't think is in the public domain, but the random maze generation logic

928830[/snapback]

Thanks. I couldn't find much about that, but I did find the following pages.

 

Public Domain code:

http://www.powerbasic.com/support/forums/F...TML/001717.html

 

 

Tutorials/explanations:

http://www.mazeworks.com/mazegen/mazetut/

 

http://en.wikipedia.org/wiki/Maze_generation_algorithm

 

http://www.ii.uni.wroc.pl/~wzychla/maze_en.html

 

http://www.cc.gatech.edu/~shivers/mazes.html

 

http://www.pmms.cam.ac.uk/~gjm11/programs/maze/

 

 

Is anyone interested in random mazes who can understand any of that and turn it into bB code?

[SeaGtGruff]

I don't know anything about the routine that does it, but the "A.D.O.M." adventure game has a great random maze generator. If the code it's based on is in the public domain, perhaps it could be adapted for bB. (I don't mean the code for A.D.O.M., which I don't think is in the public domain, but the random maze generation logic

928830[/snapback]

Thanks. I couldn't find much about that, but I did find the following pages.

 

Public Domain code:

http://www.powerbasic.com/support/forums/F...TML/001717.html

 

 

Tutorials/explanations:

http://www.mazeworks.com/mazegen/mazetut/

 

http://en.wikipedia.org/wiki/Maze_generation_algorithm

 

http://www.ii.uni.wroc.pl/~wzychla/maze_en.html

 

http://www.cc.gatech.edu/~shivers/mazes.html

 

http://www.pmms.cam.ac.uk/~gjm11/programs/maze/

 

 

Is anyone interested in random mazes who can understand any of that and turn it into bB code?

929142[/snapback]

 

I saw the MazeWorks page, too, and am studying how to adapt the DFS algorithm to bB. There isn't enough variable space to do it as described, but I think we can leave out the array for the "border" (since the maze will always be rectangular), and use the playfield pixels themselves for the "walls" array (i.e., for any given cell, we can use the pfread function on its neighboring playfield pixels to see if any of the walls around it have been knocked down yet). So that would mean we'd need only a "solution" array and a "backtrack" array. But even that requires more variable memory than we have, not to mention the need to store the cells on the stack, which isn't nearly big enough for that. In short, it will be tricky to implement a DFS algorithm in bB, but I'm going to see if I can do it!

 

Keep in mind that with the playfield pixels as provided by bB, our maze would be only 7 cells across and 5 cells down-- at least, if the cells are going to be square. There are 11 rows of playfield pixels, but every other row has to be used for the walls, so that gives us 6 rows for the walls, and 5 rows for the cells. And there are 32 columns of playfield pixels, but we want to take two at a time for each wall or cell, so they're square-- giving us 16 columns of "double-wide" playfield pixels. As with the rows, every other column must be used for the walls, so that gives us 8 columns for the walls, and 8 columns for the cells-- but the last column of cells isn't part of the maze itself, it will be the "exit" column (the same way that Maze Craze uses the last column of playfield pixels for the exit). With a 7-by-5 maze grid, the resulting maze won't be terribly challenging.

 

This is what the grid would look like before any walls are knocked down to form a maze:

 

  COLUBK = $94 : rem * The background (paths) will be blue
  COLUPF = $00 : rem * The playfield (walls) will be black
  rem * First we draw a grid of walls and cells
  rem * The maze has 7 cells across and 5 cells down
  rem * The last (8th) column of cells will be the maze exit
  rem * Draw the horizontal walls
  for y = 0 to 10 step 2
     pfhline 0 y 29 on
  next
  rem * Draw the vertical walls
  for x = 0 to 28 step 4
     t = x + 1
     pfvline x 0 10 on
     pfvline t 0 10 on
  next
loop
  drawscreen
  goto loop

 

 

And here is an example of what a maze might look like:

 

  COLUBK = $94 : rem * The background (paths) will be blue
  COLUPF = $00 : rem * The playfield (walls) will be black
  rem * First we draw a grid of walls and cells
  rem * The maze has 7 cells across and 5 cells down
  rem * The last (8th) column of cells will be the maze exit
  rem * Draw the horizontal walls
  for y = 0 to 10 step 2
     pfhline 0 y 29 on
  next
  rem * Draw the vertical walls
  for x = 0 to 28 step 4
     t = x + 1
     pfvline x 0 10 on
     pfvline t 0 10 on
  next
  rem * Now we knock down some walls to make paths
  pfpixel 4 1 off : pfpixel 5 1 off
  pfpixel 8 1 off : pfpixel 9 1 off
  pfpixel 12 1 off : pfpixel 13 1 off
  pfpixel 16 1 off : pfpixel 17 1 off
  pfpixel 28 1 off : pfpixel 29 1 off
  pfpixel 2 2 off : pfpixel 3 2 off
  pfpixel 6 2 off : pfpixel 7 2 off
  pfpixel 22 2 off : pfpixel 23 2 off
  pfpixel 26 2 off : pfpixel 27 2 off
  pfpixel 12 3 off : pfpixel 13 3 off
  pfpixel 16 3 off : pfpixel 17 3 off
  pfpixel 24 3 off : pfpixel 25 3 off
  pfpixel 2 4 off : pfpixel 3 4 off
  pfpixel 6 4 off : pfpixel 7 4 off
  pfpixel 10 4 off : pfpixel 11 4 off
  pfpixel 14 4 off : pfpixel 15 4 off
  pfpixel 18 4 off : pfpixel 19 4 off
  pfpixel 22 4 off : pfpixel 23 4 off
  pfpixel 8 5 off : pfpixel 9 5 off
  pfpixel 2 6 off : pfpixel 3 6 off
  pfpixel 14 6 off : pfpixel 15 6 off
  pfpixel 22 6 off : pfpixel 23 6 off
  pfpixel 26 6 off : pfpixel 27 6 off
  pfpixel 4 7 off : pfpixel 5 7 off
  pfpixel 12 7 off : pfpixel 13 7 off
  pfpixel 20 7 off : pfpixel 21 7 off
  pfpixel 24 7 off : pfpixel 25 7 off
  pfpixel 6 8 off : pfpixel 7 8 off
  pfpixel 10 8 off : pfpixel 11 8 off
  pfpixel 26 8 off : pfpixel 27 8 off
  pfpixel 4 9 off : pfpixel 5 9 off
  pfpixel 12 9 off : pfpixel 13 9 off
  pfpixel 16 9 off : pfpixel 17 9 off
  pfpixel 20 9 off : pfpixel 21 9 off
  pfpixel 24 9 off : pfpixel 25 9 off
loop
  drawscreen
  goto loop

 

 

As you can see, a 7-by-5 grid doesn't allow for a very complicated maze.

 

Michael Rideout

[+Random Terrain]

In short, it will be tricky to implement a DFS algorithm in bB, but I'm going to see if I can do it!

Cool. If you you find a way to do squeeze out everything that isn't necessary to create a small random maze, I hope to have enough room left over to experiment with a creature wandering the maze and so on. With various tricks, shortcuts, and Bit Operations, I'm sure you'll find a way.

 

 

As you can see, a 7-by-5 grid doesn't allow for a very complicated maze.

The small size wouldn't be a problem for me since I hate super-complicated mazes anyway.

 

I just had an idea. My original thought was to have a starting and ending point just like Maze Craze, but if it would help you out any (cut down on the complexity and need for things such as a 'solution array'), just having a random maze that is somewhere between a Maze Craze maze and a Pac-Man maze would be great.

 

On another subject I guess I was starting out all wrong. This is what I started with:

[SeaGtGruff]

On another subject I guess I was starting out all wrong. This is what I started with:

929179[/snapback]

 

That looks a lot like what I posted, except you aren't using double-wide playfield pixels. That's okay, if you don't mind that the vertical walls and pathways will be about half as wide as the horizontal walls and pathways. With that size, you could get 5 rows going down and 15 columns going across.

 

The other difference is that your colors are different, and the fact that you used a black background suggests that maybe you were aiming at using the background for the pathways, and the playfield for the walls. If you did that, you could get 6 rows down and 16 columns across with single-wide playfield pixels, or 8 columns across with double-wide playfield pixels. However, the player movement would be trickier to handle.

 

By using the playfield for the walls, you can just let the player run into the walls (as I do in "Reventure"), and bump it back whenever you detect that a collision between the player and the playfield has occurred. That keeps the logic simpler to program, but it also adds a possible irritation for the gamer if his/her player keeps bumping into the wall and getting hung up. On the other hand, you could work that into the game. For example, if the player is a car, and the pathways are roads, then bumping into a wall would be like running into a concrete divider, which would probably slow the driver down, as well as damage the car. So if the player collided with a wall, you could take away points or something. But whether or not you take away points for bumping into the walls, avoiding the walls to keep from getting hung up would become part of the gameplay.

 

If you use the playfield for the pathways, you won't be able to use the collisions to keep the player on the pathways, which means you'll need to keep track of where the player is (which you'll be doing anyway, with the variables you'll be using to store/control the player0x and player0y values), and then use if-thens to check if it's okay for the player to move forward, or if a wall's there. From what I've read in the "homebrew" forum about maze movement in games like "Pacman," it seems that that's what they do. With a random maze, you won't know in advance where the walls are, but you could use the pfread function to check the space in front of the player-- in whatever direction the player is moving in-- and prevent the player from moving forward if a wall is detected (i.e., if the playfield pixel that the player would be moving into is off). That would be easy to do, but you'd need to convert the location that the player is about to move into to the equivalent playfield pixel coordinates, since the player's movement would be only a fraction of a playfield pixel (i.e., the player might be moving forward within the same playfield pixel that it's already located in). The only tricky part I see there would be needing to pay attention to the direction the player is moving in, and factor in the player's size, since the player0x and player0y coordinates will be the position of the bottom left corner of the player. Thus, if a single-wide player is moving right (and assuming all 8 of the player's pixels are being used), you'd need to add 8 to the variable that gives the player0x value, and check to see if that target pixel is on or off. Or, if the player is moving up (and supposing the player is 8 double-scanlines tall), you would need to subtract 8 from the variable that gives the player0y value to see which playfield pixel to test.

 

Michael Rideout

[+Random Terrain]

By using the playfield for the walls, you can just let the player run into the walls (as I do in "Reventure"), and bump it back whenever you detect that a collision between the player and the playfield has occurred. That keeps the logic simpler to program, but it also adds a possible irritation for the gamer if his/her player keeps bumping into the wall and getting hung up. On the other hand, you could work that into the game. For example, if the player is a car, and the pathways are roads, then bumping into a wall would be like running into a concrete divider, which would probably slow the driver down, as well as damage the car. So if the player collided with a wall, you could take away points or something. But whether or not you take away points for bumping into the walls, avoiding the walls to keep from getting hung up would become part of the gameplay.

Understanding that I am rusty and I never was the greatest BASIC programmer, so I'm often more wrong than right, it seems like as long as you know how big the sprite is and its position, instead of using regular collision, you could check using pfread in the direction of attempted movement. There should be no hang ups, just smooth Pac-Man-like movement for the player and any 'monsters'.

[SeaGtGruff]

Understanding that I am rusty and I never was the greatest BASIC programmer, so I'm often more wrong than right, it seems like as long as you know how big the sprite is and its position, instead of using regular collision, you could check using pfread in the direction of attempted movement. There should be no hang ups, just smooth Pac-Man-like movement for the player and any 'monsters'.

929288[/snapback]

 

Yeah, that's about what I said, but in many more unnecessary words! So I've been working on a 6x8 maze using the playfield for the pathways instead of the walls. And I've got to tell you, trying to do a DFS routine in bB is kicking my butt big time! I thought I had it all figured out, but I haven't made it work yet, it does all sorts of crazy things. I'm sure it's probably a "simple" mistake in my code, but the problem is eluding me. Whenever I finally get the random maze generation working, I'll throw in a sprite and move it around using pfread to check for walls, but right now all I can say is... OH... MY... GAWD! When I post the final code (if I don't have a nervous breakdown first), you'll see what I mean!

 

Michael Rideout

[+Random Terrain]

Yeah, that's about what I said, but in many more unnecessary words!

Oh yeah, you did mention that. I glazed over that part and thought you were just talking about using pfread while creating the maze.

I'm not so stupid then, I just can't read.

 

 

Whenever I finally get the random maze generation working, I'll throw in a sprite and move it around using pfread to check for walls, but right now all I can say is... OH... MY... GAWD! When I post the final code (if I don't have a nervous breakdown first), you'll see what I mean!

I'm glad I'm not working on the maze code then, because if you're having trouble, I'd probably melt my computer.

 

Thanks for working on it. I'm sure more people are interested in this besides me, they just aren't posting here yet.

[SeaGtGruff]

Whenever I finally get the random maze generation working, I'll throw in a sprite and move it around using pfread to check for walls, but right now all I can say is... OH... MY... GAWD! When I post the final code (if I don't have a nervous breakdown first), you'll see what I mean!

I'm glad I'm not working on the maze code then, because if you're having trouble, I'd probably melt my computer.

 

Thanks for working on it. I'm sure more people are interested in this besides me, they just aren't posting here yet.

929678[/snapback]

I haven't got all the bugs out yet-- and at least one bug was coming from bB, and it drove me crazy until I realized it was a bug and compensated for it-- but here's what I have so far. Most of the time it will work as intended, but once in a while it does stuff it shouldn't, like leave one or more single cells disconnected from the maze, or connect a few cells together but leave them disconnected from the rest of the maze, or other strange things (like turning playfield pixels on or off where it shouldn't).

 

After I got it mostly working, I tried adding a few additional variables, but since I'd used up all 26, I had to use three bytes from the playfield with the dim command. The extra dimmed variables were supposed to vary the length of the pathways, as long as there are multiple directions to choose from. But I took the extra variables out, because they seemed to freak out the program sometimes.

 

The starting cell is on the left, and has a little extra block in front of it so it juts out a little further than the others-- as does the exit, which is on the right.

 

Press restart to draw a new maze. Once in a while the screen may go whacko, and no amount of resetting will fix it, in which case you'll just have to stop the program and start it over. I noticed that it seems to repeat a number of patterns at times, due to the way the random numbers work in bB. It seems like the program may start with a unique maze, but once you start to use reset to draw a new maze, it tends to get into a loop, repeating the same patterns (but the first pattern might not be one of the ones in the loop). I've played around with the way the variables are randomized to see if I can break the loop, but so far it either makes it worse (more likely to go whacko), or else doesn't seem to make any difference.

 

There are different types of algorithms for drawing "perfect" random mazes, but this program is based on the "depth-first search" method, apparently also known as "backtracking." According to one web site I found-- by Walter Pullen, who has a really cool freeware maze program-- there is one method known as "hunt and kill" that uses little or no memory, so I might try that algorithm if I can find a good description of it. (Walter Pullen either still works, or used to work, at Microsoft, and I was already familiar with him through a freeware astrology program he wrote-- astrology being one of my other life-long hobbies.) That site is www.astrolog.org, then you should navigate to the pages about mazes and labyrinths. He has a very lengthy description of different types of mazes, and it's a great resource if you're interested in mazes, so I recommend it.

 

The depth-first search works by picking a random starting cell, then looking for a neighbor that hasn't been "visited" yet. If such a neighboring cell exists, then the wall between the two cells is knocked down, and the neighbor becomes the new current cell. If the current cell has no unvisited neighbors, then the current cell is popped off of the stack, and you backtrack through the cells you've already done until you find one that still has an unvisited neighbor, and repeat the process until all of the cells have been visited.

 

Given the limited number of variables (the stack would need to be up to 48 bytes for a 6-by-8 maze), I came up with the following scheme: The stack is 12 bytes long, with each byte holding up to 4 cells. Rather than storing the position of the cell on the stack, I'm storing a 2-bit value (0, 1, 2, or 3) to remember the direction taken to reach the cell (0=north, 1=east, 2=south, and 3=west). So when I pop a cell off of the stack so I can return to the previous cell, I check the direction that was taken, and go in the opposite direction (i.e., if I went north to get to the cell that's on top of the stack, then I go south to return to the previous cell, and adjust the stack accordingly). And I'm using a 6-byte array to keep track of which cells have been visited, one bit per cell (0=unvisited, 1=visited). This worked out nicely for a 6-by-8 cell grid, because each byte of the visited-cell array corresponds to one row of the maze!

 

My original code had a lot of comments in it, but I removed all of the comments to reduce the length of the printout while I was debugging it, so the code is probably hard to follow. When I'm finished working out all the kinks, I'll put the comments back in to explain everything that's going on.

 

And once the maze generation is bug-free, I intend to throw in a sprite or two and move them around using the pfread function to keep it on the paths. I also thought about generating a new maze once the player reaches the exit (i.e., the exit and maybe also the entrance of the maze leads to another maze), so the "game" just keeps going as long as the player doesn't get captured by a monster. But right now I'm more focused on getting the maze generation down pat. I especially want to try some other algorithms, because the depth-first search or backtracking tends to produce longer pathways and fewer branches, and the mazes ought to be more interesting if there are shorter pathways and more branches.

 

Michael Rideout

drawmaze2.zip

[supercat]

Most of the old BASIC code I have in books and magazines and have seen on the Internet for creating random mazes looks kind of long and too hard to convert. Do one of you math geniuses know how to make a Maze Craze-type random maze using Playfield Pixels? If you do, I'd like to use it for making a couple of test programs.

928793[/snapback]

 

Is it really USEFUL to create a "perfect" maze? It would seem to me that it would be much more interesting to have mazes that were somewhat more open. The approach I would tend to favor would be to have some "maze pieces" that are assembled in random fashion. Then check to ensure there aren't any inappropriate islands (unless the game is such that islands aren't a problem) and fix them. Challenging on the 2600, but probably not impossible.

[+Random Terrain]

Is it really USEFUL to create a "perfect" maze?  It would seem to me that it would be much more interesting to have mazes that were somewhat more open.  The approach I would tend to favor would be to have some "maze pieces" that are assembled in random fashion.  Then check to ensure there aren't any inappropriate islands (unless the game is such that islands aren't a problem) and fix them.  Challenging on the 2600, but probably not impossible.

I did say this in a later post:

 

I just had an idea. My original thought was to have a starting and ending point just like Maze Craze, but if it would help you out any (cut down on the complexity and need for things such as a 'solution array'), just having a random maze that is somewhere between a Maze Craze maze and a Pac-Man maze would be great.

[SeaGtGruff]

Is it really USEFUL to create a "perfect" maze?  It would seem to me that it would be much more interesting to have mazes that were somewhat more open.  The approach I would tend to favor would be to have some "maze pieces" that are assembled in random fashion.  Then check to ensure there aren't any inappropriate islands (unless the game is such that islands aren't a problem) and fix them.  Challenging on the 2600, but probably not impossible.

930991[/snapback]

I had the same thought before I started tackling the "perfect" maze algorithm-- that putting together a maze out of different possible pieces might be the way to go. "Perfect" mazes certainly seem to be boring when they're small (e.g., 6x8), although Maze Craze did it really well with the grid size it used-- more than 6x8, since it wasn't limited by bB's playfield pixel size.

 

Anyway, I'd still like to figure out a way to get a nice "perfect" maze in bB, but I think a different algorithm than DFS (depth-first search) might produce more interesting mazes. My attempts to limit the "run" size (how long a pathway can run straight in the same direction) did help, but caused to many problems with the screen display for it to be reliable until I can work out all the bugs.

 

I did feel a little vindicated by playing with Walter Pullen's program, though, since setting the maze size in that program to 6x8 or 8x6 produced results very similar to what I get from my program. The only real problem-- aside from the length of the pathways-- is that bB's random numbers aren't random enough, so the mazes tend to get into a loop. I'm experimenting with different ways to work around that, but the results so far are too unreliable to be useful (i.e., the screen tends to go whacko more often).

 

Michael Rideout

[+Random Terrain]

Thanks again for working on this.

 

I haven't got all the bugs out yet-- and at least one bug was coming from bB, and it drove me crazy until I realized it was a bug and compensated for it. . .

What was that bug? Are you going to report it or has it already been reported by someone else?

 

 

I especially want to try some other algorithms, because the depth-first search or backtracking tends to produce longer pathways and fewer branches, and the mazes ought to be more interesting if there are shorter pathways and more branches.

Oh yeah, since the Maze Craze idea with smaller mazes doesn't sound like such a good idea, having the maze more open would be nice. The 'maze piece' idea that supercat posted might be a good alternative too and it's probably something every person who has played Pac-Man has thought about. I wondered about doing it on the VIC-20 a long time ago, but I moved on to other things.

 

I wondered if it was possible to make pieces that 'fit' the other pieces no matter what, so you wouldn't have to do any checking or cleanup. There might not be enough room with bB to do that though. Probably have to save that for a PC BASIC-style language where I'd have more room. If Cobra ever comes out and I buy it, I'll see if I can remember to try the idea.

 

Too bad a maze can't be grown similar to fractals or cellular automata or something like that so that there would no longer be a need for a ton of variables and so on.

 

I think most bB users would be happy with a more open maze that was randomly created. Think of all the maze games people could make for the fun of it. If the maze creation code could be cut down to a few lines because of some ingenuous algorithm, people would fight each other over who would be first to give you a medal.

[SeaGtGruff]

I haven't got all the bugs out yet-- and at least one bug was coming from bB, and it drove me crazy until I realized it was a bug and compensated for it. . .

What was that bug? Are you going to report it or has it already been reported by someone else?

931004[/snapback]

It was where I was checking for unvisited cells in the four directions, which uses bit evaluations like this:

 

if x = 4 && !z{5} then check_south

 

That line says that if we're in the 5th column (x = 4, since the first column is where x = 0), and if the bit for the 6th column is already on (!z{5}), then the eastern neighbor has already been visited, so check the southern neighbor to see if it's still unvisited. Well, I thought that "if z{5}" meant "yes, z{5} is on (=1)," but I had to use "!z{5}" instead. Okay, so I added "!" in front of all the ones that needed it, but then these wouldn't work:

 

if x = 5 && !z{6} then check_south

if x = 6 && !z{7} then check_south

 

In those lines, "!z{6}" and "!z{7}" seemed to mean the opposite from in the other lines, so I had to take out the "!" for those lines! I tried to do some simple test programs to verify the behavior, but in my test programs, it seemed to work okay, yet it would not work okay in the maze program. What it was doing was drawing a 6x6 maze every time, even though all the cells in the 7th and 8th columns were unvisited! And oddly enough, I did't get any flaky results with a 6x6 maze, it's only with an 8x6 maze that the flakiness starts.

 

I especially want to try some other algorithms, because the depth-first search or backtracking tends to produce longer pathways and fewer branches, and the mazes ought to be more interesting if there are shorter pathways and more branches.

Oh yeah, since the Maze Craze idea with smaller mazes doesn't sound like such a good idea, having the maze more open would be nice. The 'maze piece' idea that supercat posted might be a good alternative too and it's probably something every person who has played Pac-Man has thought about. I wondered about doing it on the VIC-20 a long time ago, but I moved on to other things.

 

I wondered if it was possible to make pieces that 'fit' the other pieces no matter what, so you wouldn't have to do any checking or cleanup. There might not be enough room with bB to do that though. Probably have to save that for a PC BASIC-style language where I'd have more room. If Cobra ever comes out and I buy it, I'll see if I can remember to try the idea.

 

Too bad a maze can't be grown similar to fractals or cellular automata or something like that so that there would no longer be a need for a ton of variables and so on.

 

I think most bB users would be happy with a more open maze that was randomly created. Think of all the maze games people could make for the fun of it. If the maze creation code could be cut down to a few lines because of some ingenuous algorithm, people would fight each other over who would be first to give you a medal.

931004[/snapback]

No medals, please, but I do want to try the other algorithms, especially the "hunt and kill" method that's supposed to work using no extra memory (presumably, no stack and no visited-cells array). That even sounds like an appropriate name for a maze-generation method to use in a videogame!

 

Michael Rideout

[SeaGtGruff]

Okey-day, me's a bein' finished with the #@!*%! maze program, and me's brain's a bein' goners!

 

This is version 1.0, since the version I posted before was buggy, and this is the first bug-free version. It was a bear to debug, but it was also kind of fun (in a painful learning-experience kind of way), because I had to use the score to display all of the debug information, three or four variables at a time!

 

This version still draws a "perfect" maze, which isn't very much fun to solve with such a small grid, but I'm going to use this program to create another one called draw_maze_2, which will draw a "braid" maze by connecting all of the dead ends to adjacent passages. For a videogame where the player has to navigate a maze, collecting things and avoiding monsters, a "braid" maze is the way to go. For a "perfect" maze to be any fun, it really needs to have a larger grid so there are more passages to navigate, and maybe involve some kind of race, as in the "Atari Maze Craze" game.

 

The actual code isn't that long, but the program listing is rather lengthy because I added lots of comments to make it easier to understand, just in case anyone is foolish enough to try!

 

The "instructions" are in the program listing, but to save everyone the trouble of actually looking at the code, pressing the left joystick's fire button will draw the next maze in the sequence, or pressing the console's reset switch will restart the sequence with a new random value. In theory, the program can draw 255 mazes, but it's possible (if not highly probable) that some of the random number seeds will produce identical mazes as each other, so the actual number of distinct mazes that the program will draw could very well be less than 255.

 

I discovered a couple of bugs in batari BASIC while working on this program. One is the bit test bug that I documented in the "bugs" thread. The other one also has to do with bits, because statements like the following don't seem to work:

 

a{4} = b{4}

 

I didn't try to understand the way it compiles (PHP? PLP? Why?), but I think it can be done in fewer bytes and machine cycles as follows:

 

; var1{bit1} = var2{bit2}

 

LDA var2

AND #bit2_value (e.g., bit 4 would be #16)

TAX

LDA var1

AND #negative_bit1_value (e.g., bit 4 would be #240)

STA var1

TXA

ORA var1

STA var1

 

Also, it would have been easier to write the program if variables could be used in bit operations, or if bit operations could be used with arrays, as follows:

 

a{b} = 1

if c[d]{e} then go_there

 

I'll gladly contribute anything I can toward getting those sorts of things added to future versions of batari BASIC.

 

Anyway, I can't blame my difficulties on those things, because I had booboos and brain farts aplenty, like sticking a return at the end of an if when it was supposed to be on the next line by itself, not to mention all the troubles I had with the "cell stack"-- particularly when popping values off the "cell stack" and then backtracking to the previous cell's coordinates, which is why the version I posted before would go all flakey at times.

 

I don't know how useful this code will be to anyone, but the basic logic could be adapted to a larger maze grid, which would create more interesting mazes. And given more RAM space (such as with a RAM-added bankswitching method), it might be kind of neat to create a random "perfect" maze using the basic "DFS" logic, store it in memory (rather than displaying it with the playfield), and then using the stored maze pattern to display a 3D first-person view, as in "Escape from the Mind Master" or (shudder) "Crypts of Chaos."

 

The "braid" maze program that I'm going to do next should be much more useful. Since it's going to basically be the "perfect" maze program with an extra routine to join the dead ends to other passages, I'll probably remove most of the comments, unless you think I should leave them in?

 

I don't want to spend too much more time on maze programs, because it's kept me from working on my planned tutorial. But with all the fun I've been having, I couldn't resist!

 

Michael Rideout

 

Dammit, I jinxed myself by saying it was bug-free! I was just running it again, stepping through the mazes, when I noticed that maze #63 had no exit. I've just fixed it to be sure the maze exit gets created, whether or not all 48 cells have already been visited. So now maze #63 has an exit.

draw_maze_1.zip

draw_maze_1a.zip

Edited September 19, 2005 by SeaGtGruff

[supercat]

; var1{bit1} = var2{bit2}
LDA var2
AND #bit2_value (e.g., bit 4 would be #16)
TAX
LDA var1
AND #negative_bit1_value (e.g., bit 4 would be #240)
STA var1
TXA
ORA var1
STA var1

 

Assuming bit1 and bit2 are in the same bit location, that might work. Can be shrunk further, though:

 lda var2
 and #bit2_mask
; Insert ASL's, LSR's, ROL's, or ROR's as needed here to move bit to proper spot
 eor var1
 and #bit2_mask
 eor var1
 sta var1

More compact and faster, I think. For the bit-shifting part, the cases of 1-3 bits can be most easily done with ASL/LSR. Four or more bits gets interesting. Some examples (note: these require pre-masking):

; Move from bit 7 to bit 0
 asl
 rol
; Move from bit 7 to bit 1
 asl
 rol
 asl
; Move from bit 7 to bit 3 (or any bit)
 asl
 adc #7
 and #8
; Move from bit 2 to bit 7 (any bit except 0, going upward)
 adc #$7C  ; Note: Carry-in is irrelevant
 and #$80
; Move from bit 0 to bit 7
 lsr
 ror
; Move from bit 0 to bit 6
 lsr
 ror
 lsr
; Move from bit 0 to bit 5 (bit 0 to any bit)
 clc
 adc #$1F
 and #$80
; Move from bit 6 to bit 3 (any bit, moving downward)
 cmp #1 ; Generate carry if bit is set
 adc #$07
 and #8

I think that's all the non-obvious cases that require different code. Note that the case of bit 0 to bit 6 can be done using 3 bytes in six cycles (as illustrated) or 4 bytes in four cycles (using the general case).

[supercat]

[duplicate post deleted]

Edited September 19, 2005 by supercat

[+Random Terrain]

The "braid" maze program that I'm going to do next should be much more useful. Since it's going to basically be the "perfect" maze program with an extra routine to join the dead ends to other passages, I'll probably remove most of the comments, unless you think I should leave them in?

 

I don't want to spend too much more time on maze programs, because it's kept me from working on my planned tutorial. But with all the fun I've been having, I couldn't resist!

934082[/snapback]

Thanks for working on this and for working on the 'braid' maze. The 'braid' maze will be more useful for making most games. Whether people use it for Pac-Man type games or adventure games, having a random 'braid' maze will make the games more fun. I love games that seem to have never-ending replayability. It's hard to get sick of a maze when it's different every time you play.

 

About comments: If they are ignored when the game is compiled, seems like a good idea to leave them in.

 

Thanks again.

Edited September 19, 2005 by Random Terrain

[SeaGtGruff]

The "braid" maze program that I'm going to do next should be much more useful. Since it's going to basically be the "perfect" maze program with an extra routine to join the dead ends to other passages, I'll probably remove most of the comments, unless you think I should leave them in?

 

I don't want to spend too much more time on maze programs, because it's kept me from working on my planned tutorial. But with all the fun I've been having, I couldn't resist!

934082[/snapback]

Thanks for working on this and for working on the 'braid' maze. The 'braid' maze will be more useful for making most games. Whether people use it for Pac-Man type games or adventure games, having a random 'braid' maze will make the games more fun. I love games that seem to have never-ending replayability. It's hard to get sick of a maze when it's different every time you play.

 

About comments: If they are ignored when the game is compiled, seems like a good idea to leave them in.

 

Thanks again.

934127[/snapback]

 

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.

 

Michael Rideout

[+Random Terrain]

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.

[+batari]

The other one also has to do with bits, because statements like the following don't seem to work:

 

a{4} = b{4}

 

I didn't try to understand the way it compiles (PHP? PLP? Why?)

The bit to bit assignment was kind of an afterthought... basically a quick hack because I got the request only days before the 0.30a release. I guess it's not terribly surprising that it doesn't work, though I had hoped it would. The bug is minor, but the code is such a bad hack that I should probably change it to something like you suggested.

Also, it would have been easier to write the program if variables could be used in bit operations, or if bit operations could be used with arrays, as follows:

 

a{b} = 1

if c[d]{e} then go_there

934082[/snapback]

I can probably do this eventually. I have to put bB aside for a couple of weeks due to work-related stuff, but I will get back to it. For now, we'll let the bug reports and feature requests pile up a little, but lately they have been trickling in, so by then I should have enough to keep me busy.

[+batari]

I think that's all the non-obvious cases that require different code.  Note that the case of bit 0 to bit 6 can be done using 3 bytes in six cycles (as illustrated) or 4 bytes in four cycles (using the general case).

934124[/snapback]

I'll put these on the todo list as well. It's better to produce optimal code if we can instead of just the same general routine for everything.

[supercat]

I'll put these on the todo list as well.  It's better to produce optimal code if we can instead of just the same general routine for everything.

934166[/snapback]

 

I just realized that the routines I posted aren't really optimal for time or space . The AND which follows the first EOR is necessary even if the bit is premasked, and so other bits won't matter. Plus, the LSR/ASL instructions are compact, so from a code-size perspective there's not too much wrong with

 LDA src
; Insert 0-4 ROL or ROR instructions here
; When the bit needs to move 5 or more places, rotate in the opposite
; direction by 9-# bits.
 EOR dest
 AND #dest_mask
 EOR dest
 STA dest

 

This will probably end up being optimal for space in every instance. For some bit moves, other approaches may be faster but require more code. And if you do the rotates in the "shortest direction", the time required to do four rotates is not bad in any case.

[vdub_bobby]

Very nice random maps! This is very cool!