Python: Astar algorithm implementation

Question

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)

Answer 1

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)