How to create this mazegenerator?

I want to enhance the game WolfenDoom3D with a generic levelgenerator.

The task is to create a mazegenerator (in lite-c).
The generator should create (depending on a 2D grid) a multipath maze (more than one solution) some rooms and finally place doors/keys/(breakable, movable) walls, goodies and enemies (per handicap).

How would you code this?
Any ideas?

This could be the process.

I would start by flooding the grid as you did.
then randomly make some rooms that have a random size (this means they could potentially into each other... but that shouldnt matter really).

Now you switch the last 2 steps.
since you just created the rooms, you know the edges of them.
You can create secret walls and doors based on that (maybe even secret rooms in this step). and once you know all this, link up all the rooms by making hallways (take the closest doors, and calculate the path between these every time).

Then add random enemies and pickups on random white spots.

Maybe it's a bad example image I posted.

The way you offered just creates connected (opt. seperated by br.wall, simple doors) and filled rooms.
This would become boring in the second level.
Furtheron there is the problem with doors & keys.
How to place them in a correct order (you have 4 colored keys/doors) and need the right key before you approach the ref. door.

The perfect generated level I think should be a maze with rooms (not vice versa) and a correct sequence of keys/doors.
Some rooms should have no door but just a br./move wall.

1) and 2) are easy.

So let's start with the corridors.
You can check for each room which room is next and then you can do simple connections with doors at each passage end.
Fleshing out a maze is not really easy. What you can do is you scan what's around the sides of the room connector passages and dig in the sides until this is not possible anymore (no 'a's anymore). When starting to dig you might place a door right away.

During all this you have to track all possible routes (from room a to room b via corridor c passing door d which is between room b and passage c and so you can evaluate in which room you might place a key (in this case it would either be passage c or room a).
For ammo I would count how many enemies are placed in a room or passage and then drop ammo fitting to this enemy number.

Which weapons can be placed I would restrict via options in the generator tool. The weapons itself I would again place like the keys. You need an internal list in which order rooms and passages can be accessed. You some simple map scanning and a node structure for this, like it is also done with pathfinding.

It's not easy, but surely fun!
There are a lot of algorithms for mazes on the internet, in all languages. Perhaps an idea?

About placing the keys...


0...Duplicate the data-structure holding your map, so we don't mess up the original.
1...Do a flood-fill with P(player start) as your starting node and space (the empty area) as your target color.
2...Modify the flood-fill algorithm to find doors adjacent to the empty areas that it traverses and store them in a queue. We'll call it, door-queue. I'll write the modified* flood-fill algorithm at the end of this post.
3...If door-queue is empty, return (this is the only exit. means all doors have been opened)
4...While door-queue is not empty:
5.......Set D to the front node of door-queue.
6.......Select a replacement-color painted node at random. (replacement-color are the nodes visited in the last flood-fill).
7.......Create a key of the color of the door found in D node and place it on the node selected in Step 6. Also place the same key at the same position on the ORIGINAL MAP.
8.......Remove the door from D node on the map and replace it with replacement-color, if you haven't done it already in 0 step of Modified Flood-fill.
9.......Dequeue door-queue (remove the front node).
10..Repaint all replacement-color nodes as target-color (white space).
11..Loop back to 1. Map should now be just like it was at the beginning (no replacement-color painted nodes) except that the doors examined in this cycle are replaced with white space (opened) and the keys that open them lay around. Since these doors are now white spaces, the next flood-fill will examine a bigger area of the map since it will now be able to traverse beyond them. The algorithm ends in step 3 if the last flood-fill didn't find any doors (they have all been removed, or there wasn't any in the first place).


*About Step 2. Assuming you're using the recursive implementation (you should. It's the simplest one and lite-c can handle it). Add the following zero line at the beginning:

I would create that from the players perspective:

The main aim is to have general Path a player takes, with
a limited amount of departures, so you feel a progress in the game, and not just a wild maze. This way cou can also influence
on the level-rythm. (like: spawn-explore-fight-explore-find key -bossfight-end of level)

So Basically first think about a sequence of "things" the player should encounter in that level.

For example:
-A enter medium room with enemy and ammo (possible key)
-B enter corridor with several doors (small rooms along, ich have a 25% of having some pickup or enemy)
-C entering a corner-corridor
-D entering a larger room with several enemies
-E encountering a Door, key must have been accesible before
-D entering a "Secret" rooms with lots of coins
-f entering a Hall with a boss enemy. Hall is locked by door
-g exitdoor


Now you define the "Must have" for that level.

For example a gamedesigner defienes a sequence

(Start-room), A,B,C,B,D,A,D,C,E,A,E,D,A,B,B,C,F, (G -END )

You can allow some random variations in that sequence. But it must
have G, and ist must have keys before the doors, and at least
one Boss-level in the end.


To generate your maze now, use some recursive algorythm,
that tests out combinations, and returns a list of valid rooms.
Of wich you can choose one randomly.

The specific step in the generation could be,
that you start with the spawn-room.
Now you create a randomly long corridor and add an "A" room
to the left front or side. "A" rooms are randomly between 4x4 and 7x7 quares big.
From there you create an "B" corridor to the right,left or front side, etc.., starting at a random wall square.
Then you insert a "C" corner corridor....

Each step return as invalid (recursion) if it hits the
edges of the level, or intersects with an created levelpart.
This step is thus ignore, and "the next side or wallsquare" is tried out.

-------------

For using "split" paths, you can remember the split position,
and first create things toward the one side for 5 steps or so.
Then return back to the split position and create the other 5 steps.
The requirement is, that the second split intersects with an element of the path of the first split (to not have dead ends).
Or more easy, with some previously created part of the level.


Then you could insert a door at this room where they meet again, to make a single path again... etc. etc...

--------

you can let the computer run this expensive recursicve search,
and let him return back a list of valid rooms.

From this list you select a random one.

Voila, you have a random level, that meets your gamedesign targets and retrictions.

(It should in concept generate random Levels such as in games like
Diablo or Torchlight.
There also its not a wild random area, but defined by
a gameplay defined rythm of elements to encounter.)

i'd create the paths 1st, then create the rooms,

each room will have a priority and know which are accessible from the order they were created in

once you know this, you're able to place keys and doors, bosses, etc, in these rooms to make sure everything is possible

thanx.
I think I have found a good solution (it's a combination of your ideas).
If it works you can test it in the game (later)...

Hurray!!!!
The Mazeganerator is implemented (it's first version).

You can choose four different sizes (S,M,L,XL) at the end of the level selection. (L, XL is slow on my system!).


I choosed to make it a cave:


Have fun. You can download the new version (v.5) on the known webpage webpage

have fun...