7 replies to this topic

[shadowgamesco]

I've spent the last little while working on a random dungeon generator in python. Right now, it generates random dungeons, and places the "staircases" to go to a higher level in the dungeon (possibly exit the dungeon) or to descend deeper into the dungeon. The next thing I want to add is a way to add "chests" to it. I thought of just picking a random number of chests to add, then to just add them in random spots in the dungeon, but then I get the occasional time when 2 chests are right next to each other, or they are in the same rooms as the stair cases, etc. Just overall bad places for them to be if it where to be used in a game. So I came up with an idea to use path finding (specifically A*) to find the shortest path from the staircase leading up to the staircase leading down, then to place the chests (a random number of them) in the areas furthest away from the path. That way the player has to go more out of his way to find all the goodies. Which encourages the player to explore more (kill more demons!) instead of focusing on just going deeper into the dungeon.

I have the path finding working, and the path is generated. But I have no idea how to do the next part. Actually finding the areas furthest away from the path. Any ideas/suggestions are appreciated!
If you want to know more about how my dungeon generator works you can look at the guide I wrote on random map generation here, or if you want to see it in action, you can download the Python source code here.

Attached Thumbnails

• 

[laztrezort]

I have the path finding working, and the path is generated. But I have no idea how to do the next part. Actually finding the areas furthest away from the path. Any ideas/suggestions are appreciated!

My first intuition would tell me to experiment with Dijkstra maps - see here for a short article. Although this is not something I've experimented with, it seems like it might be suitable.

[Suspense]

From looking over your algorithm, I think it would be useful to convert your list of rooms into a tree. Make the room with one staircase the root of the tree and mark the path from the root to the other staircase. Now you can traverse the tree from the root along any other branch and drop a chest somewhere on that branch. This will ensure that no chests are placed along the path from one staircase to the other. You can adjust things from there to get the kind of results you're after.

[Nice Try]

Just want to say that you're my hero for posting this. I've been looking for an example of how to do this for a while in pygame and this is exactly what i need to help me create my own.

[Infernal-rk]

if you implemented A* pathing, you already have a tree correct? can you travel your optimal path and then from each node of the path, branch out perpendicular to your A*s directional heuristic as far as you can or want and place chests in rooms without other chests prior (to avoid your double chest rooms)....You can make the farther pathed out chests have more valuable items to justify the larger detours to get to them.

might not work... who knows.

[Kian]

I can think of a brute force approach. Something like, go room by room and measure the distance from the room to each stair. Store the location of the room where the sum of these two distances is maximum. That will guarantee that the player has to do the longest detour possible to find the chest.

I suppose if you modify the A* algorithm a bit so it caches instead of making a fresh search from each room it won't be so bad, you'll just need to map the whole level from each stair.

[px]

This doesn't really do anything to help you with your problem, but...

How about having the quality of the items in the chest depend on the distance the chest is away from the shortest path. That way people who want to just rip through a dungeon fast will still have some chance of finding goodies and people who take their time and explore get a better chance.

Just a thought...

[shadowgamesco]

My first intuition would tell me to experiment with Dijkstra maps - see here for a short article. Although this is not something I've experimented with, it seems like it might be suitable.

Thanks for your reply, I actually came up with my own algorithm very similar to 'Dijkstra Maps' described in that article. Turned out great! Thanks to everyone else who suggested a solution.

This doesn't really do anything to help you with your problem, but...

How about having the quality of the items in the chest depend on the distance the chest is away from the shortest path. That way people who want to just rip through a dungeon fast will still have some chance of finding goodies and people who take their time and explore get a better chance.

Just a thought...

Already done my friend. Thanks!
Now there is a small chance that a chest will be placed closer to the path, but most of them are placed far away from the path. And the quality of the items inside is random, but there is an increased chance of the items being of a higher quality the further they are from the path. I'll be uploading this version (1.7) to the google code project page sometime this week! Thanks again for all of you suggestions guys!