Data structure and movement for tilt maze

Question

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)

Answer 1

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.