0

I have a matrix:

maze = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0]]

1 - obstacles

0 - regular cells

I want to implement an algorithm for finding the shortest path between the two selected cells (If you can not go diagonally). I tried the A * algorithm but it did not give the correct result:

def astar(maze, start, end):

    start_node = Node(None, start)
    start_node.g = start_node.h = start_node.f = 0
    end_node = Node(None, end)
    end_node.g = end_node.h = end_node.f = 0

    open_list = []
    closed_list = []

    open_list.append(start_node)

    while len(open_list) > 0:
        current_node = open_list[0]
        current_index = 0
        for index, item in enumerate(open_list):
            if item.f < current_node.f:
                current_node = item
                current_index = index

        open_list.pop(current_index)
        closed_list.append(current_node)

        if current_node == end_node:
            path = []
            current = current_node
            while current is not None:
                path.append(current.position)
                current = current.parent
            return path[::-1] # Return reversed path

        children = []
        for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, 1), (1, -1)]: 

            node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])

            if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or node_position[1] > (len(maze[len(maze)-1]) -1) or node_position[1] < 0:
                continue

            if maze[node_position[0]][node_position[1]] != 0:
                continue

            new_node = Node(current_node, node_position)
            children.append(new_node)
        for child in children:

            for closed_child in closed_list:
                if child == closed_child:
                    continue

            child.g = current_node.g + 1
            child.h = ((child.position[0] - end_node.position[0]) ** 2) + ((child.position[1] - end_node.position[1]) ** 2)
            child.f = child.g + child.h
            for open_node in open_list:
                if child == open_node and child.g > open_node.g:
                    continue

            open_list.append(child)

Please tell me how it can be implemented in the language Python so that it works correctly.

Tim Gates
  • 41
  • 8
  • 1
    I am not sure if A * should work and you are implementing it wrong, but this is a clear case of BFS, not A * – juvian Oct 16 '18 at 15:34
  • @juvian Thanks, Could you show how this works if the record is in the form of a matrix? – Tim Gates Oct 16 '18 at 15:50
  • you can check [this similar post](https://stackoverflow.com/questions/47896461/get-shortest-path-to-a-cell-in-a-2d-array-python) – juvian Oct 16 '18 at 15:56
  • Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation, as suggested when you created this account. [Minimal, complete, verifiable example](http://stackoverflow.com/help/mcve) applies here. We cannot effectively help you until you post your MCVE code and accurately describe the problem. We should be able to paste your posted code into a text file and reproduce the problem you described. StackOverflow is not a coding or tutorial resource. "Does not give the correct result" is not a problem specification. – Prune Oct 16 '18 at 16:12
  • Briefly, you haven't told us *specifically* how it doesn't work -- those first debugging steps, and reporting the results accurately, are your responsibility. Also, there are many examples on line of both maze solvers and A* implementations, so you should *not* be asking us for an A* example: again, that research is your responsibility before posting. Go through those steps, update your posting, and we'll be happy to help with your problem -- but we're not likely to step through your program to make the initial diagnosis. – Prune Oct 16 '18 at 16:15
  • @juvian help me please how to do it for this start and end? start = (0,0), end = (6,7) ? – Tim Gates Oct 16 '18 at 17:00
  • @ПавелЯкимов link I gave already has start, as for end you just need to change if grid[y][x] == goal: to if y == 6 and x == 7 – juvian Oct 16 '18 at 17:11
  • @ПавелЯкимов no, if y == 6 and x == 7: – juvian Oct 16 '18 at 17:22

2 Answers2

3

Here's a BFS implementation for your problem: https://ideone.com/tuBu3G We initiate our queue with the starting point of interest and stop once we've visited our ending point. At every step of our iteration, we aim to explore new unexplored state and set the distance of this new point as 1 + the distance of the point from where it was explored.

from collections import deque


graph = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 1, 0, 0, 0, 0, 0]]

# To move left, right, up and down
delta_x = [-1, 1, 0, 0]
delta_y = [0, 0, 1, -1]

def valid(x, y):
    if x < 0 or x >= len(graph) or y < 0 or y >= len(graph[x]):
        return False
    return (graph[x][y] != 1)

def solve(start, end):
    Q = deque([start])
    dist = {start: 0}
    while len(Q):
        curPoint = Q.popleft()
        curDist = dist[curPoint]
        if curPoint == end:
            return curDist
        for dx, dy in zip(delta_x, delta_y):
            nextPoint = (curPoint[0] + dx, curPoint[1] + dy)
            if not valid(nextPoint[0], nextPoint[1]) or nextPoint in dist.keys():
                continue
            dist[nextPoint] = curDist + 1
            Q.append(nextPoint)

print(solve((0,0), (6,7)))

Prints: # 13

Nilesh
  • 1,388
  • 6
  • 17
  • This returns the length of the shortest path - how to return the shortest path itself? – K-- Jun 20 '23 at 13:47
0

Here is an example of how to implement BFS in python 3:

import collections


    def breadth_first_search(graph, root): 
        visited, queue = set(), collections.deque([root])
        while queue: 
        vertex = queue.popleft()
        for neighbour in graph[vertex]: 
            if neighbour not in visited: 
                visited.add(neighbour) 
                queue.append(neighbour) 


if __name__ == '__main__':
    graph = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0]]
    breadth_first_search(graph, 0)

I hope this was able to help, Please let me know how it goes!

B. Cratty
  • 1,725
  • 1
  • 17
  • 32