Make this backtracking maze-generation algorithm iterative
New here? Learn about Bountify and follow @bountify to get notified of new bounties! x

The following gist is a working implementation of a back-tracing maze algorithm:

https://gist.github.com/suchow/d446254351717ec57223af648bdc7696

 python maze.py
*****************************************
*         *               *             *
***** *** * ***** ******* * *********** *
*     * * * *     * *     *   *       * *
* ***** * * * ***** * ***** * ******* * *
*   *     * * *       *   * * *     *   *
* * *** *** * * ******* * * * * *** * ***
* *   * *   * *     *   * * *   *   *   *
* *** *** *** ***** * *** * ***** *******
* * *   * *   *   * *   * *   * *       *
* * *** * * * * * * *** * *** * ******* *
*   * * * * * * * *   * *     *     * * *
*** * * * * *** * *** * ******* *** * * *
* * * *   *   * *   * * *   *     * * * *
* * * ******* * *** * * * * ***** * * * *
* * *     *   * * * * *   *       *   * *
* * * ***** *** * * * *************** * *
*     *     *   * * *         *       * *
* ***** *** * *** * ********* ******* * *
* *     *   *   * *   *     *       * * *
* * ***** ***** * *** *** * ******* *** *
* * *     * *   * * *   * *     * *   * *
* * ***** * * *** * * * *** *** * *** * *
* * *   *   *   * * * *   *   *     *   *
*** * * * ***** * * ***** * * ********* *
*   * * * *     * *       * *       *   *
* * * * *** ***** ********* ******* * ***
* * * *     *       *     * *     *   * *
* *** ******* *** * * *** * *** * ***** *
*   *       * *   * * * *       * *     *
*** ******* * * *** * * ********* * * ***
*     * *   * * * * *   *   *   * * *   *
* *** * * ***** * * ***** * *** * ***** *
*   *   * *     * *       *   *   *     *
* * *** * * ***** *********** * *** *** *
* *   * *   *     *         * *   * *   *
* *** ******* ***** *** ***** *** * * ***
*   *     *         * *   *   * *   *   *
*** ***** * ********* *** * *** ******* *
*       *               *   *           *
*****************************************

Unfortunately, this algorithm breaks for large maze sizes (e.g., 100 x 100, 200 x 200) because the maximum recursion depth is reached:

File "/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/random.py", line 288, in shuffle
    for i in reversed(xrange(1, len(x))):
RuntimeError: maximum recursion depth exceeded while calling a Python object

This bounty is to modify this algorithm to that it is iterative and thus capable of creating a 100 x 100 and 200 x 200 maze without the above error.

awarded to gabrielsimoes

Crowdsource coding tasks.

4 Solutions


https://gist.github.com/subhashdasyam/56534c63ef0b5f0f714a5c3a162eddc4

Hi suchow,

I have modified your script slightly added the limit to the recursion, and its working now :)

Check the link

Regards
Subhash Dasyam

can you tell me what is the problem you are facing ?
Subhash Dasyam 4 months ago
nm got it you want to convert this to iterative
Subhash Dasyam 4 months ago
Hi Subhash — thanks for working on this. The goal here, however, is to adjust the algorithm so that it uses some stack-like data structure instead of a recursive function call. Increasing the recursion limit to 5000 allows a 100 x 100 and 200 x 200, but suffers from the same problem if you make the grid even slightly bigger (e.g., 300 x 300).
suchow 4 months ago

I believe gabrielsimoes' solution had one of the xx and yy swapped.

A similar solution that keeps the walk function:

https://gist.github.com/enj/e2d853ff2c5616ba79e63eb39cbeec4b

Where did you find a xxswapped with a yy?
gabrielsimoes 4 months ago

In my last year, i made a project in c programming that will generate a maze randomly or from a file when parameters can be (0:path/1:wall).

Also, it solve the maze to find the shortest path between two points (start/end).

The script i made, had no problem with the size!! it can work even if it's 10000 x 10000 size!! :D :D

if it's ok, i can submit it in C or we can even convert it in Python

View Timeline