🔒 Locked

Random dungeon creation

Started by Exorph Jul 20, 2011 at 7:35 AM 5 replies 2.1k views

Original Post

Jul 20, 2011 at 7:35 AM

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?

kru

Jul 20, 2011 at 8:43 AM

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.

ApochPiQ

Jul 20, 2011 at 9:42 AM

Have a look around for common maze generation algorithms; there are several different approaches which might be suitable.

Andrew Kabakwu

Jul 20, 2011 at 10:49 AM

Check the dev blog for Drillboid

samoth

Jul 20, 2011 at 11:22 AM

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, do not make it straight. 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 two or three paths going from each opening to the other, the random variations giving a broader overall corridor (or several alternative corridors, depending on parameters).

NEXUSKill

Jul 20, 2011 at 2:58 PM

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.

Wyrframe

Jul 21, 2011 at 6:06 AM

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.

Exorph

Jul 25, 2011 at 7:43 PM

http://roguebasin.ro...tegory: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.

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

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.