Author Topic: Maze Generation (Source Included)  (Read 6001 times)

0 Members and 1 Guest are viewing this topic.

Offline JustCause

  • CoT Emeritus
  • LV8 Addict (Next: 1000)
  • *
  • Posts: 810
  • Rating: +115/-5
    • View Profile
Maze Generation (Source Included)
« on: November 22, 2010, 10:36:06 am »
prgmMAZE is a backtracking maze generator. When there are no available spots to carve, it backtracks until there is an open space. Because of memory limitations, large mazes will start writing outside of saferam: be careful if you decide to adjust the size! (to do this, recompile with different values for L and W.)
prgmMAZE2 shares a lot of code with MAZE, but when there are no free carving spots it randomly picks a spot already open to start carving.
These algorithms are really fast, but the most time-consuming part of the code is drawing the screen every frame. This could be omitted for map generation and such.

I'll post a detailed code explanation here later.
See you, space cowboy...

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55941
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Maze Generation (Source Included)
« Reply #1 on: November 22, 2010, 02:45:11 pm »
Interesting, I shall try this soon. I think this might be useful to write RPGs with randomized dungeons.

Offline Munchor

  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 6199
  • Rating: +295/-121
  • Code Recycler
    • View Profile
Re: Maze Generation (Source Included)
« Reply #2 on: November 22, 2010, 06:40:49 pm »
prgmMAZE is a backtracking maze generator. When there are no available spots to carve, it backtracks until there is an open space. Because of memory limitations, large mazes will start writing outside of saferam: be careful if you decide to adjust the size! (to do this, recompile with different values for L and W.)
prgmMAZE2 shares a lot of code with MAZE, but when there are no free carving spots it randomly picks a spot already open to start carving.
These algorithms are really fast, but the most time-consuming part of the code is drawing the screen every frame. This could be omitted for map generation and such.

I'll post a detailed code explanation here later.

Oh my god!

Today during the afternoon I was having a conversation with a friend and I said:

'I'd like to make a maze generator program'
'For calculator?'
'I thought to make  python (PC) one, but a calculator one would be very cool!'
'We could try to make one in that new language you're learning, Axe'


Damn, you were too quick!

Congratulations!
Haven't tested it yet, will post later with feedback

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55941
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Maze Generation (Source Included)
« Reply #3 on: November 23, 2010, 12:48:20 am »
Wow I just tried it and it's really great. I am almost tempted to use this one day if I ever decide to create a RPG with randomized dungeons. Nice job!

Offline JustCause

  • CoT Emeritus
  • LV8 Addict (Next: 1000)
  • *
  • Posts: 810
  • Rating: +115/-5
    • View Profile
Re: Maze Generation (Source Included)
« Reply #4 on: November 23, 2010, 08:57:28 am »
Yea. Adding a 50 or 70% chance for it to carve in the same direction would make your dungeons...less sadistic.
See you, space cowboy...

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55941
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Maze Generation (Source Included)
« Reply #5 on: November 23, 2010, 01:10:33 pm »
Nah, Illusiat  7 final dungeon was one huge 96x64 maze, after all. ;D

During the final escape sequence, it took 15 minutes to exit on a regular 83+ if you remembered the path approximately. X.x

Offline Munchor

  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 6199
  • Rating: +295/-121
  • Code Recycler
    • View Profile
Re: Maze Generation (Source Included)
« Reply #6 on: November 23, 2010, 02:36:42 pm »
Nah, Illusiat  7 final dungeon was one huge 96x64 maze, after all. ;D

During the final escape sequence, it took 15 minutes to exit on a regular 83+ if you remembered the path approximately. X.x

That's exagerated.

A PC RPG Maker (RPG Maker VX, very cool one!) has an auto dungeon creator, a very good one, and you can choose how hard you want it to be

Offline JustCause

  • CoT Emeritus
  • LV8 Addict (Next: 1000)
  • *
  • Posts: 810
  • Rating: +115/-5
    • View Profile
Re: Maze Generation (Source Included)
« Reply #7 on: November 23, 2010, 03:59:02 pm »
Last post until Monday.
Just found out something neat: MAZE1 generates a 20x20 maze in less than a second if you leave out the DispGraph in the main loop.
See you, space cowboy...

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55941
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Maze Generation (Source Included)
« Reply #8 on: November 23, 2010, 04:07:55 pm »
Nah, Illusiat  7 final dungeon was one huge 96x64 maze, after all. ;D

During the final escape sequence, it took 15 minutes to exit on a regular 83+ if you remembered the path approximately. X.x

That's exagerated.

A PC RPG Maker (RPG Maker VX, very cool one!) has an auto dungeon creator, a very good one, and you can choose how hard you want it to be
Yeah my dungeon was meant to be that hard. You could save anywhere, though, and by then you had about 99 potions, so you were good. And yeah I used the RM2K3 dungeon generator for one of my game back then. It was kinda cool.
Last post until Monday.
Just found out something neat: MAZE1 generates a 20x20 maze in less than a second if you leave out the DispGraph in the main loop.
Ah ok, see you then. Also that seems cool. Not too slow. :)

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Maze Generation (Source Included)
« Reply #9 on: November 23, 2010, 04:54:48 pm »
I'll have to take a look at this- the algorithm in my 3D maze project had some issues.

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55941
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Maze Generation (Source Included)
« Reply #10 on: November 24, 2010, 01:07:15 am »
* DJ Omnimaga is glad the 3D Maze is still alive, though. ;D