Generate maze with path of specified length

Question

My question is pretty simple, but very difficult to do. I have size of maze and length of path. I need to find path that is exactly specified length. Maze however can contains valid longer paths. Maze always starts on [0, 0] and end on [size X, size Y]. Example of 5x5 maze with path length 13: (X: wall, -: path)

---XX
XX-XX
---XX
-XXXX
-----

6x6 maze, 11 path length (contains another path of size 15) - is valid

------
XX-XX-
---XX-
-XXXX-
-XXXX-
------

I already tried many algorithms, but nothing worked. It would be nice if someone could give me some tips as to what i'd need to do or where i could read up on for this problem.

Answer 1

First the logic as generic concept: You start in the Left top Corner, giving the cell a 0. Now for all valid cells adjecent to this cell, give it a 1. Continue moving forward, always in all direction, increase cell by 1. When you are at the bottom-right, you have your shortest route!

Now we need to look at the directional impact. When we move away from the bottom-right, we have to compensate this with a step forward again. So the minimum steps will be 12 and each larger path will be p + 2. In the path of 15, we move 2 steps away from bottom-right (step 5 & 6) so path lenght = 12 + 2*2 = 16.

Generating a maze must be a bit random but at the same time it should fullfill the request of path lenght. If we want to move one away from bottow-right to generate path lenght we need to have at least 1+2 same moves in forward direction (right-down-down or down-right-right). If we want to move 2 away, we need 2+2, etc.

If you realy want to go random, you need to use backtracking, you try each posibility and check if steps can still be done. Lets take following example, we want 14 steps): when we place 7, cells [2,3] & [4,3] get blocked. When we place 8, cells [2,4], [2,5] & [3,5] get blocked. Now there is no space left to move left or up so placing 8 on [4,4] is not possible. 8 can get placed on [2,4].