Untitled

from Drones import SpawnDrone
from f0 import Plant
from util import goto

DIRECTIONS = [North, South, East, West]
OPPOSITE = {
	North: South,
	South: North,
	East: West,
	West: East,
}
DELTA = {
	North: (0, 1),
	South: (0, -1),
	East: (1, 0),
	West: (-1, 0),
}

SUBSTANCE_AMOUNT = 0


def get_dynamic_k():
	size = get_world_size()
	if size <= 8:
		return 6
	return 22


def wait_one_tick():
	can_move(North)


def reverse_list(items):
	rev = []
	idx = len(items) - 1
	while idx >= 0:
		rev.append(items[idx])
		idx -= 1
	return rev


def get_move_direction(c1, c2):
	dx = c2[0] - c1[0]
	dy = c2[1] - c1[1]
	for d in DELTA:
		if DELTA[d] == (dx, dy):
			return d
	return None


def execute_moves(moves):
	for d in moves:
		move(d)


def execute_moves_backward(moves):
	rev = reverse_list(moves)
	for d in rev:
		move(OPPOSITE[d])


def handle_chest_and_reset():
	for _ in range(5):
		if get_entity_type() == Entities.Treasure:
			use_item(Items.Weird_Substance, SUBSTANCE_AMOUNT)

	if get_entity_type() == Entities.Treasure:
		harvest()


def visit_and_process(worker, target_coord):
	if target_coord not in worker["paths"]:
		return

	outward = worker["paths"][target_coord]
	execute_moves(outward)
	handle_chest_and_reset()
	execute_moves_backward(outward)


def spawn_worker_drone(forbidden_dir, k, maze_start_time):
	res = SpawnDrone(worker_main, (forbidden_dir, k, maze_start_time))
	if res == False:
		harvest()
	return res


def establish_center_home(forbidden_dir, k):
	path = []
	forbidden = forbidden_dir

	while len(path) < 2 * k:
		moved = False
		for d in DIRECTIONS:
			if d != forbidden and can_move(d):
				move(d)
				path.append(d)
				forbidden = OPPOSITE[d]
				moved = True
				break
		if not moved:
			break

	chosen_depth = len(path) // 2
	steps_to_backtrack = len(path) - chosen_depth

	while steps_to_backtrack > 0:
		d = path.pop()
		move(OPPOSITE[d])
		steps_to_backtrack -= 1

	home_coord = (get_pos_x(), get_pos_y())
	return home_coord


def map_territory(home_coord, k, boundary_parent_coord, maze_start_time):
	tree = {
		home_coord: {
			"coord": home_coord,
			"parent": None,
			"children": [],
		}
	}

	def dfs(cur_coord, depth):
		for d in DIRECTIONS:
			if can_move(d):
				dx, dy = DELTA[d]
				next_coord = (cur_coord[0] + dx, cur_coord[1] + dy)

				if next_coord == boundary_parent_coord:
					continue

				if next_coord not in tree:
					move(d)

					if depth == k:
						has_deeper_path = False
						for forward_d in DIRECTIONS:
							if forward_d != OPPOSITE[d] and can_move(forward_d):
								has_deeper_path = True
								break

						if has_deeper_path:
							spawn_worker_drone(OPPOSITE[d], k, maze_start_time)
						else:
							tree[next_coord] = {
								"coord": next_coord,
								"parent": cur_coord,
								"children": [],
							}
							tree[cur_coord]["children"].append(next_coord)
					else:
						tree[next_coord] = {
							"coord": next_coord,
							"parent": cur_coord,
							"children": [],
						}
						tree[cur_coord]["children"].append(next_coord)
						dfs(next_coord, depth + 1)

					move(OPPOSITE[d])

	dfs(home_coord, 0)
	return tree


def precompute_worker(starting_location, home_coord, tree):
	nodes = []
	edges = []
	adj = {}

	for c in tree:
		nodes.append(c)
		adj[c] = []

	for c in tree:
		p = tree[c]["parent"]
		if p != None and p in tree:
			edges.append((c, p))
			adj[c].append(p)
			adj[p].append(c)

	paths = {}
	parent_in_path = {home_coord: None}
	queue = [home_coord]

	while len(queue) > 0:
		curr = queue.pop(0)
		for neighbor in adj[curr]:
			if neighbor not in parent_in_path:
				parent_in_path[neighbor] = curr
				queue.append(neighbor)

	for target in nodes:
		steps = []
		curr = target
		while curr != home_coord:
			p = parent_in_path[curr]
			steps.append(get_move_direction(p, curr))
			curr = p
		paths[target] = reverse_list(steps)

	return {
		"starting_location": starting_location,
		"home": home_coord,
		"nodes": nodes,
		"edges": edges,
		"paths": paths,
	}


def run_farming_loop(worker, maze_start_time):
	active_search_time = maze_start_time + 90

	while True:
		if get_entity_type() == Entities.Grass:
			return

		if get_time() < active_search_time:
			wait_one_tick()
			continue

		target = measure()
		if target != None:
			if target in worker["paths"]:
				visit_and_process(worker, target)
			else:
				wait_one_tick()
		else:
			wait_one_tick()


def worker_main(args):
	forbidden_dir = args[0]
	k = args[1]
	maze_start_time = args[2]
	starting_location = (get_pos_x(), get_pos_y())

	parent_boundary_dx, parent_boundary_dy = DELTA[forbidden_dir]
	boundary_coord = (
		starting_location[0] + parent_boundary_dx,
		starting_location[1] + parent_boundary_dy,
	)

	home_coord = establish_center_home(forbidden_dir, k)
	tree = map_territory(home_coord, k, boundary_coord, maze_start_time)
	worker_obj = precompute_worker(starting_location, home_coord, tree)

	run_farming_loop(worker_obj, maze_start_time)
	return None


def SpawnMaze():
	global SUBSTANCE_AMOUNT
	Plant(Entities.Bush)
	SUBSTANCE_AMOUNT = get_world_size() * 2 ** (num_unlocked(Unlocks.Mazes) - 1)
	use_item(Items.Weird_Substance, SUBSTANCE_AMOUNT)


def FarmMaze():
	goto(0, 0)
	SpawnMaze()
	maze_start_time = get_time()

	k = get_dynamic_k()
	root_start = (0, 0)
	root_tree = map_territory(root_start, k, None, maze_start_time)
	root_worker = precompute_worker(root_start, root_start, root_tree)

	run_farming_loop(root_worker, maze_start_time)