Skip to content

Instantly share code, notes, and snippets.

@danbst
Created November 20, 2020 00:34
Show Gist options
  • Save danbst/7cc0d7043f456bb1989a8d0d21752eaa to your computer and use it in GitHub Desktop.
Save danbst/7cc0d7043f456bb1989a8d0d21752eaa to your computer and use it in GitHub Desktop.
Maze generation using Randomized Prim's algorithm
def maze(width=10, height=10):
def sides(field, x, y):
sides_ = []
if x > 0:
sides_.append((-1,0))
if x < len(field[y]) - 1:
sides_.append((1,0))
if y > 0:
sides_.append((0,-1))
if y < len(field) - 1:
sides_.append((0,1))
return sides_, [ field[y+sy][x+sx] for sx,sy in sides_]
import random
field = [ ['W']*width for _ in range(height) ]
field[1][1] = ' '
walls = [(0,1), (1,0),(2,1),(1,2)]
while True:
if len(walls) == 0:
break
wi = random.randrange(len(walls))
wx, wy = walls[wi]
del walls[wi]
ss, vals = sides(field, wx, wy)
if vals.count(' ') != 1:
pass
else:
sx, sy = ss[vals.index(' ')]
newpos = (wx - sx, wy - sy)
field[newpos[1]][newpos[0]] = ' '
field[wy][wx] = ' '
newsides, newvals = sides(field, *newpos)
for (nsx, nsy), v in zip(newsides, newvals):
p = (newpos[0]+nsx, newpos[1]+nsy)
if v == 'W' and p not in walls:
walls.append(p)
return field
@danbst
Copy link
Author

danbst commented Nov 20, 2020

██  ██████████  ██████  ██  ██████████  ██████████████  ██████████  ██  ██  ██████████████  ██  ██████████  ██████  ██  
    ██              ██  ██      ██      ██                          ██  ██              ██      ██      ██          ██  
██  ██  ██  ██████████  ██  ██████  ██████  ██████  ██  ██████████████  ██████████████████  ██  ██  ██████████  ████████
    ██  ██  ██      ██  ██          ██          ██  ██                      ██  ██          ██              ██  ██  ██  
██  ██████  ██  ██████  ██████  ██████  ██████████████████████████████████  ██  ██  ██████  ██████████████  ██  ██  ████
    ██          ██      ██      ██                                      ██          ██          ██  ██  ██  ██      ██  
██  ██████  ██████  ██████  ██  ██  ██████████████  ██████████████████████████  ██  ██████████████  ██  ██████  ██████  
        ██      ██      ██  ██                  ██  ██  ██      ██  ██      ██  ██                          ██      ██  
██████████████████████████████  ██████  ██████  ██████  ██  ██████  ██  ██████████  ██  ██  ██████  ██████████  ██  ████
    ██  ██                  ██  ██  ██      ██                          ██      ██  ██  ██      ██          ██  ██  ██  
██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  
                        ██      ██              ██                      ██      ██  ██  ██  ██          ██      ██  ██  
██████  ██████  ██████████  ██████  ██████████████  ██████████████████████  ██████  ██  ██  ██  ██████████  ██████  ██  
        ██                  ██      ██      ██                  ██  ██      ██      ██  ██  ██              ██      ██  
██████████  ██████  ██████  ██  ██████████  ██  ██████████████████  ██  ██████  ██████  ██  ██  ██████████  ██  ████████
                ██      ██  ██                  ██  ██      ██  ██          ██      ██  ██              ██  ██  ██  ██  
██  ██████  ██  ██  ██████████  ██████  ██  ██  ██  ██████  ██  ██  ██████████  ██████  ██  ██  ██████████████  ██  ██  
    ██      ██  ██                  ██  ██  ██  ██                  ██          ██  ██  ██  ██          ██          ██  
██████  ██  ██████  ██████████  ██████████  ██████  ██████  ██████████  ██████████  ██  ██  ██████████████  ██████████  
        ██  ██          ██              ██      ██  ██  ██  ██  ██  ██      ██  ██  ██  ██                  ██      ██  
██████  ██  ██████  ██  ██████  ██████████  ██  ██  ██  ██████  ██  ██  ██████  ██  ██  ██  ██████████  ██  ██  ██████  
        ██      ██  ██      ██  ██  ██      ██      ██                  ██  ██      ██  ██  ██      ██  ██  ██  ██  ██  
██████████  ██████  ██████████  ██  ██  ██████  ██████  ██████████  ██████  ██████  ██  ██  ██  ██████████████  ██  ██  
    ██          ██  ██              ██      ██          ██      ██  ██      ██                  ██  ██              ██  
██  ██  ██████████████████████  ██████████████  ██████  ██  ██████████  ██████  ██████  ██████████  ██  ██████████  ████
                ██              ██  ██      ██      ██              ██  ██      ██  ██      ██  ██      ██  ██  ██  ██  
██████  ██████  ██████████  ██  ██  ██  ██████  ██████████  ██████████  ██  ██████  ██████  ██  ██████  ██  ██  ████████
            ██          ██  ██              ██      ██                                  ██                          ██  
██████████████████████████████████████████████████  ██████  ██████████  ██████  ██████████████  ██████  ██  ██  ██  ████

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment