Author Topic: Maze algorithm help  (Read 5128 times)

0 Members and 1 Guest are viewing this topic.

Offline Scipi

  • Omni Kitten Meow~ =^ω^=
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1547
  • Rating: +192/-3
  • Meow :3
    • View Profile
    • ScipiSoftware
Maze algorithm help
« 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.

Imma Cat! =^_^= :3 (It's an emoticon now!)
Spoiler For Things I find interesting:
Spoiler For AI Programming:
Spoiler For Shameless advertising:

Spoiler For OldSig:





Spoiler For IMPORTANT NEWS!:
Late last night, Quebec was invaded by a group calling themselves, "Omnimaga". Not much is known about these mysterious people except that they all carried calculators of some kind and they all seemed to converge on one house in particular. Experts estimate that the combined power of their fabled calculators is greater than all the worlds super computers put together. The group seems to be holding out in the home of a certain DJ_O, who the Omnimagians claim to be their founder. Such power has put the world at a standstill with everyone waiting to see what the Omnimagians will do...

Wait... This just in, the Omnimagians have sent the UN a list of demands that must be met or else the world will be "submitted to the wrath of Netham45's Lobster Army". Such demands include >9001 crates of peanuts, sacrificial blue lobsters, and a wide assortment of cherry flavored items. With such computing power stored in the hands of such people, we can only hope these demands are met.

In the wake of these events, we can only ask, Why? Why do these people make these demands, what caused them to gather, and what are their future plans...

Offline calcdude84se

  • Needs Motivation
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2272
  • Rating: +78/-13
  • Wondering where their free time went...
    • View Profile
Re: Maze algorithm help
« 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
« Last Edit: August 04, 2011, 09:25:10 pm by calcdude84se »
"People think computers will keep them from making mistakes. They're wrong. With computers you make mistakes faster."
-Adam Osborne
Spoiler For "PartesOS links":
I'll put it online when it does something.

Offline Scipi

  • Omni Kitten Meow~ =^ω^=
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1547
  • Rating: +192/-3
  • Meow :3
    • View Profile
    • ScipiSoftware
Re: Maze algorithm help
« 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. :P

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. :(

Imma Cat! =^_^= :3 (It's an emoticon now!)
Spoiler For Things I find interesting:
Spoiler For AI Programming:
Spoiler For Shameless advertising:

Spoiler For OldSig:





Spoiler For IMPORTANT NEWS!:
Late last night, Quebec was invaded by a group calling themselves, "Omnimaga". Not much is known about these mysterious people except that they all carried calculators of some kind and they all seemed to converge on one house in particular. Experts estimate that the combined power of their fabled calculators is greater than all the worlds super computers put together. The group seems to be holding out in the home of a certain DJ_O, who the Omnimagians claim to be their founder. Such power has put the world at a standstill with everyone waiting to see what the Omnimagians will do...

Wait... This just in, the Omnimagians have sent the UN a list of demands that must be met or else the world will be "submitted to the wrath of Netham45's Lobster Army". Such demands include >9001 crates of peanuts, sacrificial blue lobsters, and a wide assortment of cherry flavored items. With such computing power stored in the hands of such people, we can only hope these demands are met.

In the wake of these events, we can only ask, Why? Why do these people make these demands, what caused them to gather, and what are their future plans...

Offline calcdude84se

  • Needs Motivation
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2272
  • Rating: +78/-13
  • Wondering where their free time went...
    • View Profile
Re: Maze algorithm help
« Reply #3 on: August 04, 2011, 10:35:17 pm »
Nah, it'd take me a bit too to remember how it works :P
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).
« Last Edit: August 04, 2011, 10:35:37 pm by calcdude84se »
"People think computers will keep them from making mistakes. They're wrong. With computers you make mistakes faster."
-Adam Osborne
Spoiler For "PartesOS links":
I'll put it online when it does something.

Offline Scipi

  • Omni Kitten Meow~ =^ω^=
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1547
  • Rating: +192/-3
  • Meow :3
    • View Profile
    • ScipiSoftware
Re: Maze algorithm help
« 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) :P

With this I can finally get this thing coded. XD

Imma Cat! =^_^= :3 (It's an emoticon now!)
Spoiler For Things I find interesting:
Spoiler For AI Programming:
Spoiler For Shameless advertising:

Spoiler For OldSig:





Spoiler For IMPORTANT NEWS!:
Late last night, Quebec was invaded by a group calling themselves, "Omnimaga". Not much is known about these mysterious people except that they all carried calculators of some kind and they all seemed to converge on one house in particular. Experts estimate that the combined power of their fabled calculators is greater than all the worlds super computers put together. The group seems to be holding out in the home of a certain DJ_O, who the Omnimagians claim to be their founder. Such power has put the world at a standstill with everyone waiting to see what the Omnimagians will do...

Wait... This just in, the Omnimagians have sent the UN a list of demands that must be met or else the world will be "submitted to the wrath of Netham45's Lobster Army". Such demands include >9001 crates of peanuts, sacrificial blue lobsters, and a wide assortment of cherry flavored items. With such computing power stored in the hands of such people, we can only hope these demands are met.

In the wake of these events, we can only ask, Why? Why do these people make these demands, what caused them to gather, and what are their future plans...

Offline calcdude84se

  • Needs Motivation
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2272
  • Rating: +78/-13
  • Wondering where their free time went...
    • View Profile
Re: Maze algorithm help
« 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...
« Last Edit: August 04, 2011, 10:48:33 pm by calcdude84se »
"People think computers will keep them from making mistakes. They're wrong. With computers you make mistakes faster."
-Adam Osborne
Spoiler For "PartesOS links":
I'll put it online when it does something.

Offline Scipi

  • Omni Kitten Meow~ =^ω^=
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1547
  • Rating: +192/-3
  • Meow :3
    • View Profile
    • ScipiSoftware
Re: Maze algorithm help
« 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?

Imma Cat! =^_^= :3 (It's an emoticon now!)
Spoiler For Things I find interesting:
Spoiler For AI Programming:
Spoiler For Shameless advertising:

Spoiler For OldSig:





Spoiler For IMPORTANT NEWS!:
Late last night, Quebec was invaded by a group calling themselves, "Omnimaga". Not much is known about these mysterious people except that they all carried calculators of some kind and they all seemed to converge on one house in particular. Experts estimate that the combined power of their fabled calculators is greater than all the worlds super computers put together. The group seems to be holding out in the home of a certain DJ_O, who the Omnimagians claim to be their founder. Such power has put the world at a standstill with everyone waiting to see what the Omnimagians will do...

Wait... This just in, the Omnimagians have sent the UN a list of demands that must be met or else the world will be "submitted to the wrath of Netham45's Lobster Army". Such demands include >9001 crates of peanuts, sacrificial blue lobsters, and a wide assortment of cherry flavored items. With such computing power stored in the hands of such people, we can only hope these demands are met.

In the wake of these events, we can only ask, Why? Why do these people make these demands, what caused them to gather, and what are their future plans...

Offline calcdude84se

  • Needs Motivation
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2272
  • Rating: +78/-13
  • Wondering where their free time went...
    • View Profile
Re: Maze algorithm help
« 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 :)
"People think computers will keep them from making mistakes. They're wrong. With computers you make mistakes faster."
-Adam Osborne
Spoiler For "PartesOS links":
I'll put it online when it does something.

Offline Scipi

  • Omni Kitten Meow~ =^ω^=
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1547
  • Rating: +192/-3
  • Meow :3
    • View Profile
    • ScipiSoftware
Re: Maze algorithm help
« 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.

Imma Cat! =^_^= :3 (It's an emoticon now!)
Spoiler For Things I find interesting:
Spoiler For AI Programming:
Spoiler For Shameless advertising:

Spoiler For OldSig:





Spoiler For IMPORTANT NEWS!:
Late last night, Quebec was invaded by a group calling themselves, "Omnimaga". Not much is known about these mysterious people except that they all carried calculators of some kind and they all seemed to converge on one house in particular. Experts estimate that the combined power of their fabled calculators is greater than all the worlds super computers put together. The group seems to be holding out in the home of a certain DJ_O, who the Omnimagians claim to be their founder. Such power has put the world at a standstill with everyone waiting to see what the Omnimagians will do...

Wait... This just in, the Omnimagians have sent the UN a list of demands that must be met or else the world will be "submitted to the wrath of Netham45's Lobster Army". Such demands include >9001 crates of peanuts, sacrificial blue lobsters, and a wide assortment of cherry flavored items. With such computing power stored in the hands of such people, we can only hope these demands are met.

In the wake of these events, we can only ask, Why? Why do these people make these demands, what caused them to gather, and what are their future plans...