Sign in to follow this  
Exorph

Random dungeon creation

Recommended Posts

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 this post


Link to post
Share on other sites
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 this post


Link to post
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
[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. :D

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this