3
\$\begingroup\$

I made a maze generator in python that outputs in CLI. With mazes that are extremely big, it can take a while to output. I want to know if there is any way to increase the efficiency of this code. Here it is:

import random
def mgen(size=3, disallowedcoords = [[]]):
    try:
        def canmove(coords, size, coordslist, disallowedcoords, coordsarray):
            actuallist = []
            for n in range(len(coordsarray)):
                actuallist.append(coordsarray[n][0:2])
            actuallist.extend(coordslist)
            actuallist.extend(disallowedcoords)
            canmoveto = []
            if len(coords) == 3:
                coords = coords[0:2]
            #--------------------NORTH CHECK--------------------
            if [coords[0], coords[1]+1] not in actuallist and coords[1]+1 != size: canmoveto.append(0)
            #--------------------EAST CHECK --------------------
            if [coords[0]+1, coords[1]] not in actuallist and coords[0]+1 != size: canmoveto.append(3)
            #--------------------SOUTH CHECK--------------------
            if [coords[0], coords[1]-1] not in actuallist and coords[1]-1 == abs(coords[1]-1): canmoveto.append(2)
            #--------------------WEST CHECK --------------------
            if [coords[0]-1, coords[1]] not in actuallist and coords[0]-1 == abs(coords[0]-1): canmoveto.append(1)
            #RETURN:
            return canmoveto
        def move(coords, direction):
                if direction == 0: return [coords[0], coords[1]+1]
                if direction == 1: return [coords[0]-1, coords[1]]
                if direction == 2: return [coords[0], coords[1]-1]
                if direction == 3: return [coords[0]+1, coords[1]]
                else: raise Exception("ERROR CODE: 0001. DIRECTION NOT IN 0-3.")
        previouscoords = [-1, -1, -1]
        coords = [random.randint(0, size-1), random.randint(0, size-1), -1]
        while coords[0:2] in disallowedcoords:
            coords = [random.randint(0, size-1), random.randint(0, size-1), -1]    
        coordsarray = []
        coordslist = []
        coordsarray.append(coords)
        coordslist.append([coords[0], coords[1]])
        success = 0
        iterations = 0
        backtrack = 0
        while len(coordsarray)-1 != size**2:
            movement = canmove(coords, size, coordslist, disallowedcoords, coordsarray)
            if len(movement) != 0:
                previouscoords = coords
                startback = False
                iterations += 1
                direction = movement[random.randint(0, len(movement)-1) if len(movement) > 1 else 0]
                coords = move([coords[0], coords[1]], direction)
                coords.append(direction)
                coordslist.append(coords[0:2])
                coordsarray.append(coords[:])
                success += 1
            if len(movement) == 0:
                backtrack += 1
                coords = coordslist[(len(coordslist)-1)]
                del coordslist[len(coordslist)-1]
    except Exception as e:
        return coordsarray

   

def displaymaze(coords, size, grasschance=0, brokenwallchance=0, questionchance=0):
    linkcoords = []
    for n in range(len(coords)):
        linkcoords.append([(coords[n][0]*2)+1, (coords[n][1]*2)+1])
    for n in range(len(coords)):
        if coords[n][2] == -1:
            pass
        elif coords[n][2] == 2:
            linkcoords.append([coords[n][0]*2+1, coords[n][1]*2+2])
        elif coords[n][2] == 3:
            linkcoords.append([coords[n][0]*2, coords[n][1]*2+1])
        elif coords[n][2] == 1:
            linkcoords.append([coords[n][0]*2+2, coords[n][1]*2+1])
        elif coords[n][2] == 0:
            linkcoords.append([coords[n][0]*2+1, coords[n][1]*2])
    """
    for n in range(len(coords)):
        if coords[n][2] == -1:
            links.append([coords[n][0:2], coords[n+1][0:2]])
            links.append([coords[n+1][0:2], coords[n][0:2]])
        elif coords[n][2] == 0:
            links.append([coords[n][0:2], [coords[n][0], coords[n][1]-1]])
            links.append([[coords[n][0], coords[n][1]-1], coords[n][0:2]])
        elif coords[n][2] == 1:
            links.append([coords[n][0:2], [coords[n][0]-1, coords[n][1]]])
            links.append([[coords[n][0]-1, coords[n][1]], coords[n][0:2]])
        elif coords[n][2] == 2:
            links.append([coords[n][0:2], [coords[n][0], coords[n][1]+1]])
            links.append([[coords[n][0], coords[n][1]+1], coords[n][0:2]])
        elif coords[n][2] == 3:
            links.append([coords[n][0:2], [coords[n][0]+1, coords[n][1]]])
            links.append([[coords[n][0]+1, coords[n][1]], coords[n][0:2]])
        #FINISH---------------------------------------------THIS NEEDS TO BE FINISHED LINKS SYSTEM!!!!!!!!!!!!!!!!!!--------------------------------------
        else:
            raise Exception("ERROR CODE: 0002. DIRECTiON NOT IN 0-3 WHILE LINKING MAZE PATHS.")
    """
    lines = []
    for n in range(size):
        currentline = ""
        if n == 0 or n == size-1:
            lines.append("██"*(size))
        else:
            for i in range(size):
                if i == 0 or i == size-1:
                    currentline += "██"
                else:
                    if [n, i] in linkcoords:
                        chance = random.randint(1, 100)
                        if chance <= int(grasschance):
                            currentline += "░░"
                        elif chance > 100-int(questionchance):
                            currentline += "??"
                        else:
                            currentline += "  "
                    else:
                        if random.randint(1, 100) <= int(brokenwallchance):
                            currentline += "▓▓"
                        else:
                            currentline += "██"
            lines.append(currentline)
    return lines

def maze(length=3, disallowedcoords = [], gc = 0, bwc = 0, qc = 0):
    """GC -> GRASS CHANCE. BWC - > BROKEN WALL CHANCE. QC - > QUESTION CHANCE IN PERCENTAGE"""
    return displaymaze(mgen(size=length, disallowedcoords = disallowedcoords), length*2+1, grasschance = gc, brokenwallchance = bwc, questionchance = qc)
while True:
    try:
        length = int(input("How long + wide do you want the maze to be?"))
        gc = int(input("What do you want the chance of grass to be in the maze?"))
        qc = int(input("What do you want the chance of question marks to be in the maze?"))
        bwc = int(input("What do you want the chance of broken walls to be in the maze?"))
        input(">>>")
        display = maze(length = length, gc = gc, bwc = bwc, qc = qc)
        for n in range(length*2+1):
          print(display[n])
    except:
        print("Invalid values.")

Is there any way to increase the efficiency of this code?

Important Side Note: With very big mazes it might seem like it doesn't work but this is because Python automatically cuts the maze to the next line, this is something that is unfixable and it's a problem with the Command Line Interface. Copying and Pasting it to notepad will fix this.

\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

First, a random list:

  • There's no strict benefit to having canmove and move as being nested functions. They're not closures over any variable so far as I can tell; so just move them to the global scope.
  • Consider adding PEP484 type hints
  • Make an Enum for your four cardinal directions instead of relying on integer magic
  • displaymaze does not display anything, since it does not print; perhaps call it format_maze.
  • Expand your gc = 0, bwc = 0, qc = 0 variables to spell out English words

This block:

except Exception as e:
    return coordsarray

is a deeply bad idea. You're saying that if anything goes wrong, including running out of memory, a None where there shouldn't be one, index errors etc., give up and return what you have so far. Even stranger, if nothing goes wrong, this function is guaranteed to throw away all of its work and return None. The fix to this, I think, is:

        if len(movement) == 0:
            backtrack += 1
            if len(coordslist) == 0:
                return coordsarray

and delete your try/except.

When I tried running this, it was extremely slow for a 50x50 maze. Did you implement an off-the-shelf algorithm or is this your own? If it's your own, I encourage you to do some reading and compare to more efficient, well-established algorithms. 50x50 should execute "instantly" by human perception.

\$\endgroup\$
1
\$\begingroup\$

Took me a while to understand it all because I had no prior experience with maze generation. Your approach looks like a pretty good implementation of the "Randomized depth-first search" algorithm. I think it's not the most efficient algorithm but one of the easiest to implement.

Apart from the good comments by @Reinderien, I have one tip. When checking whether a coordinate is in a list of coordinates, it can be faster if you use a set of coordinates instead of a list; you'll have to represent coordinates as tuples instead of lists. I didn't measure it, but I guess I gained most time in canmove(). My laptop runs a 50x50 maze in 1.4 second and a 100x100 maze in 30 seconds.

With this in mind, I did some refactoring. I renamed some of the variables that were not obvious to me. I should have changed coordsarray and coordslist as well (if you don't know the algorithm, these variables look as if they do the same) but instead I put some comments to explain them. Comments in general help me in the sense of being an extension of my working memory. You can see my code here: https://hastebin.com/kareyugozu.py

Maybe another improvement is to make coordslist an instance of collections.deque and then maybe you could make coordsarray a set as well. But I haven't looked into it that deeply yet.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.