Find path from source to destination in tilt maze

Question

For a tilt maze general reference, you can refer to this example. The previous related code review discussion could be referred here.

The problem I want to resolve is to find all possible path (so that in the future I can find minimal path) from source to destination.

My major idea is:

1. Represent the maze by flag which direction I can move from a specific cell
2. Using recursion, move left/right, then move top/down, then left/right, then top/down, until the destination is reached

I'm not sure if my implementation is elegant, move left/right, then move top/down, then left/right, then top/down, until reach to destination, seems a bit hard-coded way. I'm wondering if there are any functional/logical bugs in my code -- even if I tested, but might be potential issues which I do not find yet.

  __ __ __ __ 
 |__   |__   |          
 |  |  |     |           
 |  |   __|  |      
 |     |   __|            
 |__|__ __ __|         

class MoveEnum:
    CAN_MOVE_LEFT = 1
    CAN_MOVE_RIGHT = 2
    CAN_MOVE_UP = 4
    CAN_MOVE_DOWN = 8

class Maze:
    def __init__(self, matrix):
        self.matrix = matrix
        self.results = []
    def move_left(self, x1, y1):
        while self.matrix[y1][x1] & MoveEnum.CAN_MOVE_LEFT:
            x1 -= 1
        return (x1, y1)
    def move_right(self, x1, y1):
        while self.matrix[y1][x1] & MoveEnum.CAN_MOVE_RIGHT:
            x1 += 1
        return (x1, y1)
    def move_up(self, x1, y1):
        while self.matrix[y1][x1] & MoveEnum.CAN_MOVE_UP:
            y1 -= 1
        return (x1, y1)
    def move_down(self, x1, y1):
        while self.matrix[y1][x1] & MoveEnum.CAN_MOVE_DOWN:
            print y1
            y1 += 1
        return (x1, y1)
    # find shortest move from x1 y1, to x2, y2
    def move_path(self, x1, y1, x2, y2, is_left_right, path):
        if x1 == x2 and y1 == y2:
            self.results.append(path[:])
        elif is_left_right:
            (x, y) = self.move_right(x1,y1)
            if x != x1:
                path.append((x, y))
                self.move_path(x, y, x2, y2, not is_left_right, path)
                path.pop(-1)
            (x, y) = self.move_left(x1,y1)
            if x != x1:
                path.append((x, y))
                self.move_path(x, y, x2, y2, not is_left_right, path)
                path.pop(-1)
        else:
            (x, y) = self.move_up(x1, y1)
            if y != y1:
                path.append((x, y))
                self.move_path(x, y, x2, y2, not is_left_right, path)
                path.pop(-1)
            (x, y) = self.move_down(x1, y1)
            if y != y1:
                path.append((x, y))
                self.move_path(x, y, x2, y2, not is_left_right, path)
                path.pop(-1)


if __name__ == "__main__":
    maze_matrix = [[MoveEnum.CAN_MOVE_RIGHT, MoveEnum.CAN_MOVE_LEFT|MoveEnum.CAN_MOVE_DOWN, MoveEnum.CAN_MOVE_RIGHT, MoveEnum.CAN_MOVE_LEFT|MoveEnum.CAN_MOVE_DOWN],
                   [MoveEnum.CAN_MOVE_DOWN, MoveEnum.CAN_MOVE_UP|MoveEnum.CAN_MOVE_DOWN, MoveEnum.CAN_MOVE_RIGHT|MoveEnum.CAN_MOVE_DOWN, MoveEnum.CAN_MOVE_LEFT|MoveEnum.CAN_MOVE_UP|MoveEnum.CAN_MOVE_DOWN],
                   [MoveEnum.CAN_MOVE_UP | MoveEnum.CAN_MOVE_DOWN, MoveEnum.CAN_MOVE_UP|MoveEnum.CAN_MOVE_DOWN|MoveEnum.CAN_MOVE_RIGHT, MoveEnum.CAN_MOVE_UP|MoveEnum.CAN_MOVE_LEFT, MoveEnum.CAN_MOVE_UP|MoveEnum.CAN_MOVE_DOWN],
                    [MoveEnum.CAN_MOVE_UP | MoveEnum.CAN_MOVE_DOWN | MoveEnum.CAN_MOVE_RIGHT, MoveEnum.CAN_MOVE_UP | MoveEnum.CAN_MOVE_DOWN | MoveEnum.CAN_MOVE_LEFT, MoveEnum.CAN_MOVE_DOWN|MoveEnum.CAN_MOVE_RIGHT, MoveEnum.CAN_MOVE_UP|MoveEnum.CAN_MOVE_LEFT],
                   [MoveEnum.CAN_MOVE_UP, MoveEnum.CAN_MOVE_UP|MoveEnum.CAN_MOVE_RIGHT, MoveEnum.CAN_MOVE_UP | MoveEnum.CAN_MOVE_RIGHT, MoveEnum.CAN_MOVE_LEFT]]
    maze = Maze(maze_matrix)
    maze.move_path(0,0,3,4,True,[])
    maze.move_path(0, 0, 3, 4, False, [])
    print maze.results

Answer 1

I'd still suggest using a closure, which I addressed in my last answer:

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)

The name of MoveEnum could be changed to Moves, as the Enum part is useless when using it. I'd also change CAN_MOVE_* to just *, this is as it doesn't add any value. And so I'd much prefer it to be Moves.UP.

move_path is dodgy. You shouldn't have to pass a list to it, and it should really return results. Instead I would create another closure the outer function to create path, return results, and call the inner function. The inner function to perform the recursion as you currently have it.