Pathfinding for the ants problem

a_star.py

def a_star_search(loc, dest, ants):
    def cost_f(path):
        return len(path) + ants.distance(path[-1], dest)

    initial_path = (loc,)
    frontier = [(cost_f(initial_path), initial_path)]
    
    while frontier:
        cost, path = frontier.pop()

        if path[-1] == dest:
            return path

        for next_path in expand(path, ants):
            frontier.append((cost_f(next_path), next_path))

        frontier.sort(reverse=True)

bfs.py

from collections import deque

def breadth_first_search(loc, dest, ants):
    queue = deque()
    queue.append((loc,))
    
    while queue:
        path = queue.popleft()

        # goal test
        if path[-1] == dest:
            return path

        for next_path in expand(path, ants):
            queue.append(next_path)

    # return failure

expand.py

def expand(path, ants):
    loc = path[-1]
    for neighbour in neighbours(loc, ants):
        yield path + (neighbour,)

greedy.py

def greedy_search(loc, dest, ants):
    def cost_f(path):
        return ants.distance(path[-1], dest)

    initial_path = (loc,)
    frontier = [(cost_f(initial_path), initial_path)]
    
    while frontier:
        cost, path = frontier.pop()

        if path[-1] == dest:
            return path

        for next_path in expand(path, ants):
            frontier.append((cost_f(next_path), next_path))

        frontier.sort(reverse=True)

neighbours.py

def neighbours(loc, ants):
    for direction in ['n', 's', 'e', 'w']:
        dest = ants.destination(loc, direction)
        if ants.passable(dest):
            yield dest