Dungeon Generator: Create a procedurally generated map that contains rooms connected by hallways

[tristanbob]

Note:

This is a work in progress. I'm looking for suggestions on how to improve this extension. I want this to be flexible and enable many use-cases. Thank you for helping!

Describe the extension

Create a procedurally generated map that contains rooms that are connected by hallways

Logic

Create map terrain

1) Fill the entire map with terrain objects (based on inputs for map size)

Create rooms

2) Create the desired quantity of room objects 3) Change the size of the room objects to random values within the min and max constraints 4) Assign each room object a unique number

Place rooms

5) Place the first half of the room objects in a random location on one side of the map. Place the second half of room objects in a random location on the other side of the map. Split the map horizontally/vertically based on the longest side of the map. 6) If room objects are too close (based on the diagonal of the largest possible room), move a room to a new random location 7) Keep a counter of how many moves are made, and give up when the "Max attempts" value has been reached.

Connecting rooms

8) Create a pathfinding object and place it in the center of a randomly selected room object 9) Find the nearest room and set it as the destination of the pathfinding object 10) For each node on the calculated path (A*), create a Hallway object. 11) Move the pathfinding object to the center of that room and mark the room as "Visited" 12) Repeat until all rooms are "Visited" 13) If the "Close loop" parameter is selected, add a final connection from the last room to the first room 14) If the "Additional paths" parameter is greater than 0, select a random room to travel to. Repeat for the value of "Additional Paths".

Cleaning up

15) Delete the pathfinding object and any terrain that is over a hallway or room

Todo

• Gather feedback on how to make this extension more useful. What helper functions or options should be added?
• Consider adding additional generation algorithms such as random-walk and BSP (binary space partitioning).
• Clean up extension code
• Clean up example code
• Add documentation and metadata inside the extension (it's mostly blank at the moment)

Checklist

• [x] Extension has a proper name and description.
• [x] Extension has tags (for example: "platform, brick, breakable").
• [x] All behaviors have a description.
• [x] All functions (actions, conditions, expressions) have descriptions and proper sentences.
• [x] I've followed the best practices listed on http://wiki.compilgames.net/doku.php/gdevelop5/extensions/best-practices
• [x] I confirm that this extension can be integrated to this GitHub repository, distributed and MIT licensed.

Example game

https://games.gdevelop-app.com/game-f1d19ad1-8422-4f58-af9f-d1e6787b2934/index.html

Extension file

DungeonGeneratorExtension_0.5.0.json.zip

Project files

DungeonGenerator_SourceFiles_0.5.0.zip

Video

https://user-images.githubusercontent.com/8879811/126932356-084e090e-5025-414f-aa6b-ff9bdf78b641.mp4

[tristanbob]

Still a work in progress, I'm just sharing my progress so far.

Version 0.6.0

• Added option to use a random walk algorithm (using a 2D array for speed)

Random walk logic:

• Start the walker in the center of the map
• Move walker in a random direction up/down/left/right (25% chance)
• If walker lands on terrain, change it to floor
• If walker lands on border of map, move it to the center of the map
• Continue until the desired number of floor tiles have been created

Extension file

DungeonGeneratorExtension_0.6.0.json.zip

Play it here

https://games.gdevelop-app.com/game-578b39fe-a127-4f96-b590-b99944f403dc/index.html

Video

https://user-images.githubusercontent.com/8879811/127522948-b5d0fac2-d929-4fd8-aef2-7b72afadd509.mp4

[tristanbob]

I'm still working on this, but here is my latest progress.

DungeonGenerator_SourceFiles_0.7.1.zip

[tristanbob]

https://twitter.com/VictrisGames/status/1422327497006346245

[tristanbob]

Note: This will be the last version I make before I go on an extended duration family vacation. I would love to get feedback before I submit this in a few weeks. I don't plan on changing anything except cleaning up descriptions and comments, but that can change based on feedback. Thanks!

Version 0.8.1

Changes include:

• Counts neighbors correctly (similar to Minesweeper)
• Greatly improved algorithm for placing rooms
• Major UI improvements on the example game
• Added doorways that can be locked/unlocked with actions.
• Pre-made rooms can be inserted into the randomly placed rooms
• Uses physics to keep objects apart

Playable game

https://games.gdevelop-app.com/game-7dfa4696-6dc9-470e-a5b4-b0aeda926240/index.html

Extension file

DungeonGeneratorExtension_0.8.1.json.zip

Project files

DungeonGenerator_SourceFiles_0.8.1.zip

[kevino93]

Hey, very good job! I would ask you a question about the 8.1 version code you posted. How did you made chests generate in the number 5 spot in the dungeon cave?

[4ian]

@tristanbob Is this ready for review by the way? :)

[tristanbob]

I would ask you a question about the 8.1 version code you posted. How did you made chests generate in the number 5 spot in the dungeon cave?

@kevino93 this extension includes a function to count neighbors, and so it counts the number of wall tiles near a floor tile (this logic is similar to how minesweeper works). Then I simply search all floor tiles that have a neighbor count of 5 or greater and place a treasure there.

@tristanbob Is this ready for review by the way? :)

Not ready for review yet. I am done with functionality, but I need to clean up descriptions and code. Oh I do need to adjust the chance the random walker moves based on the aspect ratio of the map.

I expect I will submit this by this weekend.

[UlisesFreitas]

Hi Tristan Rhodes one little thing if is possible for you to tag all the Debug objects so it's easy to delete them later I'm currently working with the 8.1 and I don't really know what could or couldn't be deleted, maybe it's me alone in this.

So I grabbed the 8.1 version and resize all the assets to fit 8x8 changed the tile size in the events and this is happening any clue https://www.youtube.com/watch?v=6pJyNCvDKcs

[tristanbob]

After the dungeon has been created, you can delete any of the objects. This extension only creates the dungeon, it doesn't handle any logic of how the game interacts with the objects.

That said, I recommend leaving the objects and hide them. This way you can create logic that references "walls", "rooms", hallways", "hallways that are doorways", etc. for collisions, camera movement, and special events.

[tristanbob]

So I grabbed the 8.1 version and resize all the assets to fit 8x8 changed the tile size in the events and this is happening any clue https://www.youtube.com/watch?v=6pJyNCvDKcs

Can you share your project? I'll see if I can find out what is happening.

[UlisesFreitas]

Sure here is the project I only just modified the size of the sprites to 8x8 and the tile grid to 8 DungeonGenerator8.1-Ulises.zip

[tristanbob]

This extension is now ready for review. Thanks for your time!

Version 1.0.0

• Walkers now select a random direction based on the aspect ratio of the map
• Cleaned up unused code and descriptions
• Added helper conditions and expressions

Extension file

DungeonGeneratorExtension_1.0.0.json.zip

Playable demo

https://victrisgames.itch.io/extension-dungeon-generator

Project folder

DungeonGenerator_SourceFiles_1.0.0.zip BE SURE TO IMPORT EXTENSION VERSION 1.1.0

[tristanbob]

Version 1.1.0

• Automatically resizes all objects based on the specified tile size
• Thanks to @UlisesFreitas for testing this and finding a problem when using different object sizes

Extension file

DungeonGeneratorExtension_1.1.0.json.zip

[tristanbob]

Version 1.1.5

• Updated the "cave" mode to also resize objects to match tile size automatically
• Minor updates to the example game

Extension file

DungeonGeneratorExtension_1.1.5.json.zip

Project folder

DungeonGenerator_SourceFiles_1.1.5.zip

[tristanbob]

@4ian (and all). Anyone interested in reviewing this?

[4ian]

@tristanbob Yes! Speaking of it, I tried the demo, and while the DungeonCave seems to work properly, the DungeonWithRooms seems to have a spaceship that is way too large? Is this normal? :)

[tristanbob]

The ship is not part of the extension, just the example. I must have left the tile size of example set to 8. Try changing it to 64 (it should be near the top of the event sheet when I define the TileSize variable).

[tristanbob]

Here is my most recent version of the example (I have crossed out the previous ones above). There are no changes to the extension:

DungeonGenerator_SourceFiles_1.1.5.zip

[4ian]

Looks great overall!

Very quick review:

In the example, sounds strange to use a random channel number, do you need a channel at all?

Blocking the room entrance is a real gameplay stuff that should then not be under the "UI" group (where I expect only to see stuff related to the interface, not the gameplay itself)?

A few typos:

• Caculate the number of grid
• Generate dungeon. Room Qty: _PARAM7_, Tile size: _PARAM1_ pixels, Map width: _PARAM2_ tiles, Map height: _PARAM3_ tiles, Terrain object: _PARAM4_, Room object: _PARAM5_, Wall object: _PARAM20_, Doorway object: _PARAM21_, Hallway object: _PARAM6_, Pathfinding object: _PARAM13_, Min room width: _PARAM9_ tiles, Max room width: _PARAM10_ tiles, Min room height: _PARAM11_ tiles, Max room height: _PARAM12_ tiles, Hallway width: _PARAM17_ tiles, Create objects on layer: _PARAM8_, Max separation attempts: _PARAM15_, Connect rooms in a loop: _PARAM16_, Additional paths: _PARAM18_ Delete unused terrain: _PARAM19_ => I would put inside parenthesis the whole parameters, because sentences in the events sheet don't have period. Also ensure there are commas everywhere and no capital letters after a comma? Something like: Generate dungeon (Room quantity: _PARAM7_, tile size: _PARAM1_ pixels [...]).
• Same for generating a cave.

Apart from that, looks very very cool! It will be a great example and extension 👍👍

[tristanbob]

In the example, sounds strange to use a random channel number, do you need a channel at all?

My main concern is when a new sound is initiated while the previous sound is playing, it seems to cut off the existing sound. This is not how sounds work in the real world, so it sounds unnatural. My method is ugly but it greatly reduces the chance of a channel collision. How do you recommend I accomplish this goal?

Blocking the room entrance is a real gameplay stuff that should then not be under the "UI" group (where I expect only to see stuff related to the interface, not the gameplay itself)?

I have not spent a lot of time preparing the example for submission, but I will work on that now.

A few typos:

• Caculate the number of grid
• Generate dungeon. Room Qty: _PARAM7_, Tile size: _PARAM1_ pixels, Map width: _PARAM2_ tiles, Map height: _PARAM3_ tiles, Terrain object: _PARAM4_, Room object: _PARAM5_, Wall object: _PARAM20_, Doorway object: _PARAM21_, Hallway object: _PARAM6_, Pathfinding object: _PARAM13_, Min room width: _PARAM9_ tiles, Max room width: _PARAM10_ tiles, Min room height: _PARAM11_ tiles, Max room height: _PARAM12_ tiles, Hallway width: _PARAM17_ tiles, Create objects on layer: _PARAM8_, Max separation attempts: _PARAM15_, Connect rooms in a loop: _PARAM16_, Additional paths: _PARAM18_ Delete unused terrain: _PARAM19_ => I would put inside parenthesis the whole parameters, because sentences in the events sheet don't have period. Also ensure there are commas everywhere and no capital letters after a comma? Something like: Generate dungeon (Room quantity: _PARAM7_, tile size: _PARAM1_ pixels [...]).
• Same for generating a cave.

I'll get these wording and formatting issues corrected.

Apart from that, looks very very cool! It will be a great example and extension 👍👍

Thanks! I have a lot of fun making them. :)

[arthuro555]

How do you recommend I accomplish this goal?

Simply do not play a sound on a channel. It will only be cut off if you play a sound on a channel that already has a sound running.

[tristanbob]

Wow, I did not know that. I assumed it would be similar to playing everything on the same channel. Thanks for the insight!

[tristanbob]

Version 1.1.6

• Updated per recommendations
• Added juice and polish to example
• Cleaned up unused resources (and fixed problems caused by removing the wrong things)

Example game

https://victrisgames.itch.io/extension-dungeon-generator

Extension file

DungeonGeneratorExtension_1.1.6.json.zip

Project folder

DungeonGenerator_SourceFiles_1.1.6.zip

[4ian]

Awesome! I've added this both as an example and as an extension ✨ Many thanks for this, great example of an advanced "algorithm"! :)

[tristanbob]

It looks like the sound effects I used are free, but not for redistribution: https://99sounds.org/license/

PROHIBITIONS
You do not have the right to sell, sublicense, stream, or redistribute (even for free) the content downloaded from 99Sounds on its own or as a separate attachment from any of your work.

I will replace them tonight from this collection: https://sonniss.com/gameaudiogdc

d) Licensee may transfer the licensed sound effects to as many hard
drives, computers and friends as they see fit.

BTW, the music is Public Domain: https://freepd.com/

[tristanbob]

I worked on this example yesterday but it is not ready. Here is what I have done:

• Replaced sound effects with ones that can be distributed
• Converted WAV files to AAC (10 times smaller)
• Added dinosaurs to the cave dungeon

https://twitter.com/VictrisGames/status/1440185081079873544

My goal tonight is to submit a pull request on the examples repository. I believe that would be the best way to reduce the amount of work others have to do.

Just to be clear, I am only changing the example. The extension does not need any changes (that I know of).

[4ian]

Sounds good, please open a PR on the examples repository (and close this one) or if it's too complex feel free to submit your files as usual! :)

[tristanbob]

I submitted a pull request for the updated example, so I am closing this extension issue.

https://github.com/GDevelopApp/GDevelop-examples/pull/118