I am making a maze game where the player navigates randomly generated mazes. I have manage to create a level generation system (with simple code as i am new to coding) where it has a 50% chance of spawning squares in each space in the grid. The player then has to get to the other side like a classic maze.
You may be noticing that if i generate every level with a 50% chance of an obstacle spawning on each square - it will be impossible for the player to reach the end every time. However, i want there to be a mechanic where the player has a limit amount of âdashesâ where they can pass through an obstacle of one block thick to reach the end. This will allow the player to create their own path but still keeping a level of difficulty as larger obstacles/diagonals will not be bypassable.
The problem with normal, randomly generated mazes is that not every level is possible, a block might be blocking the start or end, there might not be a possible path to the end etc. I was trying to implement a system of checking if a level was possible using a tester which detected if a block was blocking it etc. but soon gave up as the preview kept freezing on a black screen. I then tried pathfinding but i wasnât able to make it work either. Additionally, all these methods did not take into account the mechanic i want there to be which adds another level of difficulty to the code.
I was wondering if there was a simpler way to check if a level is possible in general, but also if someone really smart could help me devise some code to not only see if a level is physically passable, but also see if there is at least one path possible using my mechanic of bypassing 3 or so obstacles per level.
I apologise for my ignorance, and welcome any help, In addition i have attached a screenshot of an example level.
(Player in grey, End in green, Obstacles in red).
*Player is in yellow
Or it would figure out the amount of âdashesâ needed to complete the level this way, and give the player that same amount. This way it could range from 7 dashes to 3 per level and if the player doesnât find the âperfect wayâ A.K.A. the way the system figured the level out, they wouldâve failed the level.
Eg. in the screenshot i have attached to the first post, the level can be beat by passing through 7 blocks without going through diagonals or blocks that are more than 1 tile thick. This would mean the player would be given 7 âdashesâ to beat the level and find the optimal path.
Are you or have you used the maze generator extension?
https://wiki.gdevelop.io/gdevelop5/extensions/maze-generator/
I think youâd need some type of AI to run through the maze and figure out the most efficient way.
But maybe approach it a different way - create a solvable maze and then plonk on a few extra blocks along the solution route.
Fool question: physic engine in GD donât go with water, isnât it?
Otherwise, it should be easier to use water descending in the labyrinth to indicate if the solution exists or not.
But i am dreaming!
In classic programmation, in the past, we used BackTracking method.
Xierra
The thing is, i donât want it to be a classic maze. Think of my idea to be more of a puzzle, randomly generated where the player has to solve it with certain moves, not a âfollow a pathâ kind of maze. It would still need to check if levels are possible.
Thanks for the suggestion though.
@MrMen Is there a way to create such an AI in Gdevelop?
Otherwise i could try your other suggestion.
Thanks for your help.
Possibly, but itâd probably take a lot of work. And I wouldnât know where to start on that one.
You could start with the maze extension. If you donât use it then maybe you can study itâs functions. It has a builder and solver.
The pathfinder might be one way. Add blocks, check for path, add blocks check for path. You could add a certain minimum number of blocks and also add a certain number of blocking blocks.
It might be easier to create a path with temporary objects and then place blocks around it. Add extra blocks as needed.
Hey, Iâve got a solution that can help with this without lagging out the game entirely.
Before the player starts the level, have an invisible block start at the beginning and randomly choose to go left right up or down, not going to a space itâs already been to. After itâs made that path, the remaining tiles can get a 50/50 if they stay or not.
The code would be simple, just a random variable on the map setter, but let me know if this works.
I think people are forgetting to read your original prompt carefullyâŚ
Being able to eliminate some obstacles makes determining a solution much more complex. With a static maze, you can test pathways with certainty. The typical way to find a solution (that I know of) is to have an algorithm that follows pathways and keeps track of branches. At each branch, it picks one option, then follows that until either finding another branch, the goal, or a dead end. When a dead end is found, it goes back to the last branch location to try the next option, until all branches are exhausted.
This doesnât work quite the same way when some of the walls can be eliminated, since that means there are potential new pathways all over the place. Youâll essentially need to start treating every wall as a possible branch, until it is proved that destroying that wall makes the solution unreachable.
I think it is a really cool idea that makes maze-solving a lot more interesting, but checking for a solvable puzzle is going to be pretty difficult. I guess the mathematics term for this is âshortest Path with k-Wall Crashesâ, try reading about that and see if your mind explodes 
There is a âcheatâ (proper?) way to avoid generating puzzles and then checking for solvability. Like others suggested for a regular maze, you could focus on making it so that the generation algorithm always creates something solvable. This could be just as complicated depending on how you do it, but some methods would be simpler. For example, instead of just giving 50/50 chance to each tile, you could generate the maze using a âdigâ method. Fill every space, then create a path to the exit by removing walls along a somewhat random track. Along the way, skip up to 3 walls, or however many you want the player to be able to remove. Then you can also randomly dig out other parts of the maze, but youâll know that thereâs at least one solution.