Author Topic: Just how exactly does the generator work?  (Read 1495 times)

Xion350

  • Posts: 2
Just how exactly does the generator work?
« on: May 14, 2016, 02:35:38 AM »
What I'd like to do is make a game that has a level generator similar to the way Oblige works.  The levels it creates is way better than the 'Box rooms connected by hallways' that most randomized games do.  I've already taken a look at the .lua files and there's quite a lot and I'm not sure where to start to even figure out how it works.

andrewj

  • Developer
  • *****
  • Posts: 1366
Re: Just how exactly does the generator work?
« Reply #1 on: May 14, 2016, 04:37:38 AM »
I have used several different methods over the years.

Version 6.20 uses an approach of dividing the map into rectangles.  Then each rectangle or a group of rectangles becomes a room.  Each room is then filled based on some pre-defined patterns.  For example, one pattern divides the room into two floors (of different heights) and specifies a staircase to connect them.

Version 7.37 grows each room from a starting shape (a small rectangle) by applying rules which match a pattern and add stuff into each room -- sometimes creating new floors.  Special "sprout" rules are used create new rooms off an existing room.  This method is harder to program but can produce better results.

The animated GIF below is an example of the 7.37 growing process.  Blue lines represent boundaries between two rooms.  Green lines separate different floors in a room.  Purple rectangles are connections between two rooms.
« Last Edit: May 14, 2016, 05:06:24 AM by andrewj »

andrewj

  • Developer
  • *****
  • Posts: 1366
Re: Just how exactly does the generator work?
« Reply #2 on: May 14, 2016, 06:39:56 AM »
This animation shows version 6.20 (the current stable version) in action:

Glaice

  • Contributor
  • *****
  • Posts: 1115
  • Veteran OBLIGE modder
    • The Doom Video Vault
Re: Just how exactly does the generator work?
« Reply #3 on: May 14, 2016, 09:03:44 AM »
Quite a difference in room building indeed!

Xion350

  • Posts: 2
Re: Just how exactly does the generator work?
« Reply #4 on: May 14, 2016, 12:36:13 PM »
I have used several different methods over the years.

Version 6.20 uses an approach of dividing the map into rectangles.  Then each rectangle or a group of rectangles becomes a room.  Each room is then filled based on some pre-defined patterns.  For example, one pattern divides the room into two floors (of different heights) and specifies a staircase to connect them.

Version 7.37 grows each room from a starting shape (a small rectangle) by applying rules which match a pattern and add stuff into each room -- sometimes creating new floors.  Special "sprout" rules are used create new rooms off an existing room.  This method is harder to program but can produce better results.

The animated GIF below is an example of the 7.37 growing process.  Blue lines represent boundaries between two rooms.  Green lines separate different floors in a room.  Purple rectangles are connections between two rooms.

Funny, it seems more complicated than that.  It's rather amazing that it produces such high quality maps.

andrewj

  • Developer
  • *****
  • Posts: 1366
Re: Just how exactly does the generator work?
« Reply #5 on: May 15, 2016, 09:46:59 PM »
Naturally there is more needed, e.g. quest system for choosing what doors to lock and where to place the key, choosing textures, picking floor and ceiling heights, and placing monsters and items in rooms.

But the basic structure of the level is generated as described above.

Here is an animation of another method I tried, the "weird shape" generator.

De-M-oN

  • Posts: 126
Re: Just how exactly does the generator work?
« Reply #6 on: July 20, 2016, 03:49:05 PM »
I could imagine a cool feature would be to have an option which randomizes the used method for each map. It would raise the overall randomness.
Maybe even some methods can be combined in some way to maximize its randomness output?

Or some rooms use this method, some rooms the other one
then there is suddenly a cave with 6.20 method caves
then there is suddenly a cave with weird shape method connected on a next (indoor) area where the 7.37 method was used, then a staircase to a version 4 rooms area and so on, you get the idea I think^^

andrewj

  • Developer
  • *****
  • Posts: 1366
Re: Just how exactly does the generator work?
« Reply #7 on: July 29, 2016, 01:42:53 AM »
I could imagine a cool feature would be to have an option which randomizes the used method for each map. It would raise the overall randomness.
Maybe even some methods can be combined in some way to maximize its randomness output?
This has been suggested before, so I've added an entry to the FAQ about it:

http://oblige.sourceforge.net/doc_faq.html#hodgepodge

Shrinker

  • λ
  • Posts: 6
  • λ
    • Homepage
Re: Just how exactly does the generator work?
« Reply #8 on: January 20, 2017, 07:45:18 AM »
This animation shows version 6.20 (the current stable version) in action:
This was a very nice idea and I am replicating it for my own program.
Before I saw this, shifting common walls between rooms, I only got as far in my concept as what is shown in the first frame here. :3
In my version, I am making sure in each step that the the original potentials for connecting rooms is preserved, i.e. when a wall is moved, one of the limits imposed is that it doesn't block entrance to an adjacent room that a room originally had access to.

andrewj

  • Developer
  • *****
  • Posts: 1366
Re: Just how exactly does the generator work?
« Reply #9 on: January 22, 2017, 09:55:25 PM »
In my version, I am making sure in each step that the the original potentials for connecting rooms is preserved, i.e. when a wall is moved, one of the limits imposed is that it doesn't block entrance to an adjacent room that a room originally had access to.
Ahh, I guess your algorithm connects rooms first.  Oblige V6 does the connections after resizing the rooms.

Glaice

  • Contributor
  • *****
  • Posts: 1115
  • Veteran OBLIGE modder
    • The Doom Video Vault
Re: Just how exactly does the generator work?
« Reply #10 on: January 23, 2017, 12:41:12 PM »
Shrinker, do you have a page you're going to set up? RMGs and procedural generation in general interest me greatly.

Shrinker

  • λ
  • Posts: 6
  • λ
    • Homepage
Re: Just how exactly does the generator work?
« Reply #11 on: January 24, 2017, 12:29:21 PM »
I have a Twitter for updates on projects like this (in my signature), and a homepage with project pages (linked to from Twitter too). I'm not looking so much into writing articles on this, but I can share my stuff just fine in responses to specific questions or in chat. :)

Shrinker

  • λ
  • Posts: 6
  • λ
    • Homepage
Re: Just how exactly does the generator work?
« Reply #12 on: January 26, 2017, 12:26:49 PM »
Ahh, I guess your algorithm connects rooms first.  Oblige V6 does the connections after resizing the rooms.
Yeah, all my approaches are very top-down at the moment, so decisions made earlier in the pipeline are carried through.
I've just successfully generated a sample: Here, the different numbers represent the different rooms. They started off in a regular grid and I've let the algorithm move their south (bottom) walls around randomly. The constraints are that a room is 2 to 5 cells "long" (high) and that the original adjacencies be retained: 0 to 3 formed a line, 4 to 7, etc. - that's why the room marked 14 can be reached by 13 and 15, and 12 and 13 share a wall. In this case, -1 is just empty space no room grew into during the run.
Code: [Select]
00 00 01 01 02 02 03 03
00 00 01 01 02 02 03 03
00 00 01 01 02 02 03 03
00 00 05 05 06 06 03 03
00 00 05 05 06 06 07 07
04 04 05 05 06 06 07 07
04 04 05 05 10 10 07 07
08 08 09 09 10 10 11 11
08 08 09 09 14 14 11 11
08 08 09 09 14 14 15 15
08 08 13 13 14 14 15 15
08 08 13 13 18 18 15 15
12 12 13 13 18 18 19 19
12 12 13 13 18 18 19 19
16 16 17 17 18 18 19 19
16 16 17 17 18 18 23 23
20 20 21 21 22 22 23 23
20 20 21 21 22 22 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1

If I skew the random numbers to always pick the maximum room size, it grows like this (saturated with rooms as big as possible and topped off with rooms as small as possible):
Code: [Select]
00 00 01 01 02 02 03 03
00 00 01 01 02 02 03 03
00 00 01 01 02 02 03 03
00 00 01 01 02 02 03 03
00 00 01 01 02 02 03 03
04 04 05 05 06 06 07 07
04 04 05 05 06 06 07 07
04 04 05 05 06 06 07 07
04 04 05 05 06 06 07 07
04 04 05 05 06 06 07 07
08 08 09 09 10 10 11 11
08 08 09 09 10 10 11 11
08 08 09 09 10 10 11 11
08 08 09 09 10 10 11 11
12 12 13 13 14 14 15 15
12 12 13 13 14 14 15 15
16 16 17 17 18 18 19 19
16 16 17 17 18 18 19 19
20 20 21 21 22 22 23 23
20 20 21 21 22 22 23 23

Once I've checked this more thoroughly, I can generalize the code for the south direction to cover the other directions too.

Shrinker

  • λ
  • Posts: 6
  • λ
    • Homepage
Re: Just how exactly does the generator work?
« Reply #13 on: February 06, 2017, 03:54:56 PM »
Managed to generalize my method to cover all four sky directions: https://twitter.com/shrinker42/media
So much work. o_o

Glaice

  • Contributor
  • *****
  • Posts: 1115
  • Veteran OBLIGE modder
    • The Doom Video Vault
Re: Just how exactly does the generator work?
« Reply #14 on: February 06, 2017, 05:31:45 PM »
What are you writing this program in?