I'm taking a break from pathfinding and AI to go back and talk about the raw level design in The Cluster; More specifically the procedural generation.
The entire world in The Cluster is procedurally generated at runtime, though it is consistent, meaning that the world will be the same every time you play. However, this is strictly a design choice, not a technical limitation, and I'm considering including some kind of bonus areas or similar that will be different every time.
To give you an idea of the current state of the game, here is a simple playable demo (requires Unity plug-in):
Controls: Arrows to run, Ctrl to jump.
This demo is just a "tech demo" and features no enemies and no way to win. It extends infinitely to the right.
Back in 2007 I explained the procedural level generation of the game. The game has changed a lot since then - among other things it has turned from a tile based 2D game into a 2.5D game with 3D graphics - but the basic method of generation is still the same.
You can actually see the maze map in-game in the demo above by pressing 2. Press 1 to hide the world to only see the map. You can zoom a bit out by pressing Z, X zooms back in, and you can pan around using WASD. Press Esc to reset the camera.
A map of the maze that the area is based on.
The map overlayed onto the actual generated area.
The generated area by itself.
One feature not explained in depth on the page linked to above is the placement of locked doors and keys in the game. The game places locked doors and keys in a "perfect way" such that it is always necessary to find all keys and unlock all doors to be able to proceed, and a "deadlock" will never occur, where the key for a door is placed behind that door. The placements are calculated using a simple algorithm I came up with which is based on dividing the area up into a binary tree and then placing keys in leaf nodes and locks in inner nodes in a specific way. Several years after implementing it, I found this article about "Environment Tree" at Squidi.net. It's basically the same algorithm, so rather than explaining it myself here, I'll refer to that.
A nice aspect about the algorithm is that it supports placing keys both sequentially and nested. In the screenshots above, the red door is sequential in the sense that all the following keys and doors are on the far side of the red door, so once you've gone through it, you don't have to go back. The green door, however, is nested. You go through the green door, pick up the blue key, and then go back out the green door in order to proceed. The algorithm doesn't have separate handling of sequential versus nested key and door placements; these are just emergent properties so to speak.
If there's any interest I can cover other aspects of the procedural generation in The Cluster in coming blog posts.
6 comments:
Very cool! I've been fooling with procedurally generated mazes in my own project for a while and I may have to steal your mechanism for keys and doors. :)
That sounds great Mark! If I can follow your project anywhere, let me know. :)
I just stumbled upon this and am impressed. I would like to know more about the procedural generation, as I'm working on a game that involves it (an RPG, but still...). I'm interested to see how you've gone about generation process.
Thanks @Ithmer. The procedural generation is pretty involving, taking up many thousands of line of code, and many small aspects of it could fill a blog post on its own.
Are there any particular aspects of the generation that you're particularly interested in? I.e. a "How did you achieve X?" sort of question would be a good starting point.
I'm just starting with procedural generation, computer game design in general in fact, but I wanted to focus on building levels and content that way as it suits my tendencies, and I hope learning the coding bits bass-ackwards will meen I avoid the common pitfalls.
So notwithstanding the fact I don't even know how to turn a 2d array into a template for 3d terrain, you called the map a modified depth-first search. Is there a random starting set of nodes connected in every possible way, and you pick routes between a a starting point and a random target with random biasing until you get to the node marked finish?
Ok it can't be that because with nodes looped that heavily I think a depth first search would keep going down till it found it, leading to a structure closer to a net than a branching tree. So I don't get it, how do you decide the ways it connects?
@Josh: Have a look at Think Labyrinth - an excellent resource for everything on maze generation: http://www.astrolog.org/labyrnth/algrithm.htm
The "modified depth first search" I referred to is what Think Labyrinth calls the Recursive Backtracker algorithm. I then added some hacks on top to make the mazes look more interesting: I made certain cells inaccessible, and also stopped the generation before all cells were filled out (if the target cell had already been reached).
Much later I discarded that in favor of a hybrid algorithm I came up with that has more desirable properties for my specific needs, but that's for another time. I think that the Think Labyrinth site has plenty of inspiration to get started with creating interesting mazes that can be used for levels.
Post a Comment