Author Topic: Maze algorithm help (Read 5946 times)

Scipi · « **on:** August 04, 2011, 09:09:51 pm »

I am working on a small maze game and I am hitting a roadblock in generating a random maze. I'm trying to implement the depth first algorithm but I'm unsure how to even start. Can someone come up with some code or help me with the overall programming logic to generate the maze?

Thanks.

calcdude84se · « **Reply #1 on:** August 04, 2011, 09:22:03 pm »

Here's a page full of maze generation algorithms: http://www.astrolog.org/labyrnth/algrithm.htm
Eller's algorithm is cool because it only needs to store data for one row of the maze.
Edit: If you're any good at reading BASIC code, I do have a program that implements Eller's algorithm. Lemme find its topic...
Edit 2: Found it. http://ourl.ca/8028

Scipi · « **Reply #2 on:** August 04, 2011, 09:43:04 pm »

I tried looking at you code, but I couldn't figure it out. I'm pretty bad at reading code sometimes.

What was the general logic you used in that program to actually generate the maze? I looked at the site and I can't quite figure out how to implement it in a program.

calcdude84se · « **Reply #3 on:** August 04, 2011, 10:35:17 pm »

Nah, it'd take me a bit too to remember how it works

As for the general logic:

Create two arrays the width of the maze (in cells). Call them, say, NEW and OLD.
For the first row, connect each cell to the one on its left with a given probability. Each member in a set of connected cells should have the same value at its index in array OLD.
For each subsequent row:
- For each set of connected cells from the previous row:
  - Choose one cell from it and connect it downwards.
  - Set that cell's value in array NEW the same as in array OLD
- For each cell in the row:
  - Connect the same cell from the previous row with a given probability.
  - If you do, set that cell's value in array NEW the same as in array OLD.
  - If not, and if it's not already connected from earlier, set it to some new value.
  - As long as it is not in the same set of connected cells as the cell to its left (which can be checked via array NEW), connect it to the cell to its left with a given probability.
  - If you do, set all elements in arrays NEW and OLD which have the value of the current cell (including the current cell itself) to the value of the cell on its left.
  - Store array NEW to array OLD (or swap pointers. Whatever.)
Some special things need to be done for the last row to connect all cells:
Until every element of array OLD has the same value:
- Pick two cells whose values are different and connect them.
- Set all elements in array OLD which have the value of the second cell to the value of the first cell (still including the second cell)

Notes:

Don't perform steps mentioning "cell to the left" for the first cell in a row, obviously.
When I refer to the "value of a cell", I mean the value of the element at the corresponding index in array NEW (or OLD for a cell in the previous row).

Scipi · « **Reply #4 on:** August 04, 2011, 10:42:22 pm »

calcdude, you are a god. I just went on a rant on how there's no simple, easy to grasp explanation on how to implement it. Much less easy to follow source code. (Everything's optimized beyond all comprehension)

With this I can finally get this thing coded.

calcdude84se · « **Reply #5 on:** August 04, 2011, 10:45:29 pm »

And, to clarify further, a set of connected cells is one whose cells' values are all the same. (Edit: except the first time it's mentioned, where it actually means its literal meaning. You could have a counter that you increment every time you don't connect to the cell on the left in the first row to initially fill array OLD.)
And the code isn't very optimized; it's just TI-BASIC. I have never found a way to make TI-BASIC code easy to read for more complicated things.
Glad you like it

. Maybe I should start writing tutorials...

Scipi · « **Reply #6 on:** August 04, 2011, 11:54:53 pm »

Ok, so I started and so far I have the code to make the first row

http://pastebin.com/vH1VdNyD

Up next would be to start making the next rows correct?

I'm thinking to make the next rows I would effectively do a pointer switch between Old and New, so basically

Code: [Select]

myfunc([address of Old], [address of New])
{
    (Pick a cell from a set in Old and copy it to New)
    (Remove Wall between them)
    For(i = 1; Width; i++)
    {
    if(!part of a set)
    {
        Random(0, 1)
        If (1)
        {
            (Copy cell from Old to New)
            (Remove Wall)
        }
        else
        {
            (Make new cell here)
            if(rand(0,1))
                (copy cell from left and remove wall)
        }
    }
}

myfunc(New, Old)//Notice I switched old and new so that in the func, New becomes Old and vice versa

Would that pretty much do it?

calcdude84se · « **Reply #7 on:** August 06, 2011, 08:19:36 pm »

I'll need some time to learn a bit of C++ and look over what you've written.
Meanwhile, you could just continue yourself and see if you can get it work

Scipi · « **Reply #8 on:** August 06, 2011, 10:16:59 pm »

That's what I'm so far doing. I've got to the point of making random drop downs from each set and making sure each set has at least one. Next up is to make the empty cells their own set and randomly connect them to existing sets.

Author Topic: Maze algorithm help (Read 5946 times)

Scipi

Maze algorithm help

calcdude84se

Re: Maze algorithm help

Scipi

Re: Maze algorithm help

calcdude84se

Re: Maze algorithm help

Scipi

Re: Maze algorithm help

calcdude84se

Re: Maze algorithm help

Scipi

Re: Maze algorithm help

calcdude84se

Re: Maze algorithm help

Scipi

Re: Maze algorithm help