6
\$\begingroup\$

I have implemented Astar algorithm for a problem on an online judge relating to maze given start and end positions along with a grid representing the maze. I output the length of the path along with the path itself. The following is the implementation in Python using the Euclidean distance:

import heapq, math, sys

infinity = float('inf')

class AStar():

    def __init__(self, start, grid, height, width):
        self.start, self.grid, self.height, self.width = start, grid, height, width

    class Node():
        def __init__(self, position, fscore=infinity, gscore=infinity, parent = None):
            self.fscore, self.gscore, self.position, self.parent = fscore, gscore, position, parent
            
        def __lt__(self, comparator):
            return self.fscore < comparator.fscore

    def heuristic(self, end, distance = "Euclidean"):
        (x1, y1), (x2, y2) = self.start, end
        if (distance == "Manhattan"):
            return abs(x1 - x2) + abs(y1 - y2)
        return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)

    def nodeNeighbours(self, pos):
        (x, y) = pos
        return [(dx, dy) for (dx, dy) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)] if 0 <= dx < self.width and 0 <= dy < self.height and self.grid[dy][dx] == 0]

    def getPath(self, endPoint):
        current, path = endPoint, []
        while current.position != self.start:
            path.append(current.position)
            current = current.parent
        path.append(self.start)
        return list(reversed(path))

    def computePath(self, end):
        openList, closedList, nodeDict = [], [], {}
        currentNode = AStar.Node(self.start, fscore=self.heuristic(end), gscore = 0)
        heapq.heappush(openList, currentNode)
        while openList:
            currentNode = heapq.heappop(openList)
            if currentNode.position == end:
                return self.getPath(currentNode)
            else:
                closedList.append(currentNode)
                neighbours = []
                for toCheck in self.nodeNeighbours(currentNode.position):
                    if toCheck not in nodeDict.keys():
                        nodeDict[toCheck] = AStar.Node(toCheck)
                        neighbours.append(nodeDict[toCheck])
                
                for neighbour in neighbours:
                    newGscore = currentNode.gscore + 1
                    if neighbour in openList and newGscore < neighbour.gscore:
                        openList.remove(neighbour)
                    if newGscore < neighbour.gscore and neighbour in closedList:
                        closedList.remove(neighbour)
                    if neighbour not in openList and neighbour not in closedList:
                        neighbour.gscore = newGscore
                        neighbour.fscore = neighbour.gscore + self.heuristic(neighbour.position)
                        neighbour.parent = currentNode
                        heapq.heappush(openList, neighbour)
                    heapq.heapify(openList)
        return None
        
if __name__ == '__main__':
    
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
    
    matrix = [[int(num) for num in line.split()] for line in sys.stdin]
    size = matrix.pop(0)
    coordinates = matrix.pop(0)
    n, m = size[0], size[1]
    x1, y1, y2, x2 = coordinates[0], coordinates[1], coordinates[2], coordinates[3]
    path = AStar((x1-1, y1-1), matrix, n, m).computePath((y2-1, x2-1))
    print(len(path))
    for pos in path:
        print(pos[0] + 1, pos[1] + 1)
\$\endgroup\$
  • \$\begingroup\$ I do not have anything else to say yet, but your Manhattan distance code seems to be wrong (it currently is abs((x1 - x2) + abs(y1 - y2)) but should probably be abs(x1 - x2) + abs(y1 - y2)) \$\endgroup\$ – the default. Sep 2 at 13:40
5
\$\begingroup\$
self.start, self.grid, self.height, self.width = start, grid, height, width

I would not put these all on the same line like that. I think it would be much easier to read spread over multiple lines:

self.start = start
self.grid = grid
self.height = height
self.width = width

I would probably have the Node class as toplevel instead of nested. I don't think you're gaining much by having it inside AStar. You could name it _Node to make it "module-private" so that attempting to import it to another file will potentially raise warnings.

In Node's __lt__ implementation, I wouldn't call the second parameter comparator. A comparator is something that compares, whereas in this case, that's just another node. other_node or something would be more appropriate.


In heuristic, I'd personally make use of an else there:

if (distance == "Manhattan"):
    return abs((x1 - x2) + abs(y1 - y2))
else:
    return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)

It makes it clearer that only one of the lines will be executed. Personally, I only neglect the else in a case like that if the if was an "early exit" precondition check, and I want to avoid nesting the entire rest of the function inside a block. That's not a problem here though.


nodeNeighbors (which should be node_neighbors) would be cleaner broken over several lines:

def nodeNeighbours(self, pos):
    (x, y) = pos
    return [(dx, dy)
            for (dx, dy) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
            if 0 <= dx < self.width and 0 <= dy < self.height and self.grid[dy][dx] == 0]

I think that makes it a lot easier to see what's going on in it.


Again, in many places you're assigning two or more variables on one line:

(x1, y1), (x2, y2) = self.start, end
current, path = endPoint, []
openList, closedList, nodeDict = [], [], {}
x1, y1, y2, x2 = coordinates[0], coordinates[1], coordinates[2], coordinates[3]

I would break those up. Especially once you get to 3+ on a line, for the reader to see what variable matches up with what value, they'll need to count from the left instead of just checking what's on each side of a =.


In computePath, it seems like closedList should be a set. It doesn't appear as though order matters with it, and neighbour in closedList will be faster with a set than it will with a list. It looks though like openList is required to be a list though due to it being passed to heapify.


I don't think I'd reassign stdin and stdout. The reassignment of stdin seems completely unnecessary, and changing stdout will make it harder to debug later using print statements. You don't necessarily want all printed text to be sent to the file.

If need-be, you can specify what file you want printed to when printing:

with open('output.txt', 'w') as out_f:
    print("To file!", file=out_f)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks! Do you think using openList a priority_queue instead will make the code more efficient than using heapq? \$\endgroup\$ – Jalanji Moh Sep 2 at 16:39
  • 1
    \$\begingroup\$ @JalanjiMoh Honestly, it's been a long time since I've written a A* implementation, so it's difficult for me to make algorithmic suggestions here. Even if you did switch though, you likely still wouldn't be able to have open_list as a set for the same reason. Standard Python sets are unordered, so any place you need to maintain order, plain sets won't be appropriate. \$\endgroup\$ – Carcigenicate Sep 2 at 16:43
  • \$\begingroup\$ Right. Thanks!! \$\endgroup\$ – Jalanji Moh Sep 2 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.