258 lines
6.0 KiB
Python
258 lines
6.0 KiB
Python
import utils
|
|
from __builtins__ import *
|
|
|
|
spawn_dirs = []
|
|
spawn_index = [0]
|
|
spawned_branches = []
|
|
treasure_found = [0]
|
|
gold_start = [0]
|
|
|
|
def pop_spawn_dir():
|
|
if spawn_index[0] >= len(spawn_dirs):
|
|
return None
|
|
direction = spawn_dirs[spawn_index[0]]
|
|
spawn_index[0] = spawn_index[0] + 1
|
|
return direction
|
|
|
|
def is_spawned_at(vx, vy, direction):
|
|
for i in range(len(spawned_branches)):
|
|
entry = spawned_branches[i]
|
|
if entry[0] == vx and entry[1] == vy and entry[2] == direction:
|
|
return True
|
|
return False
|
|
|
|
# Plant a full maze.
|
|
#
|
|
# Parameters:
|
|
# dimensions (tuple): The dimensions of the maze. If not set, default to the maximum size.
|
|
def place(dimensions=None):
|
|
if dimensions == None:
|
|
dimensions = get_world_size()
|
|
|
|
plant(Entities.Bush)
|
|
substance = dimensions * 2**(num_unlocked(Unlocks.Mazes) - 1)
|
|
use_item(Items.Weird_Substance, substance)
|
|
|
|
def solve(dimensions=None):
|
|
if dimensions == None:
|
|
dimensions = get_world_size()
|
|
|
|
treasure_found[0] = 0
|
|
gold_start[0] = num_items(Items.Gold)
|
|
spawn_index[0] = len(spawn_dirs)
|
|
|
|
grid_size = get_world_size()
|
|
|
|
directions = [North, East, South, West]
|
|
|
|
def next_pos(x, y, direction):
|
|
if direction == North:
|
|
return x, (y + 1) % grid_size
|
|
if direction == South:
|
|
return x, (y - 1) % grid_size
|
|
if direction == East:
|
|
return (x + 1) % grid_size, y
|
|
return (x - 1) % grid_size, y
|
|
|
|
def direction_between(x, y, nx, ny):
|
|
if (x + 1) % grid_size == nx and y == ny:
|
|
return East
|
|
if (x - 1) % grid_size == nx and y == ny:
|
|
return West
|
|
if x == nx and (y + 1) % grid_size == ny:
|
|
return North
|
|
return South
|
|
|
|
visited = []
|
|
x = get_pos_x()
|
|
y = get_pos_y()
|
|
visited.append([x, y])
|
|
|
|
def is_visited(vx, vy):
|
|
for i in range(len(visited)):
|
|
if visited[i][0] == vx and visited[i][1] == vy:
|
|
return True
|
|
return False
|
|
|
|
stack = [[x, y, 0]]
|
|
|
|
while len(stack) > 0:
|
|
if treasure_found[0] or num_items(Items.Gold) > gold_start[0]:
|
|
treasure_found[0] = 1
|
|
return
|
|
|
|
current = stack[-1]
|
|
x = current[0]
|
|
y = current[1]
|
|
next_dir_index = current[2]
|
|
|
|
if get_entity_type() == Entities.Treasure and can_harvest():
|
|
harvest()
|
|
treasure_found[0] = 1
|
|
return
|
|
|
|
candidates = []
|
|
for i in range(len(directions)):
|
|
direction = directions[i]
|
|
if can_move(direction):
|
|
next_xy = next_pos(x, y, direction)
|
|
nx = next_xy[0]
|
|
ny = next_xy[1]
|
|
if not is_visited(nx, ny):
|
|
candidates.append(direction)
|
|
|
|
if len(candidates) > 1 and num_drones() < max_drones():
|
|
for i in range(1, len(candidates)):
|
|
candidate = candidates[i]
|
|
if not is_spawned_at(x, y, candidate):
|
|
spawned_branches.append([x, y, candidate])
|
|
spawn_dirs.append(candidate)
|
|
spawn_drone(maze_worker)
|
|
next_xy = next_pos(x, y, candidate)
|
|
visited.append([next_xy[0], next_xy[1]])
|
|
break
|
|
|
|
moved = False
|
|
while next_dir_index < len(directions):
|
|
direction = directions[next_dir_index]
|
|
stack[-1][2] = next_dir_index + 1
|
|
if can_move(direction):
|
|
next_xy = next_pos(x, y, direction)
|
|
nx = next_xy[0]
|
|
ny = next_xy[1]
|
|
if not is_visited(nx, ny):
|
|
move(direction)
|
|
visited.append([nx, ny])
|
|
stack.append([nx, ny, 0])
|
|
moved = True
|
|
break
|
|
next_dir_index = stack[-1][2]
|
|
|
|
if moved:
|
|
continue
|
|
|
|
if len(stack) == 1:
|
|
return
|
|
|
|
prev = stack[-2]
|
|
prev_x = prev[0]
|
|
prev_y = prev[1]
|
|
back_dir = direction_between(x, y, prev_x, prev_y)
|
|
move(back_dir)
|
|
stack.pop()
|
|
|
|
def maze_worker():
|
|
start_x = get_pos_x()
|
|
start_y = get_pos_y()
|
|
|
|
grid_size = get_world_size()
|
|
directions = [North, East, South, West]
|
|
|
|
def next_pos(x, y, direction):
|
|
if direction == North:
|
|
return x, (y + 1) % grid_size
|
|
if direction == South:
|
|
return x, (y - 1) % grid_size
|
|
if direction == East:
|
|
return (x + 1) % grid_size, y
|
|
return (x - 1) % grid_size, y
|
|
|
|
def direction_between(x, y, nx, ny):
|
|
if (x + 1) % grid_size == nx and y == ny:
|
|
return East
|
|
if (x - 1) % grid_size == nx and y == ny:
|
|
return West
|
|
if x == nx and (y + 1) % grid_size == ny:
|
|
return North
|
|
return South
|
|
|
|
visited = []
|
|
visited.append([start_x, start_y])
|
|
|
|
def is_visited(vx, vy):
|
|
for i in range(len(visited)):
|
|
if visited[i][0] == vx and visited[i][1] == vy:
|
|
return True
|
|
return False
|
|
|
|
first_dir = pop_spawn_dir()
|
|
if not first_dir:
|
|
return
|
|
if not can_move(first_dir):
|
|
return
|
|
|
|
next_xy = next_pos(start_x, start_y, first_dir)
|
|
move(first_dir)
|
|
visited.append([next_xy[0], next_xy[1]])
|
|
stack = [[next_xy[0], next_xy[1], 0]]
|
|
|
|
while len(stack) > 0:
|
|
if treasure_found[0] or num_items(Items.Gold) > gold_start[0]:
|
|
treasure_found[0] = 1
|
|
return
|
|
|
|
current = stack[-1]
|
|
x = current[0]
|
|
y = current[1]
|
|
next_dir_index = current[2]
|
|
|
|
if get_entity_type() == Entities.Treasure and can_harvest():
|
|
harvest()
|
|
treasure_found[0] = 1
|
|
return
|
|
|
|
candidates = []
|
|
for i in range(len(directions)):
|
|
direction = directions[i]
|
|
if can_move(direction):
|
|
next_xy = next_pos(x, y, direction)
|
|
nx = next_xy[0]
|
|
ny = next_xy[1]
|
|
if not is_visited(nx, ny):
|
|
candidates.append(direction)
|
|
|
|
if len(candidates) > 1 and num_drones() < max_drones():
|
|
for i in range(1, len(candidates)):
|
|
candidate = candidates[i]
|
|
if not is_spawned_at(x, y, candidate):
|
|
spawned_branches.append([x, y, candidate])
|
|
spawn_dirs.append(candidate)
|
|
spawn_drone(maze_worker)
|
|
next_xy = next_pos(x, y, candidate)
|
|
visited.append([next_xy[0], next_xy[1]])
|
|
break
|
|
|
|
moved = False
|
|
while next_dir_index < len(directions):
|
|
direction = directions[next_dir_index]
|
|
stack[-1][2] = next_dir_index + 1
|
|
if can_move(direction):
|
|
next_xy = next_pos(x, y, direction)
|
|
nx = next_xy[0]
|
|
ny = next_xy[1]
|
|
if not is_visited(nx, ny):
|
|
move(direction)
|
|
visited.append([nx, ny])
|
|
stack.append([nx, ny, 0])
|
|
moved = True
|
|
break
|
|
next_dir_index = stack[-1][2]
|
|
|
|
if moved:
|
|
continue
|
|
|
|
prev_x = start_x
|
|
prev_y = start_y
|
|
if len(stack) > 1:
|
|
prev = stack[-2]
|
|
prev_x = prev[0]
|
|
prev_y = prev[1]
|
|
|
|
back_dir = direction_between(x, y, prev_x, prev_y)
|
|
move(back_dir)
|
|
stack.pop()
|
|
|
|
if len(stack) == 0:
|
|
if get_pos_x() == start_x and get_pos_y() == start_y:
|
|
return
|