Automatic Level Generation

Nibbie
Posts: 2
Joined: 2012.06
Post: #1
does anyone have any good resources for, or information about automatic level generation for a maze game?

thanks,
kevin
Quote this message in a reply
Member
Posts: 196
Joined: 2002.04
Post: #2
Hmm....well, I'm writting something very, very, very, very top secret that's kind of what you're talking aboutGrin. A good resource would be some of the artificial intellegence web sites listed in the links section on idevgames. What kind of maps are you making? Are they tile based?

Iceman
Quote this message in a reply
w_reade
Unregistered
 
Post: #3
Surely this isn't an AI problem.

Basic outline: start with an empty map with just start and end points. Draw a random wiggly path from the start to the end, probably making sure it doesn't intersect itself, and once you've done that fill the rest of the space up with random wiggly paths.

This is obviously not the whole story, but I don't have time to think about it properly or say any more now. Post if you're interested and I'll try to get my thoughts in order.
Quote this message in a reply
Nibbie
Posts: 2
Joined: 2012.06
Post: #4
The game uses tiles, and i'd like to generate a map with rooms and such and not strictly a maze.

any input would be appreciated.

thanks,
kevin
Quote this message in a reply
Member
Posts: 269
Joined: 2005.04
Post: #5
If you can, find Tricks of the Mac Game Programming Gurus. It has a section on exactly this, random generation of mazes in a 2D tile-based game. If I get a chance later I'll grab my copy and post a general overview of it (about to leave to pick up Harry Potter 5).

Actually, I bet I have the source code to a sample program that shows it. I'm sure it'll be okay to post that.
Quote this message in a reply
Hog
Member
Posts: 151
Joined: 2002.09
Post: #6
something like this maybe?

http://www.aarg.net/~minam/dungeon.cgi
Quote this message in a reply
Member
Posts: 715
Joined: 2003.04
Post: #7
Whoa that brings back flashbacks.

There is in the resource section here a maze generator.
I think silvernetworks.com ..wasshisname...made it.

I made something like this as well, although it doesn't populate the grid.

Works like this:
Early script is a simple 2D array to build a grid of meshes for a 3D walkspace...this should work in 2D as well.

I modify it to check a random number, everytime it builds a bit of floor, lets say if there is a number over 90 (100 is tops) then it builds a cube like structure at that location, using another random value for height. If it was consistant then I could get a "dungeon" like maze.

Ta-da instant Platformish-citylike-something or other cube world. Pretty simple really.

Now to throw in monsters...I would repeat the mesh building step, with an offset so the monsters aren't inside the walls. I would generate a monster 3% of the time on the first level, 6% on the next, and so on, never going below 60% I think because it wuold just be choas!


Here's the trick though, you need to have a maze runner, check the level before it can be played, the exits have to be accessible, the monsters can't be trapped.
That is something I haven't figure out yet, the little AI part.

Ah just caught your post, about tiles, my example should work for that too. Just replace the height with tile-tags.
ie.
random 1 to 3
1 is a step tile
2 a wall tile
3 towering wall,

with plenty more options.

The thing about random is that it has to be good looking and sensible, so I think it needs some kind of templates it will fit into.

So its not TOTALY random, but planned chaos.

Good luck.
Quote this message in a reply
Member
Posts: 196
Joined: 2002.04
Post: #8
Wow that dungeon stuff is coolCool. Mine is a lot more complex for no reason really. Oh well.

Iceman
Quote this message in a reply
Member
Posts: 269
Joined: 2005.04
Post: #9
Oh right, I was suppose to post this wasn't I?

http://www.killerrobots.com/DungeonE.sit.hqx

Little mini-game with source from Tricks of the Mac Game Programming Gurus. Randomly generates a maze that you can walk around in and kill things. Uses the mouse for input.
Quote this message in a reply
Feanor
Unregistered
 
Post: #10
Quote:Originally posted by c_dev
something like this maybe?

http://www.aarg.net/~minam/dungeon.cgi


That's a laugh and half. Please don't tell me people actually use those. They're full of hallways that go nowhere.

If you want truly random environments, the sure, it's probably pretty easy. You could get into A.I. if you want by looking at constraint satisfaction (I think...), that is if you want levels that seem to have an order and purpose to them. It can be as simple or as impossibly complex as you want to make it, depending on whether the levels are just mazes or actually are supposed to be similar to some kinds of constructions that have real uses.

Diablo did well enough with random mazes, but honestly I thought Diablo was a stupid game.
Quote this message in a reply
Member
Posts: 749
Joined: 2003.01
Post: #11
Get the angband source code and hack it Rasp . I guess Angband has a pretty complex maze generator, with secret doors, vaults,...
Quote this message in a reply
Member
Posts: 269
Joined: 2005.04
Post: #12
Quote:Originally posted by Feanor
That's a laugh and half. Please don't tell me people actually use those. They're full of hallways that go nowhere.


Check the options on the generation page. You can remove a percentage of the dead-ends, even 100% to remove em all.
Quote this message in a reply
nickdabner
Unregistered
 
Post: #13
I have a RealBasic based game that generates a perfect maze. It uses the backtrack method and is fairly quick.

Code is a little messy and it only tested for 64x64, but works ok. Once the maze is created, I just knock down some walls randomly to open things up a little.

The good things about the backtrack method is you can reserve locations prior to the maze generation. I want lots of dead ends to put items in.

Ideally, I think the mazes in Minotaur were great. Player could see each other over the walls if they were near - gets away from that hand to hand combat thing.

There is a screenshot at http://members.optusnet.com.au/nickdabner/ss1.jpg

Could probably extract the code for you.

Nick
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Dungeon Generation stevejohnson 9 5,568 Nov 3, 2004 05:05 PM
Last Post: Diplomtennis