# Data structure and movement for tilt maze

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

My major idea is to divide into Ball, Maze, HorizontalWall and VerticalWall classes. Ball is the core class which operates on Maze, HorizontalWall and VerticalWall.

I feel my code is a bit inefficient since each time, I need to enumerate all vertical or horizontal walls, for move right/left/up/down. I'm not sure if there's a more efficient way to represent the data structure and movement implementation.

class VerticalWall: # something like |
def __init__(self, x, y1, y2):
self.x=x
self.y_start = y1
self.y_end = y2

class HorizontalWall: # soemthing like --
def __init__(self, x1, x2, y):
self.x_start = x1
self.x_end = x2
self.y = y

class Ball:
def __init__(self, top, left, maze):
self.top = top
self.left = left
self.maze = maze
def moveRight(self):
x_location=[]
y_location=[]
for i in maze.vertical_wall:
x_location.append(i.x)
y_location.append(i.y_start)
while True:
for i,x in enumerate(x_location):
if self.left + 1 == x and y_location[i] == self.top: # met with a vertical wall
return
if self.left+1==self.maze.width: # border
return
else:
self.left += 1
def moveLeft(self):
x_location=[]
y_location=[]
for i in maze.vertical_wall:
x_location.append(i.x)
y_location.append(i.y_start)
while True:
for i,x in enumerate(x_location):
if self.left == x and y_location[i] == self.top: # met with a vertical wall
return
if self.left == 0: # border
return
else:
self.left -= 1
def moveUp(self):
x_location=[]
y_location=[]
for i in maze.horizontal_wall:
x_location.append(i.x_start)
y_location.append(i.y)
while True:
for i,x in enumerate(x_location):
if self.left == x and y_location[i] == self.top: # met with a vertical wall
return
if self.top == 0: # border
return
else:
self.top -= 1
def moveDown(self):
x_location=[]
y_location=[]
for i in maze.horizontal_wall:
x_location.append(i.x_start)
y_location.append(i.y)
while True:
for i,x in enumerate(x_location):
if self.left == x and y_location[i] == self.top+1: # met with a vertical wall
return
if self.top + 1 == self.maze.height: # border
return
else:
self.top += 1

class Maze:
def __init__(self, height, width, target_x, target_y):
self.height = height
self.width = width
self.target_x=target_x
self.target_y=target_y
self.horizontal_wall=[]
self.vertical_wall=[]

if __name__ == "__main__":
# https://www.mathsisfun.com/games/tilt-maze.html
maze = Maze(5,5,4,4)
maze.horizontal_wall.append(HorizontalWall(1, 2, 1))
maze.horizontal_wall.append(HorizontalWall(4, 5, 2))
maze.horizontal_wall.append(HorizontalWall(2, 3, 3))
maze.horizontal_wall.append(HorizontalWall(1, 2, 4))
maze.horizontal_wall.append(HorizontalWall(4, 5, 4))

maze.vertical_wall.append(VerticalWall(3, 0, 1))
maze.vertical_wall.append(VerticalWall(1, 2, 3))
maze.vertical_wall.append(VerticalWall(3, 4, 5))

ball = Ball(0,0,maze)
print ('current location ', ball.top, ball.left)
ball.moveRight()
print ('current location ', ball.top, ball.left)
ball.moveDown()
print ('current location ', ball.top, ball.left)
ball.moveLeft()
print ('current location ', ball.top, ball.left)
ball.moveUp()
print ('current location ', ball.top, ball.left)


I think that for this situation you can just represent your maze as a matrix of boolean values. The boolean values can be used to indicate whether there is a wall for that position.

Here's an example (with true indicating that the right side of the cell doesn't have a wall):

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


The given example matrix includes values for vertical walls. I only need to include information about the right direction because I can look at the cell at (x - 1) to get wall information for the left side of the cell.

You'll need a separate matrix for horizontal walls (for a total of two matrices). The top, bottom, and left edges implicitly have a wall.

Using this representation, you should be able to calculate your end point in a time proportional to the distance between an end and start point. The ball only needs to know its (x, y) position.

Your walls likely don't have to be their own class for this problem. If you ever want to extend your program such that landing on specific types of walls (say a fire wall) results in different behavior, then objects may be helpful.

Even in that case, I would say that using an enum may be sufficient.

• Thanks abrarisme, sounds a smart idea. Could you elaborate a bit more the logical meaning for true and false in your matrix example? For example, you represent element as false, but element as true, I think for both the two elements, there are either vertical or horizontal walls around? Why they have different boolean value? – Lin Ma Nov 7 '16 at 8:07
• Wondering if you have only one true and false matrix? Or 4 such matrix for 4 directions indiviaully? – Lin Ma Nov 7 '16 at 8:08
• I edited my answer to clarify. You'll need two matrices. And, you only need to keep track of one side for each of them. – abrarisme Nov 7 '16 at 9:52
• Your idea is very smart, mark your reply as answer. – Lin Ma Nov 8 '16 at 7:35
• BTW, abrarisme, I implemented tour idea and created a new post, your advice is highly appreciated. Thanks. codereview.stackexchange.com/questions/146469/… – Lin Ma Nov 8 '16 at 7:57