I am trying to build a complex 3d maze generator. The maze will need a random spawn location, collectibles required to get to the next level, traps, puzzles, and a portal in the middle of the maze. Also, I will need to be able to set different difficulty levels these levels will be used when generating the maze and will dictate the size, number of traps, number of puzzles, and number of necessary collectibles. Does anyone know about some resources that would be helpful in building this?
Maze generation isn’t a simple deal, at least not when dealing with making it work with puzzles, as this requires the maze to meet some specific requirements, so no real simple answer. There are many algorithms out there to generate maxes. You want traps and puzzles, these elements are usually generated after the layout of the maze has been generated itself. There are quite a few steps to this.
For generating the maze itself I prefer a heavily modified algorithm based off of algorithms like Prim’s algorithm. One of the problems with many algorithms, is that if you’re trying to generate a maze with a set start and end, instead of generating the start and end based off the resulting maze, most algorithms have the problem that the path may be extremely short. The algorithm below addresses this problem by generating the maze in two sections, one from the end, and one from the start, then finding the tile on the border between the two sections that has the total farthest distance. That does not mean you have to use this, experiment with other generators, get used to the commonalities between them, when you feel you understand how they work, and not just copying them, them you will have the understanding to do the rest. But experiment with many algorithms and fine one that creates the look your going for. I will suggest an algorithm below, but like I said, don’t feel it’s the only one, it’s not, there’s thousands of ways to make mazes.
For this example imagine we have a class for a tile that contains the following information:
class Tile {
bool up; // Whether the wall upwards it open, true is open, false is closed
bool down; // Same as above, for down
bool right; // Same again
bool left; // And again, false is closed, true is open
byte section;
int dist_start = -1;
int dist_end = -1;
bool visited;
}
Pseudocode:
Make 2D array of Tiles
Make a Queue
Set start and end tiles to have no walls open (all bools except visited false)
Set start tile section to 0
Set end tile section to 1
Add starting tile indexes to the top of queue
Add Ending tile indexes to the top of queue
While there are tiles in the queue
Choose the tile on the bottom of the queue as A
if A.section = 0 AND A has a neighbor of section = 1 AND A hasn't been marked as a border
mark A as a border (Add to list of tiles)
Choose a random neighboring tile that hasn't been visited as B
Set B.section = A.section
If B.section = 0
Set B.dist_start = A.dist_start + 1
else if B.section = 1
Set B.dist_end = A.dist_end + 1
Set the proper bools on A and B to true (determine direction)
Set B.visited = true
Add B to the top of queue
If A has at least 1 unvisited neighbor
Add A to top of queue
// At this point every tile on the maze grid is used
Set variable max = 0
Set variable max_tile_a = null
Set variable max_tile_b = null
For each tile in border list as A
For each neighbor of section = 1 as B
sum A.dist_start and A.dist_end as dist
if dist > max
max = dist
max_tile_a = A
max_tile_b = B
// At this point every tile on the maze grid is reachable
Connect max_tile_a and max_tile_b together (set the bools, determine direction)
Add max_tile_a to queue (since queue from before is empty you may reuse it)
Set max_tile_b.dist_start = max_tile_a.dist_start + 1
while queue has tiles in it
get tile from bottom of the queue as A
for each neighbor of A with section = 1 as B
if B.dist_start = -1
Set B.dist_start = A.dist_start + 1
Add B to end of queue
// At this point every tile has a distance from the starting point
// To find the path from Start to end, start at the exit and iterate backwards, the next node in the path
// will be the only neighboring node with a lower dist_start than the current
At this point you’re ready to set traps and puzzles up. An example puzzle is a door and key, if you walk backwards as described above, while moving towards the starting place, you may randomly select any tile to become locked. When you do this, add 1 to a counter of how many keys are needed, then as you’re walking back if there’s at least 1 key to be generated, decide whether to take a path when you reach an intersection and place a key somewhere down the path and subtract 1 from the needed keys. This guarantees the keys needed are always found before the door and can not generate behind them. This system also forks for specific keys, like you need key A specifically to open door A, key B for door B and so on. To do this you’d make a list, as you make a door give the door an id, store that id in the keys list, then when you generate a key choose a random id for the key from that list.
As you’re tracing packwards, iterate through any intersections you want as well, and randomly assign those tiles to be trap rooms or etc. To help this in the Tile class you may you may add another piece of data, “type” which stores what type of room it is, normal, trap, look, door, or more specific, normal, loot, door, spikes, pit, enemy, falling_floor, etc for different types of trap rooms.
Note that the system above for the doors isn’t only limited to doors, need to make any system that requires a component elsewhere in the maze, you can use that system, and expand it, the component required could even require components of its own, the hard part has been done, generating the map, the rest is just iterating through the maze and making decisions on the type of room it is.
Now that the maze itself has been generated you can go through the maze array and based on the tile data place the physical objects in the map. I was going to provide some sample code, but as I was coding it I wasn’t even half done and it was already 103 lines so I stuck with the pseudo code, which should still give a fairly clear idea of the processes involved. Obviously you don’t need to follow the algorithm above, there’s many other ways to generate a maze, I was just suggesting one such way. As unreliable as Wikipedia can be, the Wikipedia article on Maze Generation Algorithms actually shows some example algorithms, many of them far simpler than the one above. The advantage of a system like the one above, is that it can only generate a short maze if the start and end are within a tile or two of each other and interfere with the other one’s spreading, so when choosing random location, just don’t do that
The algorithms on the Wikipedia page all could potentially create a direct path randomly, so be careful. It’s possible to circumnavigate this by creating a layered generation, imagine generating a small maze, where this maze doesn’t represent the maze itself, but a organization of smaller mazes, each maze having a start and end point in the middle of one of the sides, the sides dictated by the smaller maze where instead of rooms with walls, the smaller maze represents entire mazes and which sides their entrances or exits are on. Since all the generators on the Wikipedia page guarantee that all tiles are reachable from any other tile, the starting and ending locations on each maze are guaranteed to be able to connect. This is a project where you should feel free to experiment, there’s a lot of complex but fun things you can do to make things more interesting, but covering all of them would take a stupid amount of text, even more than already here. So I leave that to you.
So… go simple first, instead of all that
Build the maze generator, there alot of algorythims that allows to building maps, check some of them out, I’ve already heard of, and used: Cellular Automata and Drunkard Walk, search for the one that most fits your style and then implement it
after that, you can make spawns, traps, portals and collectibles as different objects, make references to them in you generator class, and set values for the minimun and maximum spawn value, and them randomly instantaite them in on tiles that don’t contain walls (Check the unity Scavengers tutorial, there is a lot to learn from there)
puzzles would be complicated since they mostly have to be man-made to work well, so I suggest you making some prefabs of puzzles and then instantiate then
your question is too complex, maybe you should study more absic before going big? what’s your experience with unity and c#?