graph.txt

cost_list=#:10,~:5, :0
###############
#        #    #
# ###### # #  #
#      #   #  #
#   s  #####  #
#      #      #
#      # ######
#~~~~~~#      #
#             #
#             #
#             #
#             #
#             #
#       e     #
###############

pathfinder.py

import sys
import queue

class Graph:
     # static
    def read_from(file_name):
        graph = Graph()
        with open(file_name, 'r') as f:
            for line in f:
                if line.startswith('cost_list='):
                    tokens = line[10:].rstrip('\n').split(',')
                    for token in tokens:
                        name, cost = token.split(':')
                        graph.cost_list[name] = int(cost)
                else:
                    graph.data.append(list(line.rstrip('\n')))
        return graph

    def __init__(self):
        self.data = []
        self.cost_list = {}

    def write_to(self, file_name):
        with open(file_name, 'w') as f:
            if len(self.cost_list) > 0:
                f.write('cost_list=')
                f.write(','.join(list(map(lambda k: str(k)+':'+str(costs[k]), costs.keys()))))
                f.write('\n')
            for y in range(self.height()):
                for x in range(self.width()):
                    f.write(self.data[y][x])
                f.write('\n')

    def neighbors(self, node):
        if not node:
            return []

        y, x = node
        w = self.width()
        h = self.height()

        nodes = []

        if y - 1 > 0:
            nodes.append((y-1, x))
        if x - 1 > 0:
            nodes.append((y, x-1))
        if y + 1 < h:
            nodes.append((y+1, x))
        if x + 1 < w:
            nodes.append((y, x+1))
        return nodes

    def cost(self, node):
        y, x = node

        if self.data[y][x] in self.cost_list:
            return self.cost_list[self.data[y][x]]
        else:
            return 0

    def find_unique_node(self, value):
        for y in range(self.height()):
            for x in range(self.width()):
                if self.data[y][x] == value:
                    return y, x
        return []

    def print(self):
        for y in range(self.height()):
            for x in range(self.width()):
                print(self.data[y][x], end='')
            print()

    def __getitem__(self, index):
        return self.data[index]

    def width(self):
        return len(self.data[0])

    def height(self):
        return len(self.data)

class PathFinder:
    def __init__(self, graph):
        self.graph = graph

    def find_path(self, start, end):
        frontier = queue.Queue()
        frontier.put(start)
        visited = {}
        visited[start] = None
        node_cost = {}
        node_cost[start] = 0

        while not frontier.empty():
            current = frontier.get()

            if current == end:
                break

            for next in self.graph.neighbors(current):
                cost = node_cost[current] + self.graph.cost(next)
                if next not in node_cost or cost < node_cost[next]:
                    node_cost[next] = cost
                    frontier.put(next, cost)
                    visited[next] = current

        node = visited[end]

        if not node:
            return []

        path = [node]
        while node != start:
            node = visited[node]
            path.append(node)
        path.reverse()
        return path

def bordered_graph(width, height):
    graph = Graph()
    graph.data = [[' '] * width for i in range(height)]

    for x in range(width):
        graph.data[0][x] = graph.data[height-1][x] = '#'

    for y in range(height):
        graph.data[y][0] = graph.data[y][width-1] = '#'

    return graph

if __name__ == '__main__':
    graph = Graph.read_from('graph.txt')

    start = graph.find_unique_node('s')
    end = graph.find_unique_node('e')

    if not start:
        print('could not detect starting node')
        sys.exit(1)
    if not end:
        print('could not detect ending node')
        sys.exit(1)

    pathfinder = PathFinder(graph)
    path = pathfinder.find_path(start, end)

    for node in path:
        y, x = node
        if graph.data[y][x] == ' ':
            graph.data[y][x] = '+'

    graph.print()
    print(path)