grid.py

import enum
from typing import List, Optional, Tuple

from termcolor import colored

class CellType(enum.Enum):
    EMPTY = ' '
    WALL = colored('#', color='white', attrs=['bold'])
    MONSTER = colored('M', color='red')
    MONSTER_FOG = colored('+', color='green')
    MONSTER_FOG_NEW = colored('+', color='magenta')
    HERO = colored('A', color='yellow')
    HERO_PATH = colored('o', color='yellow')


class Direction(enum.Enum):
    NONE = colored('·', color='yellow')
    UP = colored('↑', color='yellow')
    DOWN = colored('↓', color='yellow')
    LEFT = colored('←', color='yellow')
    RIGHT = colored('→', color='yellow')


offsets = {
    (0, 1): Direction.DOWN,
    (0, -1): Direction.UP,
    (1, 0): Direction.RIGHT,
    (-1, 0): Direction.LEFT
}

class Cell(object):
    def __init__(self, x: int, y: int, cell_type: Optional[CellType] = None) -> None:
        self.x, self.y = x, y
        self.type: CellType = cell_type or CellType.EMPTY
        self.direction: Optional[Direction] = Direction.NONE

    @property
    def canHeroPath(self) -> bool:
        return self.type is CellType.EMPTY

    @property
    def canMonsterPath(self) -> bool:
        return self.type is CellType.EMPTY or self.type is CellType.HERO or self.type is CellType.HERO_PATH

    @property
    def isFogged(self) -> bool:
        return self.type is CellType.MONSTER_FOG or self.type is CellType.MONSTER_FOG_NEW

    def getNeighbors(self) -> List[Tuple[int, int]]:
        """Generate list of pairs of integers containing positions of all neighboring tiles."""
        neighbors = []
        for offset in offsets.keys():
            neighbors.append((self.x + offset[0], self.y + offset[1]))
        return neighbors

    def __str__(self) -> str:
        if self.direction is not None and self.type is CellType.HERO_PATH:
            return str(self.direction.value)
        return str(self.type.value)

    def __repr__(self) -> str:
        return self.__str__()


class Node(object):
    def __init__(self, cell: Cell, origin: Optional['Node'] = None) -> None:
        self.cell = cell
        self.origin = origin
        self.distance = origin.distance + 1 if self.origin else 0

    @classmethod
    def get_direction(cls, node: 'Node') -> Direction:
        prev: Node = node.origin
        offset = (node.cell.x - prev.cell.x, node.cell.y - prev.cell.y)
        return offsets[offset]

    def backtrack(self) -> List['Node']:
        nodeList: List[Node] = []
        cur: Node = self

        while cur is not None:
            nodeList.insert(0, cur)
            cur = cur.origin

        return nodeList

input.dat

########
#M..A..#
#.#.M#.#
#M#..#..
#.######

main.py

from typing import List, Optional

from grid import Cell, CellType, Node

with open('test.dat') as file:
    raw = file.read().split('\n')
    raw = list(filter(lambda line: len(line) > 0, raw))

width = max(map(len, raw))
height = len(raw)
print(width, height)

grid = [[Cell(x, y) for x in range(width)] for y in range(height)]


def is_valid(x, y) -> bool:
    """Returns True if the given coordinate is valid and real."""
    return width > x >= 0 and height > y >= 0


def is_border(x, y) -> bool:
    """Returns True if the given coordinate sits on the border of the map, i.e. a ending position"""
    return x == 0 or x == width - 1 or y == 0 or y == height - 1


hero_open: List[Node] = []
monsters_open: List[Node] = []

for y, line in enumerate(raw):
    for x, char in enumerate(line):
        if char == '#':
            grid[y][x].type = CellType.WALL
        elif char == 'M':
            grid[y][x].type = CellType.MONSTER
            monsters_open.append(Node(grid[y][x]))
        elif char == 'A':
            grid[y][x].type = CellType.HERO
            hero_open.append(Node(grid[y][x]))


def printState() -> None:
    print('\n'.join([''.join(map(str, line)) for line in grid]))
    print(f'\nhero: {len(hero_open):2} monster: {len(monsters_open):2}')


bestPath: Optional[Node] = None

# While hero has not made it to the border and hero can still path
while True:
    # Print current state of the map
    printState()
    input()

    nextProcess: List[Node] = []
    # Process all newly opened hero nodes
    while len(hero_open) > 0:
        next: Node = hero_open.pop(0)

        # Check if this tile could've been hit by the monster's pathing
        if next.cell.type in [CellType.MONSTER_FOG, CellType.MONSTER_FOG_NEW]:
            continue

        if is_border(next.cell.x, next.cell.y):
            bestPath = next
            break

        # Begin looking for explorable neighbors
        for neighbor in next.cell.getNeighbors():
            # Ensure that the neighbor is a valid position on the grid
            if not is_valid(neighbor[0], neighbor[1]): continue

            # Acquire the cell referenced by this node
            cell: Cell = grid[neighbor[1]][neighbor[0]]

            # Ensure this cell is pathable and not occupied
            if not cell.canHeroPath: continue

            # Tile is valid for opening, append it to the list
            newNode = Node(cell, origin=next)
            nextProcess.append(newNode)
            cell.type = CellType.HERO_PATH
            cell.direction = Node.get_direction(newNode)

    if bestPath is not None:
        printState()
        break

    # Add all newly opened tiles to the list
    hero_open.extend(nextProcess)

    nextProcess = []  # Reset for monster processing
    while len(monsters_open) > 0:
        next: Node = monsters_open.pop(0)
        next.cell.type = CellType.MONSTER_FOG

        for neighbor in next.cell.getNeighbors():
            if not is_valid(neighbor[0], neighbor[1]): continue
            cell: Cell = grid[neighbor[1]][neighbor[0]]
            if not cell.canMonsterPath: continue
            nextProcess.append(Node(cell, origin=next))
            cell.type = CellType.MONSTER_FOG_NEW

    # Add all newly opened monster tiles to the monster open tile list
    monsters_open.extend(nextProcess)

if bestPath is not None:
    print(''.join(map(lambda node: str(node.cell.direction.value), bestPath.backtrack())))

test.dat

# #################
# ###############A#
#                 #
# # ###### ###### #
# #      #      #
# # #### ##### ## #
# # #      # #  #M#
# # # # #  # #  # #
# # # # #  #M#  # #
# # # #           #
# ############### #