# Data structure and movement for tilt maze (part 2)

This is a design data structure and movement for a tilt maze. For example, this one.

My major idea is learned from abrarisme's smart idea of using two boolean matrix to represent wall. Please refer to this link for abrarisme's smart idea (Data structure and movement for tilt maze).

I need to (1) design the data structure to represent maze and (2) also implement movement function for 4 directions.

Since it is new code and I create this new post. Appreciate for code review advice on point (1) and point (2). Thanks!

An example of right matrix and related maze,

  __ __ __ __
|__   |__   |           [[true,  false, true,  false]
|  |  |     |            [false, false, true,  false],
|  |   __|  |      =>    [false, true,  false, false],
|     |   __|            [true,  false, true,  false],
|__|__|__ __|            [false, false, true,  false]]

right = [[True, False, True, False],
[False, False, True, False],
[False, True, False, False],
[True, False, True, False],
[False, False, True, False]]
top = [[False, False, False, False],
[False, True, False, True],
[True, True, True, True],
[True, True, False, True],
[True, True, True, False]]

def move_right (start_x, start_y):
while start_y < len(right)-1 and right[start_x][start_y] == True:
start_y+=1
return (start_x, start_y)

def move_left(start_x, start_y):
while start_y >= 1 and right[start_x][start_y-1] == True:
start_y -= 1
return (start_x, start_y)

def move_top(start_x, start_y):
while start_x > 0 and top[start_x][start_y] == True:
start_x-=1
return (start_x, start_y)
def move_down(start_x, start_y):
while start_x < len(top) - 1 and top[start_x+1][start_y] == True:
start_x+=1
return (start_x, start_y)

if __name__ == "__main__":
(x,y) = move_right(0,0)
print(x,y) # output, (0, 1)
(x,y) = move_down(x,y)
print (x,y) # output, (4, 1)
(x, y) = move_left(x, y)
print (x,y) # output, (4, 1)
(x, y) = move_top(x, y)
print (x,y) # output, (0, 1)


I've a couple of problems with your code.

1. Creating both a right and top list splits up the data. Instead you can merge flags into ints to reduce the amount of variables.

The way this can work is if we can 'move up' from that position we add 1. If we can 'move right' we add 2. This means if we can't move up or right, we will input 0. Or if we can do both we'll input 3.

You can then expand on this to add 'move down' and 'move left'. Where you'd add 4 if it's 'move down', and 8 if it's 'move left'. This is as we should be able to move up, down, left and right from a single square. Which would have the value $1 + 2 + 4 + 8 = 15$. Or if we couldn't 'move right' we'd have 13.

2. Your code is WET. As you write pretty much the same thing four times. Instead I'd use a builder function to remove this duplicate logic. This is as you can set the special changes in the builder function, and mutate the data in the returned function.

Take:

def _move(band, x_inc, y_inc):
def inner(x, y):
maze = self.maze
while maze[y][x] & band:
x += x_inc
y += y_inc
return x, y
return inner

move_right = _move(2, 1, 0)


I'd also like to point out that your variables are wrong. Your x is actually the index on the y-axis. This is as your board is in a y-major layout. But you should fix this as it's outright confusing.

3. You're relying on a global variable. This is bad. What if I make a global variable that overwrites yours? Or if I want to have two boards in memory at the same time?

Instead you should create a class. Nothing fancy, just an __init__ with top and right, or with my changes maze. And your four functions.

4. You don't adhere to PEP8. Sure, some people use a different style guide, but your code is not consistent. So you should follow PEP8, like a hobgoblin, to build consistency. This is as you:

• Have both spaces and no spaces around your -=.
• Have both a space and no space between your function name an it's parentheses.
• Don't have consistent tabbing in your list top.

Sure it's three places of inconsistency, but your code is WET. And definitely shouldn't have these inconsistencies if you copy and pasted the WET parts.

5. I'd like to also point out that your variable names start_x and start_y should instead be x and y. As you're changing them, and so by the end of the function, they are no longer the starting x or y.

Additionally, to simplify the creation of the maze, so you only need to set the flags for if you can move up or right. You can make a small private helper function. This just adds if you can move down or left from the cell, without having to check the surroundings. Just as I said in (1) above.

And so you can end with something like:

class Maze:
def __init__(self, maze, position=(0, 0)):
self.maze = self._normalize_maze(maze)
self.position = position

@staticmethod
def _normalize_maze(maze):
maze = maze[:]
height = len(maze)
width = len(maze[0])
for y in range(height):
for x in range(width):
if not (0 <= maze[y][x] <= 3):
raise ValueError('Cells in array must be [0,3].')
if y > 0:
maze[y-1][x] |= (maze[y][x] & 1) << 2
if x > 0:
maze[y][x] |= (maze[y][x-1] & 2) << 2
return maze

def _move(band, x_inc, y_inc):
def inner(self):
maze = self.maze
x, y = self.position
while maze[y][x] & band:
x += x_inc
y += y_inc
self.position = x, y
return inner

move_right = _move(2, 1, 0)
move_left  = _move(8, -1, 0)
move_up    = _move(1, 0, -1)
move_down  = _move(4, 0, 1)

if __name__ == "__main__":
maze = Maze([
[2, 0, 2, 0],
[0, 1, 2, 1],
[1, 3, 1, 1],
[3, 1, 2, 1],
[1, 1, 3, 0],
])
print(maze.position) # output, (0, 0)
maze.move_right()
print(maze.position) # output, (1, 0)
maze.move_down()
print(maze.position) # output, (1, 4)
maze.move_left()
print(maze.position) # output, (1, 4)
maze.move_up()
print(maze.position) # output, (1, 0)

• Hi Peilonrayz, love all the comments and your elegant code, and vote up. One quick question, I see you are using one function to assign to some other variable -- move_right = _move(2, 1, 0), in this case move_right is a member variable of class Maze? And move_right looks like a member variable of classic function pointer? What is the technique called in Python? – Lin Ma Nov 11 '16 at 0:21
• BTW Peilonrayz, another question, in your initial value for maze in the constructor, you have value 0, 1, 2 and 3, could you clarify what they mean? Why not initialize the matrix directly to 1, 2, 4 ,8 (their combination)? – Lin Ma Nov 11 '16 at 4:24
• @LinMa _move is a Closure. The only difference mine has to a normal one is that it's defined on a class. move_right is just a function. I describe the 0, 1, 2, and 3 in my second paragraph to my first point "we can 'move up' from that position we add 1. If we can 'move right' we add 2. This means if we can't move up or right, we will input 0. Or if we can do both we'll input 3." I don't use [0,15] as you'll be duplicating input. – Peilonrayz Nov 11 '16 at 9:13
• Thanks Peilonrayz for all the help, mark your reply as answer. Wondering why not initialize by [1,2,4,8] scheme, other than [0,1,2,3] -- latter require another level of transform? – Lin Ma Nov 14 '16 at 1:45
• @linma yes you need more code, _normalize_maze, but means you don't need to duplicate input, say I can move only right from one square, I'd have to enter 2 in the left square and 8 in the right one. Instead we can enter just 2,and the program do the rest for us bug free. Obviously this removes the ability to have levels, that you can drop down into, but not up out of, in the maze. – Peilonrayz Nov 14 '16 at 1:51