Legacy GM Maze/Room/Level Generation and Loading Time

Wile94

Member
Hi, I've recently coded a maze generator inside a ds_grid. Each cell has a string value like "0000" or "1010", etc. Each number represents a wall/exit (0/1) around that cell (left-right-up-down), having a total of 16 combinations. Then I run a script that seals most of the "one way exit" cells to give it a more cave-like configuration. Lastly, I put a start cell point and an exit cell point so I can run a path finder to determine the most direct-critical path. Once the maze is done, I can export it and replace each cell with a template made out of walls, platforms, etc. (My game is a platformer, but it should work in every kind of game).

https://thumbs.gfycat.com/AltruisticBothCopperhead-mobile.mp4

My goal is to generate random levels with random rooms kind of an spelunky/binding of isaac hybrid. Now, I have the next concern:
The generator runs really fast, in fact, I can put my room speed up to 999 and the maze is generated instantly (it all depends on the size of the grid). But I'm aiming to generate around 4-6 levels with at least 8-12 rooms each (with different sizes) and it will take time mostly because the process is step-wise. I'm talking about a few seconds not that much, but maybe the player will find it kind of a turn down? I don't know, Spelunky creates its levels almost instantly every new run. I came up with these solutions for this issue:

-Put the maze generator inside a loop (for example: while(!endProcess) { generate } or do { generate } until { endProcess }). This way the fps will drop a lot but only around a few steps until the levels are generated.
-Use delta timing and let the generation run as fast as the user's processor can.

What are your thoughts on this? Maybe it's more of a design problem rather than a programming problem (if this is a problem at all). A lot of games (like Enter The Gungeon) have their loading screens and the player has to wait anyway.
 
If your just talking about a few seconds, presumably only once every.. 10 minutes? Then it's not a problem. Just design in a nice waiting sequence for the player. This could be as simple as a loading screen, to something more creative like let the player see the level being created.
 

Wile94

Member
If your just talking about a few seconds, presumably only once every.. 10 minutes? Then it's not a problem. Just design in a nice waiting sequence for the player. This could be as simple as a loading screen, to something more creative like let the player see the level being created.
Yes, I guess you're right. I had this concern specially because I'm designing my game to have the "die a lot" roguelike mechanic (you fall into a spike and you're probably screwed), so I'll probably generate a new area once it's entered and not the complete run everytime.
 
I had a very similar issue, my dungeon generator runs incredibly fast but the tiling of all the grid can cause it to hang for a second. To solve this I made the y loop of the grid into a loading function, so it passes one step of the y at a time and every pass of the y increases the total loaded game by one. Once all the ys are done the dungeon is loaded. Technically this is much slower than just letting it all run at once but it locks the game up temporarily which I found concerning.
 

TheouAegis

Member
You got the algorithm to work, that's the most important part. But you are using some of the slowest methods. A grid is horribly slow; personally, I use a 1D array or even a buffer. Second, I use reals, not strings. "1010" can be reduced to 10 or $A and checking if each bit is set it's going to be faster than looping through the string calling multiple functions over and over. This might sound like micromanaging, but it's actually not as micro as it seems. Even a simple maze generation algorithm can be sped up by seconds just by getting rid of grids alone.

My third tip is to check if you have any randomization loops (it doesn't sound like you do in this project, but I'll still throw this out there). People tend to erroneously think an outcome is only truly random if every attempt is random, but only the first attempt needs to be random and then just gradually check each option if it's invalid. For example
Code:
do x=irandom(room_width) until !place_meeting(x,y,object_index);
vs.
Code:
x = irandom(room_width) & ~7;
while place_meeting(x,y,object_index) x+=8;
Anyway, in the case of maze generation, you are typically only dealing with four directions. That means a random loop like that has a 25% chance for each direction to get hung up. If three directions are blocked, that's a 75% chance to lock up.
 
Last edited:

Wile94

Member
You got the algorithm to work, that's the most important part. But you are using some of the slowest methods. A grid is horribly slow
I know strings are pretty slow, but a ds_grid? For what I can tell those are pretty fast, In fact I use a grid to store reals to manage the collisions in my platformer (whenever is a wall = 1;empty = 0; etc) and it's lighting fast. The only time it drops fps is when I loop through the grid to autotile the room.
Maybe you're referring using a grid in this particular algorithm/storing strings inside a grid?
 

Yal

šŸ§ *penguin noises*
GMC Elder
Strings sounds more like the bottleneck here, you make the data take up at least 4 times more space and force slower comparison and split operators.

There's another even more important advantage to using numbers than strings, though... getting tiling data for free. If you assign DIFFERENT weights for each side of the tile...
upload_2019-11-4_23-54-41.png
...you will get a number between 0 and 15 for its collision data. Now just have 15 different tiles, arranged so that their shape directly matches which of the sides there's collisions next to, and bam, you can get the tile from the collision data. (For instance, tile 3 should be a corner with walls above and to the right, tile 0 be a single solitary block, and tile 15 the middle of a wall, with collisions on all sides)
 

Wile94

Member
There's another even more important advantage to using numbers than strings, though... getting tiling data for free. If you assign DIFFERENT weights for each side of the tile...
View attachment 27380
...you will get a number between 0 and 15 for its collision data. Now just have 15 different tiles
That's really cool. How would you "weight" for 8 directions in a 47-piece wall tileset? Maths ain't my thing really haha. Currently I'm using a 9 digit real for that (200000000/211111111 -> each 0/1 is a direction) and it's really messy. It's already coded and it works well but...

EDIT: Never mind, I'm finally looking into binary and bitwise operations... The answer to all my questions :eek:
 
Last edited:
Top