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.
