Random dungeon creation

Recommended Posts

Exorph    105
I'm creating a game with randomly generated dungeons. They consist of several rooms the size of the screen, but right now they are completely empty except for the enemies which makes for a rather boring game.

I want to put in objects that the player can't walk past, but obviously I can't place these completely random or I risk making the game impossible to finish. One way of solving it would be to create a straight path between the openings of a room and make it illegal to place objects on the path, but that'll probably look fake. Another way would be to do a pathfind after placing each objects, and if I can't find a path between all the openings I remove it again, but that feels a bit too much like brute force.
Is there some algorithm for finding A path between two points, not the shortest and straightest? Or do you have some other idea of how to solve this?

Share on other sites
kru    211
What you want to do is to make certain that the player is not blocked from accessing important areas within your room (treasure, exits, triggers, etc). So, after placing your objects, do a flood-fill from the entrance of the room and mark any unreachable areas as unreachable. Then you can either move important items in unreachable areas to reachable areas, or you can use some type of walk algorithm to tear down walls in between important-but-unreachable areas and the nearest reachable area. Playing around with your walk algorithm will give you good looking results.

Share on other sites
ApochPiQ    23004
Have a look around for common maze generation algorithms; there are several different approaches which might be suitable.

Share on other sites
[url="http://mildlydisconcerting.com/drillboid/2011/02/13/procedural-generation-part-2"]Check the dev blog for Drillboid[/url]

Share on other sites
One very simple way of ensuring that the game cannot be unsolvable would be to do similar to what you already proposed yourself:

Make a straight path between the openings of the room, but then again, [i]do not make it straight[/i]. Give it 2-3 vertices somewhere along the path and offset those slighly (randomly). You end up with a more or less zigzag sequence of line segments.

Now, place your random stuff, except when an object's radius is [s]greater[/s] smaller than the distance to any line segment. Done.

By tweaking the number of intermediate vertices and the amount of random, you can change the look. You can also have [i]two or three[/i] paths going from each opening to the other, the random variations giving a broader overall corridor (or several alternative corridors, depending on parameters).

Share on other sites
NEXUSKill    475
A simple density limitation in your random algorithm might just be enough, given a room size, the amount and size of random clutter should have a limited density coefficient relative to the room's space, that way the chances of randomly generating unaccessible zones is very low, then you can verify it as has been prompted by other posts here.

Share on other sites
Wyrframe    2426
http://roguebasin.roguelikedevelopment.org/index.php/Category:Articles

Several of those articles are about dungeon/level generation, as specific to roguelikes, but easily adaptable to your medium. Just be creative.

I especially like "Abstract Dungeons"; it specifies how to divide level generation into several distinct steps, letting you add huge amounts of flexibility in each one.

Share on other sites
Exorph    105
[quote name='Wyrframe' timestamp='1311228374' post='4838323']
[url="http://roguebasin.roguelikedevelopment.org/index.php/Category:Articles"]http://roguebasin.ro...tegory:Articles[/url]

Several of those articles are about dungeon/level generation, as specific to roguelikes, but easily adaptable to your medium. Just be creative.

I especially like "Abstract Dungeons"; it specifies how to divide level generation into several distinct steps, letting you add huge amounts of flexibility in each one.
[/quote]

Ended upp using mainly concepts from this article. Thanks a bunch. The dungeons are a lot more fun now.