16

I seem to have a problem with my maze generating program made in Python. I'm trying to randomly create a path that branches out at select points, with the points getting stored as it goes along. When the maze gets to a dead end, it will sort back through the visited points by testing the top value than popping that and going to the next one, until it gets to a spot where it isn't a dead end. However, when I try to append items to the list I'm using to save the spaces I've been to, something strange happens, I've never seen it before actually. Here's the code, and the best way to see it is to run it a through times until it goes all the way through. I haven't really found a way to counter the dead end problem, so if anyone could help me with that also, that would be great.

import random

width = 8

def check(x,y):
    """Figures out the directions that Gen can move while"""
    if x-1 == -1:
        maze[x][y][3] = 0 

    if x+1 == 8:
        maze[x][y][1] = 0

    if y+1 == 8:
        maze[x][y][2] = 0

    if y-1 == -1:
        maze[x][y][0] = 0

    if x + 1 in range(0,8) and visited[x+1][y] == False:
        maze[x][y][1] = 2

    if x - 1 in range(0,8) and visited[x-1][y] == False:
        maze[x][y][3] = 2

    if y + 1 in range(0,8) and visited[x][y+1] == False:
        maze[x][y][2] = 2

    if y - 1 in range(0,8) and visited[x][y-1] == False:
        maze[x][y][0] = 2



def Gen(x,y):
    visited[x][y] = True
    past.append(current)
    dirs = []
    check(x,y)
    print current

    if maze[x][y][0] == 2:
        dirs.append(0)
    if maze[x][y][1] == 2:
        dirs.append(1)
    if maze[x][y][2] == 2:
        dirs.append(2)
    if maze[x][y][3] == 2:
        dirs.append(3)

    pos = random.choice(dirs)

    print dirs

    maze[x][y][pos] = 1  

    if pos == 0:
        current[1] -= 1
    if pos == 1:
        current[0] += 1
    if pos == 2:
        current[1] += 1
    if pos == 3:
        current[0] -= 1

    if maze[x][y][0] == 4:
        maze[x][y][0] = 1

    if maze[x][y][1] == 4:
        maze[x][y][1] = 1

    if maze[x][y][2] == 4:
        maze[x][y][2] = 1

    if maze[x][y][3] == 4:
        maze[x][y][3] = 1

    print maze[x][y]
    print past, '\n'


#Build the initial values for the maze to be replaced later
maze = []
current = [0,0]
visited = []
past = []

#Generate empty 2d list with a value for each of the xy coordinates
for i in range(0,width):
    maze.append([])
    for q in range(0, width):
        maze[i].append([])
        for n in range(0, 4):
            maze[i][q].append(4)

#Makes a list of falses for all the non visited places
for x in range(0, width):
    visited.append([])
    for y in range(0, width):
        visited[x].append(False)

#Generates the walls
#for q in range(0, width):
#    for i in range(0, width):
#        check(q, i)

current = [0,0]

while current != [7,7]:
    Gen(current[0], current[1])
print maze

As you can see, it starts at 0,0 and then figures out the possible paths to take. It randomly selects from those and sets the value for that side of the room in 0,0 to 1, which means a passage. 2 means wall and 0 means out of bounds. 4 is just a placeholder as all values should be filled by the time the maze is completely generated.

If anyone could help me, that would be great and very appreciated. Thanks in advance.

Matt Habel
  • 1,493
  • 2
  • 14
  • 35
  • What is the strange behavior you see when you use list.append()? What is the expected result? What is the actual result? – dappawit Mar 12 '11 at 05:39
  • Every element of the list turns to the newly appended element. For example, after 4 squares of the maze, the 4 elements in past are changed to whatever the appended element is. The thing I'm expecting is that it will be a list of the path that the generator took, for example, [[0,0][0,1][1,1][2,1]] etc. – Matt Habel Mar 12 '11 at 05:43
  • Ok, so the current (erroneous) behavior is, for example, if you had `[[0,0],[0,0],[0,0]]` and appended `[1,2]`, the list would become: `[[1,2],[1,2],[1,2],[1,2]]`? – dappawit Mar 12 '11 at 05:46

2 Answers2

24

I believe the current list is simply copied multiple times into past. So you have multiple copies of the same list.

To fix: in the line past.append(current) (two lines below def Gen(x,y):), change it to past.append(current[:]).

The notation list[:] creates a copy of the list. Technically, you are creating a slice of the whole list.

By the way, a better solution would be to not use a global current variable :)

dappawit
  • 12,182
  • 2
  • 32
  • 26
  • 2
    That worked, but can you tell me why? I don't know why the simple append doesn't work. – Matt Habel Mar 12 '11 at 05:57
  • 9
    Okay, you have a two element list called `current`. When you append that to `past`, you insert a reference to it. So, now `current` and `past[-1]` both refer to the *same* object. Then, you append it again, and all of: `past[-2]`, `past[-1]`, and `current` refer to the *same* object. Therefore, when you edit `current`, the items in the list also change. Because all refer to the *same* object... To put it another way, using `past.append(current)` does *not* make a copy of `current`. – dappawit Mar 12 '11 at 06:01
  • or use Python list's `copy()` method to get a **deep copy**: `past.append(current.copy())` – Shayan Amani Nov 29 '20 at 15:08
0

Yeah this is correct while List Comprehension in Python you need to append by strip other wise it will replace multiple times

user3705815
  • 11