the-farmer-was-replaced/reusable_maze.py

import utils
from utils import PQ_PUSH, PQ_POP

from maze_common import MOVEMENTS, DIRECTIONS
from maze_common import get_substance_needed, spawn_maze

treasure_x = 0
treasure_y = 0

def explore_maze():
    maze = {}

    stack = []
    visited = {}

    x = get_pos_x()
    y = get_pos_y()

    visited[(x, y)] = True

    explored_all = False

    while not explored_all:
        x = get_pos_x()
        y = get_pos_y()

        possible_moves = []

        if (x - 1, y) not in visited and can_move(West):
            possible_moves.append((x - 1, y))

        if (x + 1, y) not in visited and can_move(East):
            possible_moves.append((x + 1, y))

        if (x, y - 1) not in visited and can_move(South):
            possible_moves.append((x, y - 1))

        if (x, y + 1) not in visited and can_move(North):
            possible_moves.append((x, y + 1))

        if (len(possible_moves) == 0):
            if len(stack) == 0:
                explored_all = True
                continue

            hx, hy = utils.list_back(stack)
            stack.pop()

            move(MOVEMENTS[(hx - x, hy - y)])

            continue

        (nx, ny) = utils.list_back(possible_moves)

        stack.append((x, y))
        visited[(nx, ny)] = True
        move(MOVEMENTS[(nx - x, ny - y)])

        if (x, y) not in maze:
            maze[(x, y)] = {}

        if (nx, ny) not in maze:
            maze[(nx, ny)] = {}

        maze[(x, y)][(nx, ny)] = True
        maze[(nx, ny)][(x, y)] = True

    return maze

def backtrace(parents, start, end):
    path = [end]

    while utils.list_back(path) != start:
        path.append(parents[utils.list_back(path)])

    return path
        
def bfs(graph, start, end):
    parents = {}
    queue = []
    visited = {}

    queue.append(start)

    while len(queue) > 0:
        node = queue[0]
        queue.pop(0)

        if node == end:
            return backtrace(parents, start, end)

        if node in graph:
            for adjacent in graph[node]:
                if adjacent not in visited:
                    visited[adjacent] = True
                    parents[adjacent] = node
                    queue.append(adjacent)

    return []

def heuristic(node):
    global treasure_x
    global treasure_y

    x_heuristic = abs(node[0] - treasure_x)
    y_heuristic = abs(node[1] - treasure_y)

    return x_heuristic + y_heuristic

def cmp_function(lhs, rhs):
    return lhs[0] < rhs[0]


def a_star(graph, start, end):
    pq = utils.priority_queue(cmp_function)
    pqlen = 0

    parents = {}
    costs = {}
 
    pq[PQ_PUSH]((0, start))
    pqlen += 1

    parents[start] = start
    costs[start] = 0

    while pqlen > 0:
        _, curr = pq[PQ_POP]()
        pqlen -= 1

        if curr == end:
            return backtrace(parents, start, end)

        for next in graph[curr]:
            new_cost = costs[curr] + 1
            if next not in costs or new_cost < costs[next]:
                costs[next] = new_cost
                parents[next] = curr
                pq[PQ_PUSH]((new_cost + heuristic(next), next))
                pqlen += 1

    return []

def main(max_iters):
    global treasure_x
    global treasure_y

    utils.go_to_00()

    if not spawn_maze():
        return False
    
    maze = explore_maze()

    x = get_pos_x()
    y = get_pos_y()

    for iter in range(max_iters):
        treasure_x, treasure_y = measure()

        x = get_pos_x()
        y = get_pos_y()

        ts_start = get_time()
        if iter < 120:
            path = bfs(maze, (x, y), (treasure_x, treasure_y))
        else:
            path = a_star(maze, (x, y), (treasure_x, treasure_y))
        ts_end = get_time()

        quick_print(iter, ts_end - ts_start)

        path.pop()

        def add_if_missing(direction):
            if iter > 200:
                return

            if can_move(direction):
                dx, dy = DIRECTIONS[direction]

                if (x, y) not in maze:
                    maze[(x, y)] = {}

                if (x + dx, y + dy) not in maze:
                    maze[(x + dx, y + dy)] = {}

                maze[(x, y)][(x + dx, y + dy)] = True
                maze[(x + dx, y + dy)][(x, y)] = True

        for i in range(len(path)):
            add_if_missing(East)
            add_if_missing(West)
            add_if_missing(North)
            add_if_missing(South)

            nx, ny = path[(i + 1) * -1]
            move(MOVEMENTS[(nx - x, ny - y)])
            x = get_pos_x()
            y = get_pos_y()

        substance_needed = get_substance_needed()

        if num_items(Items.Weird_Substance) < substance_needed:
            harvest()
        elif iter == (max_iters - 1):
            harvest()
        else:
            use_item(Items.Weird_Substance, substance_needed)

    return True

def run(size, iterations = 300):
    set_world_size(size)
    if not main(iterations + 1):
        return False
    return True