A-star (A*) search algorithm on labyrinth matrix in python

Question

I have a labyrinth matrix for a maze problem.

Labyrinth =
[[0, 0, 0, 0, 0, 0, 1, 0],
[0, 1, 0, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 0, 1, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 1, 1, 3, 0],
[0, 0, 1, 1, 1, 0, 0, 0],
[0, 1, 2, 0, 1, 1, 1, 0],
[0, 1, 0, 0, 0, 0, 0, 0]]

Here,

• 0 represents a blocked cell that is a wall

• 1 represents an empty cell

• 2 and 3 represents starting and ending points respectively.

I need a function which can return the path from point 2 to 3 after performing an A* Search Algorithm using Manhattan distance as distance estimate and length of the current path as path-cost.

Any Pointers? or tip/clue how I should operate on this one?

Update: I want to return path from begin to end by marking the path with some other character like X. For reference, this:

Labyrinth =
[[0, 0, 0, 0, 0, 0, 1, 0],
[0, 1, 0, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 0, 1, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, X, X, 3, 0],
[0, 0, X, X, X, 0, 0, 0],
[0, 1, 2, 0, 1, 1, 1, 0],
[0, 1, 0, 0, 0, 0, 0, 0]]

Answer 1

Classical search algorithm work using a set of states called the fringe and a set of visited states:

• the fringe is all the set that are yet to eplore hoping to find the goal state
• the visited set is all the states that have already been visited to avoid visiting them again

The idea of A* is to explore the state in the fringe that has a minimal value of cost (defined as the sum of the heuristic cost and the progression cost (computed by all the state you had to pass by before)). You can find generic implementation of this algorithm on the wikipedia page for A* search algorithm. In your case a state may consist in :

1. the i, j position in the grid
2. the previous state (assuming None for the first state)
3. the total cost of this state (heuristic + path cost).

To explore a set you only need to check the direct neighbors of the cell (including only the one where the value is one). It is worth noting that in the visited set you should only include the position (i,j) and the cost (as you may re-enter this state if you found a shorter path, even if it is unlikely in your problem).

Here is an example that works for your case (but may be generalized easily):

def astar(lab):
    # first, let's look for the beginning position, there is better but it works
    (i_s, j_s) = [[(i, j) for j, cell in enumerate(row) if cell == 2] for i, row in enumerate(lab) if 2 in row][0][0]
    # and take the goal position (used in the heuristic)
    (i_e, j_e) = [[(i, j) for j, cell in enumerate(row) if cell == 3] for i, row in enumerate(lab) if 3 in row][0][0]

    width = len(lab[0])
    height = len(lab)

    heuristic = lambda i, j: abs(i_e - i) + abs(j_e - j)
    comp = lambda state: state[2] + state[3] # get the total cost

    # small variation for easier code, state is (coord_tuple, previous, path_cost, heuristic_cost)
    fringe = [((i_s, j_s), list(), 0, heuristic(i_s, j_s))]
    visited = {} # empty set

    # maybe limit to prevent too long search
    while True:

        # get first state (least cost)
        state = fringe.pop(0)

        # goal check
        (i, j) = state[0]
        if lab[i][j] == 3:
            path = [state[0]] + state[1]
            path.reverse()
            return path

        # set the cost (path is enough since the heuristic won't change)
        visited[(i, j)] = state[2] 

        # explore neighbor
        neighbor = list()
        if i > 0 and lab[i-1][j] > 0: #top
            neighbor.append((i-1, j))
        if i < height and lab[i+1][j] > 0:
            neighbor.append((i+1, j))
        if j > 0 and lab[i][j-1] > 0:
            neighbor.append((i, j-1))
        if j < width and lab[i][j+1] > 0:
            neighbor.append((i, j+1))

        for n in neighbor:
            next_cost = state[2] + 1
            if n in visited and visited[n] >= next_cost:
                continue
            fringe.append((n, [state[0]] + state[1], next_cost, heuristic(n[0], n[1])))

        # resort the list (SHOULD use a priority queue here to avoid re-sorting all the time)
        fringe.sort(key=comp)