Hello everyone!
What's that? A devlog? Yup, I've been busing working on AdVRnture as much as possible during nights and weekends. And if this is your first time to the Hypernoodle Games website, welcome! Project AdVRnture is an exploration and collecting game where you explore a labyrinthine, procedurally generated world seeking treasures and uncovering secrets behind ancient monuments. More about the game can be seen on its page HERE. Development is progressing steadily, and I am working towards a demo of the game's movement tech and first area to be released to you as soon as possible. In the mean time, these past few days I've been working a bit on the procedural level generation of AdVRnture's maze-like main zones. I'd like to break that system down here for my own benefit as well as for anyone who may be interested. So let's talk about the flavor of level generation being used, how a level is built, and what more can still be done.
Which flavor of randomness would you like?
Right away when thinking about level generation for AdVRnture, I was drawn to the way that Derek Yu created the levels for Spelunky. Primarily, it's a system that would allow me to slot together hand-crafted pieces into a randomly flowing whole. It also has the benefit of being well documented and studied at this point, so there is a wealth of easily understood resources to help me build my own version. Thus it was decided, each area of the AdVRnture would would be a Spelunky-esque randomly generated labyrinth, hooked together by a hub town much the same way as Hyper Light Drifter's starting city connects its four world zones.
Build Spelunky, kicked over.
So the plan: start by cloning the Spelunky level generation system, only stretching horizontally rather than vertically, and customize it from there to fit the design goals of AdVRnture.
A couple resources were invaluable when setting up the basic algorithm:
- An html based Spelunky Classic level generator that breaks down the rules and generation process, which can be found HERE.
- A tutorial series on Youtube by the talented Blackthornprod, which describes how to create a roguelike level generator in Unity. Although I am using Unreal Engine for this project, the logic was straight forward enough to carry across engines. The first video of that series is HERE.
With these tools and the UE4 documentation in one monitor and the UE4 editor in another, I was able to create a system that functioned as the following:
-Start by pre-determining all the pathways of a dungeon. From an either pre-determined or random point along an arbitrary "top" row, step through the grid by selecting a random direction to move in and checking whether or not movement in that direction is possible. If not, pick a different direction. During movement along this critical path, movement back towards the "top" is not possible, and left-right movement is favorable to downward movement. When movement to a new cell is impossible it is assumed that the system has reached the "bottom" of the level bounds. Also, for each cell the system can add extra exits to the unused and unblocked sides, which will be filled in during the next step.
-Now that the critical path has been determined, the system steps along that path and finds all un-resolved exits, creating side-paths using the same algorithm as before but allowing movement towards the top when no other direction is possible. The length of these side paths is limited to a certain number of cells to prevent side paths from becoming too long. Finally, each time a new cell is placed it checks if any surrounding cells exit into it, and adds exits to the space as needed.
-This whole process creates an array of cell structs which the system can sift through one by one, spawning a cell blueprint with correct exits for each array item.
-In this initial version, the final cell of the critical path is set as the "goal", and a special cell blueprint is spawned. This is also the case for a "checkpoint" cell halfway down the critical path.
Here the simplest template cell blueprints are being used to generate a basic dungeon (This is using the current level generation system, but stripped down to the absolute bare minimum).
From utter chaos, narrative flow emerges.
Once that system was built, I could begin looking into adding a "narrative flow" to my random grid of cells. Dead Cells was a huge help here, and I found a video which I can't seem to locate anymore where one of the developers outlined both their level generation system and the narrative flowcharting that guides the placement of key set-pieces and items within the levels. This was the next piece of the puzzle for my own level generation system, along with needing to be able to create many different styles of level by tweaking the parameters of and giving different blueprint sets to my Dungeon Builder blueprint.
-Everything within the original Dungeon Builder remains the same, up to determining and spawning the cell blueprints.
-Custom data assets were created, including a Cell Style data asset, Dungeon Summary, and Item Pool.
-Cell styles list out all the possible cell blueprints for reach configuration of exits a cell can have. Cell styles have a priority, a rarity, whether or not they are a one off or spawn multiple times, and if so, whether they can spawn anywhere or at certain percentages along the main path.
-Dungeon Summaries contain a default Cell Style to use when no variations are waiting to be placed, an array of Cell Style variations for that Dungeon, and an Item Pool to guide item spawning, among other details.
-An Item Pool is a simple data asset that contains the names of all items which can be randomly spawned within the dungeon, and each item's "rank" within that dungeon. An item's rank determines if only one copy should be spawned within the dungeon, and if it must spawn or is optional.
The dungeon template creator goes cell by cell, asking the dungeon summary for a cell that can be placed given information from the template, such as which sides of the cell have exits, that cell's distance along the critical path as a percentage based on critical path length, and whether it is in fact on the critical path or a side path. The dungeon summary takes that information and updates each cell style listed in the summary of the current percent along the critical path. In turn, each style will return whether or not it is a candidate to spawn in that cell based on that percentage and whether or not the style contains a cell with the needed exits. The summary then sorts through the candidate styles, sorting them by priority and rarity, and sends one back to the dungeon builder to spawn.
(making the cell walls irregular does a great deal to break up the grid)
Once all cells have been spawned, items and all sorts of extra goodies can be added within the dungeon based on the item pool. Each spawned cell gives the dungeon builder an array of the potential "item spawn locations" it contains, with can be placed within the blueprint by hand or procedurally. Items are ranked within a Dungeon Summary's Item Pool. An item can be a "story critical" primary item, a secondary one-off item, or any of a variety of less story critical odds and ends. Likewise an item spawn location can specify the maximum "rank" of an item to spawn at that location, and the algorithm will attempt to fill the location with that item before moving to one with a lower priority if, for instance, all one off items have already been spawned.
And that's all for now, that's the level generation system for AdVRnture as it stands, still comparatively early in the game's development.
Where do we go now?
The system is still young, and while some recent changes to logic within the dungeon summary and cell style have made level editing much easier, there is still work to be done.
A more visual representation within the dungeon summary of the room flow would be nice, as right now in order to see what percentage(s) along the crit path each cell style wants to spawn along I have to check each data asset individually.
While theoretically 3 dimensional support is possible and the groundwork is there within the system to support it somewhat, it is not yet fully implemented. Once I had 2D level generation functioning I had to move on for the time being to other tasks.
Again, this is still just a couple iterations in on my first real attempt at procedural level generation, and it will likely change a great deal as development of AdVRnture progresses. I look forward to sharing more in the future, and putting up a playable demo of AdVRnture as soon as possible so that you readers can let me know how these levels feel.
What do you think of this sort of deep-dive? is it useful? Interesting? Please let me know if it's something you find beneficial or if my time would be better spent just focusing on the darn game.
Thanks for reading!
Jon