569 lines
19 KiB
Python
569 lines
19 KiB
Python
"""Tom's solution to Asteracer. Moves on the vertices of the asteroid graph by simulating all angles."""
|
|
import os
|
|
from typing import Optional
|
|
|
|
import drawsvg as draw
|
|
import networkx as nx
|
|
import numpy as np
|
|
|
|
from asteracer import *
|
|
|
|
directional_instructions_cache = {}
|
|
|
|
Vertex = tuple[int, int]
|
|
|
|
|
|
def load_asteroid_graph(path: str):
|
|
with open(path) as file:
|
|
lines = [line.strip() for line in file.readlines()]
|
|
|
|
# Filter out comments and empty lines
|
|
contents = [line for line in lines if line and not line.startswith('#')]
|
|
|
|
iter_lines = iter(contents)
|
|
first_line = list(map(int, next(iter_lines).split()))
|
|
n_racer, n_asteroid, n_goal, m = first_line
|
|
|
|
vertices = []
|
|
edges = []
|
|
vertex_objects = []
|
|
|
|
# Load vertices
|
|
for i in range(n_racer + n_asteroid + n_goal):
|
|
line = list(map(int, next(iter_lines).split()))
|
|
vertices.append((line[0], line[1]))
|
|
|
|
if i < n_racer:
|
|
vertex_objects.append(('S', i))
|
|
elif i < (n_racer + n_asteroid):
|
|
vertex_objects.append(('A', line[2]))
|
|
else:
|
|
vertex_objects.append(('G', line[2]))
|
|
|
|
# Load edges
|
|
for _ in range(m):
|
|
line = list(map(int, next(iter_lines).split()))
|
|
edges.append((line[0], line[1]))
|
|
|
|
return vertices, edges, vertex_objects
|
|
|
|
|
|
def _yield_points_at_distance(x: float, y: float, r: float, n: int):
|
|
"""Generate n points uniformly at distance r from the coordinates (x, y)."""
|
|
for i in range(n):
|
|
t = (i / n) * np.pi * 2
|
|
yield x + np.cos(t) * r, y + np.sin(t) * r
|
|
|
|
|
|
def _get_directional_instructions(
|
|
n: int = 1000,
|
|
sort_by_angle_to: tuple[float, float] = None,
|
|
limit_angle=None
|
|
) -> list[Instruction]:
|
|
"""Generate normalized instructions in at most n different angles with maximum velocity."""
|
|
instructions = []
|
|
|
|
if n in directional_instructions_cache:
|
|
instructions = directional_instructions_cache[n]
|
|
|
|
else:
|
|
for point in _yield_points_at_distance(0, 0, 127, n):
|
|
i1 = Instruction(*point)
|
|
|
|
if i1 in instructions:
|
|
continue
|
|
|
|
for i2 in instructions:
|
|
if np.sign(i1.vx) == np.sign(i2.vx) and abs(i1.vx) <= abs(i2.vx) \
|
|
and np.sign(i1.vy) == np.sign(i2.vy) and abs(i1.vy) <= abs(i2.vy):
|
|
break
|
|
else:
|
|
instructions.append(i1)
|
|
|
|
directional_instructions_cache[n] = instructions
|
|
|
|
def instr_vector_angle(i_from: Instruction, v_to: tuple[float, float]) -> float:
|
|
"""The angle between an instruction and a vector."""
|
|
i_vec = np.array([i_from.vx, i_from.vy])
|
|
o_vec = np.array(v_to)
|
|
return (1 - np.dot(i_vec, o_vec) / (np.linalg.norm(i_vec) * np.linalg.norm(o_vec))) / 2
|
|
|
|
# possibly sort by an angle to a given instruction
|
|
if sort_by_angle_to:
|
|
instructions = sorted(instructions, key=lambda x: instr_vector_angle(x, sort_by_angle_to))
|
|
|
|
if limit_angle:
|
|
return [i for i in instructions if abs(instr_vector_angle(i, sort_by_angle_to)) <= limit_angle]
|
|
else:
|
|
return instructions
|
|
else:
|
|
return instructions
|
|
|
|
|
|
def instructions_to_position(
|
|
simulation: Simulation,
|
|
position: Vertex,
|
|
try_ticks=7,
|
|
max_distance=1.25,
|
|
) -> Optional[list[Instruction]]:
|
|
"""Return a sequence of instructions that brings us the closest to the provided coordinates.
|
|
Returns None if there is no such set that brings us at most max_distance * racer_radius away."""
|
|
x, y = position
|
|
|
|
best_distance = float('inf')
|
|
best_instructions = None
|
|
|
|
def is_safe(simulation: Simulation) -> bool:
|
|
"""Returns True if the racer has a sequence of instructions to not crash at this stage of the simulation."""
|
|
simulation.push()
|
|
for instruction in _get_directional_instructions(10):
|
|
simulation.apply()
|
|
|
|
for _ in range(try_ticks):
|
|
result = simulation.tick(instruction)
|
|
|
|
if result & TickFlag.COLLIDED:
|
|
break
|
|
else:
|
|
simulation.pop()
|
|
return True
|
|
|
|
simulation.pop()
|
|
return False
|
|
|
|
simulation.push()
|
|
for inst in _get_directional_instructions(
|
|
sort_by_angle_to=(x - int(simulation.racer.x), y - int(simulation.racer.y)),
|
|
limit_angle=0.5
|
|
):
|
|
simulation.apply()
|
|
started_improving = False
|
|
prev_dist = 0
|
|
|
|
i = 0
|
|
while True:
|
|
result = simulation.tick(inst)
|
|
|
|
if result & TickFlag.COLLIDED:
|
|
break
|
|
|
|
distance = euclidean_distance(simulation.racer.x, simulation.racer.y, x, y)
|
|
|
|
# if we're closer than before, we started improving
|
|
if distance < prev_dist:
|
|
started_improving = True
|
|
|
|
# if we've started improving but are now getting worse, terminate this instruction
|
|
if started_improving and distance > prev_dist:
|
|
break
|
|
|
|
prev_dist = distance
|
|
|
|
# if we improved and are safe, save results
|
|
if distance < best_distance and is_safe(simulation):
|
|
best_distance = distance
|
|
best_instructions = [inst] * i
|
|
|
|
i += 1
|
|
|
|
simulation.pop()
|
|
|
|
if best_distance > max_distance * simulation.racer.radius:
|
|
return None
|
|
|
|
return best_instructions
|
|
|
|
|
|
def get_preview(simulation: Simulation, size=1000):
|
|
"""Generate preview of the simulation as an SVG."""
|
|
d = draw.Drawing(size, size, origin='center')
|
|
|
|
# background
|
|
d.append(
|
|
draw.Rectangle(
|
|
-size / 2, -size / 2,
|
|
size, size,
|
|
fill="White"
|
|
)
|
|
)
|
|
|
|
def draw_circles(circles: list[Asteroid | Goal | Racer], color: str):
|
|
"""Draw a circle with a specific color on the SVG."""
|
|
s = simulation.bounding_box.width() / size
|
|
|
|
for i, circle in enumerate(circles):
|
|
d.append(draw.Circle(circle.x / s, circle.y / s, circle.radius / s, fill=color, stroke=color))
|
|
|
|
draw_circles(simulation.asteroids, "Black")
|
|
draw_circles([g for i, g in enumerate(simulation.goals) if simulation.reached_goals[i]], "LightGreen")
|
|
draw_circles([g for i, g in enumerate(simulation.goals) if not simulation.reached_goals[i]], "Red")
|
|
draw_circles([simulation.racer], "Gray")
|
|
|
|
return d
|
|
|
|
|
|
def get_solution_preview(
|
|
simulation: Simulation,
|
|
simulation_path: Optional[list[Vertex]],
|
|
color: str = "Green"
|
|
) -> draw.Drawing:
|
|
"""Return an SVG object with the solution graph, possibly with the simulation too."""
|
|
d = get_preview(simulation)
|
|
s = simulation.bounding_box.width() / d.width
|
|
|
|
def draw_path(path, color, stroke_width, stroke_opacity) -> draw.Path:
|
|
p = draw.Path(stroke_width=stroke_width, stroke=color, opacity=stroke_opacity, fill_opacity=0)
|
|
|
|
p.M(path[0][0] / s, path[0][1] / s)
|
|
for i in range(1, len(path)):
|
|
p.L(path[i][0] / s, path[i][1] / s)
|
|
d.append(p)
|
|
|
|
if simulation_path:
|
|
d.append(draw_path(simulation_path, color, simulation.racer.radius / (s * 2), 1))
|
|
|
|
return d
|
|
|
|
|
|
def get_checkpoints_path(
|
|
simulation, vertices, edges, goal_vertices,
|
|
longest_edges,
|
|
):
|
|
"""Get a path that the rocket should follow to obtain all goals."""
|
|
|
|
def astar_heuristic(p1, p2):
|
|
return np.linalg.norm(np.array(p1) - np.array(p2))
|
|
|
|
def perturb_shortest_path(G, best_path, penalty_factor=2.0):
|
|
""" Perturbs the shortest path by increasing the weight of a random edge. """
|
|
if len(best_path) < 2:
|
|
return best_path # No modification possible
|
|
|
|
# Randomly choose an edge along the best path
|
|
idx = random.randint(2, len(best_path) - 3)
|
|
u, v = best_path[idx], best_path[idx + 1]
|
|
|
|
if G.has_edge(u, v):
|
|
original_weight = G[u][v].get("weight", 1.0)
|
|
G[u][v]["weight"] = original_weight * penalty_factor
|
|
if G.has_edge(v, u): # If the graph is undirected
|
|
G[v][u]["weight"] = original_weight * penalty_factor
|
|
|
|
perturbed_path = nx.astar_path(G, best_path[0], best_path[-1], heuristic=astar_heuristic)
|
|
|
|
return perturbed_path
|
|
|
|
# convert vertices, edges to nx.Graph
|
|
G = nx.Graph()
|
|
for v in vertices:
|
|
G.add_node(v)
|
|
for u, v in edges:
|
|
G.add_edge(u, v, weight=np.linalg.norm(np.array(u) - np.array(v)))
|
|
|
|
# for more than 1 goal, we have to solve TSP (at least approximately)
|
|
if len(simulation.goals) > 1:
|
|
G_tsp = nx.DiGraph()
|
|
|
|
tsp_vertices = [(simulation.racer.x, simulation.racer.y)]
|
|
|
|
for g in simulation.goals:
|
|
tsp_vertices.append((g.x, g.y))
|
|
G_tsp.add_node(tsp_vertices[-1])
|
|
|
|
count = 0
|
|
for i, u in enumerate(tsp_vertices):
|
|
for v in tsp_vertices[i + 1:]:
|
|
print(f"TSP: building graph {count + 1}/{len(tsp_vertices) * (len(tsp_vertices) - 1) // 2}")
|
|
w = nx.astar_path_length(G, u, v, heuristic=astar_heuristic)
|
|
G_tsp.add_edge(u, v, weight=w)
|
|
G_tsp.add_edge(v, u, weight=w)
|
|
|
|
count += 1
|
|
|
|
print(f"TSP: graph built")
|
|
|
|
# nx doesn't play nice with infinite values, but this might as well be
|
|
INF = 100000000000
|
|
|
|
# we solve TSP by adding a hack vertex to force us to try all possible ending vertices
|
|
# this means that we have to solve #number_of_vertices instances of TSP
|
|
G_tsp.add_node("hack")
|
|
G_tsp.add_edge(vertices[0], "hack", weight=0)
|
|
G_tsp.add_edge("hack", vertices[0], weight=INF)
|
|
|
|
best_cost = float('inf')
|
|
best_path = None
|
|
|
|
for i, g in enumerate(simulation.goals):
|
|
print(f"TSP: solving {i + 1}/{len(simulation.goals)}")
|
|
|
|
for g_hack in simulation.goals:
|
|
v = (g_hack.x, g_hack.y)
|
|
G_tsp.add_edge("hack", v, weight=0 if g is g_hack else INF)
|
|
G_tsp.add_edge(v, "hack", weight=INF)
|
|
|
|
path = nx.approximation.simulated_annealing_tsp(G_tsp, init_cycle="greedy")
|
|
path.pop()
|
|
|
|
cost = 0
|
|
for j in range(len(path)):
|
|
cost += G_tsp[path[j - 1]][path[j]]["weight"]
|
|
|
|
for g_hack in simulation.goals:
|
|
v = (g_hack.x, g_hack.y)
|
|
G_tsp.remove_edge("hack", v)
|
|
G_tsp.remove_edge(v, "hack")
|
|
|
|
path = list(reversed(path))
|
|
j = path.index("hack")
|
|
path.remove("hack")
|
|
path = path[j:] + path[:j]
|
|
|
|
assert len(path) == len(simulation.goals) + 1, "Not all goals visited!"
|
|
|
|
if cost < best_cost:
|
|
best_path = path
|
|
best_cost = cost
|
|
print(f"TSP: new optimum of length {best_cost}")
|
|
|
|
path = [(int(simulation.racer.x), int(simulation.racer.y))]
|
|
for i in range(len(best_path) - 1):
|
|
path += nx.astar_path(G, best_path[i], best_path[i + 1], heuristic=astar_heuristic)[1:]
|
|
|
|
# last vertex is a center of some goal
|
|
path = path[:-1]
|
|
|
|
# shorten the path by cutting out vertices
|
|
while True:
|
|
# try to remove vertices for goals
|
|
for i in range(len(path) - 2):
|
|
if not G.has_edge(path[i], path[i + 2]):
|
|
continue
|
|
|
|
# if it's not a part of a goal, we can remove for free
|
|
if path[i + 1] not in goal_vertices:
|
|
path.pop(i + 1)
|
|
break
|
|
|
|
# if it is and is not the only one, we can remove it too
|
|
goal_vertices_count = 0
|
|
for v in path:
|
|
if v in goal_vertices and goal_vertices[v] == goal_vertices[path[i + 1]]:
|
|
goal_vertices_count += 1
|
|
|
|
if goal_vertices_count != 1:
|
|
path.pop(i + 1)
|
|
break
|
|
else:
|
|
break
|
|
|
|
# rotate goal vertices (we can take an arbitrary one to get the goal)
|
|
while True:
|
|
improved = False
|
|
|
|
for i in range(len(path) - 2):
|
|
u = path[i + 1]
|
|
|
|
if u not in goal_vertices:
|
|
continue
|
|
|
|
for v in vertices:
|
|
if v not in goal_vertices:
|
|
continue
|
|
|
|
if goal_vertices[u] != goal_vertices[v]:
|
|
continue
|
|
|
|
if not G.has_edge(path[i], v) or not G.has_edge(v, path[i + 2]):
|
|
continue
|
|
|
|
u_dist = G[path[i]][u]["weight"] + G[u][path[i + 2]]["weight"]
|
|
v_dist = G[path[i]][v]["weight"] + G[v][path[i + 2]]["weight"]
|
|
|
|
if u_dist > v_dist:
|
|
path = path[:i + 1] + [v] + path[i + 2:]
|
|
improved = True
|
|
break
|
|
|
|
if not improved:
|
|
break
|
|
|
|
# TODO: remove goal vertices entirely if the edge exists and intersects it
|
|
# TODO: for each goal, attempt to remove vertex and connect astar to next and to previous
|
|
|
|
print("Solved with TSP.")
|
|
else:
|
|
path = nx.astar_path(
|
|
G,
|
|
(simulation.racer.x, simulation.racer.y),
|
|
(simulation.goals[0].x, simulation.goals[0].y),
|
|
heuristic=astar_heuristic,
|
|
)
|
|
|
|
path = perturb_shortest_path(G, path, penalty_factor=1000)
|
|
|
|
print("Solved with A*.")
|
|
|
|
# split long edges
|
|
while True:
|
|
split = False
|
|
|
|
i = 0
|
|
while i < len(path) - 1:
|
|
if euclidean_distance(*path[i], *path[i + 1]) > longest_edges:
|
|
x = path[i][0] + path[i + 1][0]
|
|
y = path[i][1] + path[i + 1][1]
|
|
path.insert(i + 1, (x / 2, y / 2))
|
|
split = True
|
|
i += 1
|
|
|
|
if not split:
|
|
break
|
|
|
|
return path
|
|
|
|
|
|
def finalize_instructions(simulation, instructions):
|
|
"""Finalize the instructions (cut useless ones + extend if the simulation isn't finished)."""
|
|
simulation.restart()
|
|
for i, instruction in enumerate(instructions):
|
|
simulation.tick(instruction)
|
|
|
|
# there might be some redundant instructions at the very end
|
|
if simulation.finished():
|
|
break
|
|
|
|
instructions = instructions[:i + 1]
|
|
|
|
# if we ended just before the goal, repeat last instruction
|
|
simulation.simulate(instructions)
|
|
i = 0
|
|
while not simulation.finished():
|
|
simulation.tick(instruction)
|
|
instructions.append(instruction)
|
|
i += 1
|
|
|
|
if i > 1000:
|
|
break
|
|
|
|
return instructions
|
|
|
|
|
|
def get_solution_path(simulation, instructions):
|
|
"""Generate the path the racer took using the instructions."""
|
|
simulation.restart()
|
|
solution_path = [(simulation.racer.x, simulation.racer.y)]
|
|
for i, instruction in enumerate(instructions):
|
|
simulation.tick(instruction)
|
|
solution_path.append((simulation.racer.x, simulation.racer.y))
|
|
|
|
return solution_path
|
|
|
|
|
|
def solve(simulation, path):
|
|
"""Solve the simulation by following the path."""
|
|
steps_instructions = []
|
|
randomize_step_counter = 0
|
|
i = 1
|
|
while i < len(path):
|
|
v = path[i]
|
|
|
|
for goal in simulation.goals:
|
|
if euclidean_distance(goal.x, goal.y, v[0], v[1]) < goal.radius + simulation.racer.radius:
|
|
is_goal_position = True
|
|
break
|
|
else:
|
|
is_goal_position = False
|
|
|
|
print(f"Simulating {i}/{len(path) - 1}{'' if not is_goal_position else ' to goal'}", end=": ", flush=True)
|
|
|
|
if randomize_step_counter:
|
|
print("randomized, ", end="")
|
|
|
|
# only move towards the goal
|
|
if is_goal_position:
|
|
p2g_vector = np.array([goal.x, goal.y]) - np.array(v)
|
|
v = (p2g_vector / np.linalg.norm(p2g_vector)) * np.random.normal(0, simulation.racer.radius, 1)
|
|
else:
|
|
v = np.array(v) + np.random.normal(0, simulation.racer.radius, 2)
|
|
|
|
new_instructions = instructions_to_position(simulation, v, max_distance=2 if not is_goal_position else 0.75)
|
|
|
|
if new_instructions is None:
|
|
if len(steps_instructions) != 0:
|
|
randomize_step_counter += 1
|
|
|
|
i -= randomize_step_counter
|
|
for _ in range(randomize_step_counter):
|
|
steps_instructions.pop()
|
|
|
|
print(f"(- backtrack {randomize_step_counter}x)")
|
|
|
|
if len(steps_instructions) != 0:
|
|
simulation.simulate(list(np.hstack(steps_instructions)))
|
|
else:
|
|
simulation.restart()
|
|
|
|
continue
|
|
else:
|
|
randomize_step_counter = max(randomize_step_counter - 1, 0)
|
|
|
|
steps_instructions.append(new_instructions)
|
|
simulation.simulate(list(np.hstack(steps_instructions)))
|
|
|
|
print(f"(+ {len(new_instructions)})")
|
|
|
|
i += 1
|
|
|
|
return finalize_instructions(simulation, list(np.hstack(steps_instructions)))
|
|
|
|
|
|
if __name__ == "__main__":
|
|
iterations = 5000
|
|
|
|
for task in ["sprint"]:
|
|
print(f"Solving {task} ({iterations} attempts):")
|
|
|
|
os.makedirs(task, exist_ok=True)
|
|
|
|
simulation = Simulation.load(f"../mapy/{task}.txt")
|
|
print("Simulation loaded.")
|
|
|
|
vertices, edges, object_types = load_asteroid_graph(f"../grafy/{task}.txt")
|
|
edges = [(vertices[u], vertices[v]) for u, v in edges]
|
|
|
|
print("Graph loaded.")
|
|
|
|
average_asteroid_radius = sum([asteroid.radius for asteroid in simulation.asteroids]) / len(simulation.asteroids)
|
|
goal_vertices = {
|
|
vertices[i]: (simulation.goals[j].x, simulation.goals[j].y)
|
|
for (i, (c, j)) in enumerate(object_types)
|
|
if c == "G"
|
|
}
|
|
|
|
best_instructions = None
|
|
best_instructions_length = float('inf')
|
|
|
|
i = 0
|
|
while i < iterations:
|
|
simulation.restart()
|
|
path = get_checkpoints_path(
|
|
simulation,
|
|
vertices, edges, goal_vertices,
|
|
longest_edges=average_asteroid_radius * np.random.uniform(0.5, 5),
|
|
)
|
|
|
|
instructions = solve(simulation, path)
|
|
i += 1
|
|
|
|
if len(instructions) < best_instructions_length:
|
|
best_instructions = instructions
|
|
best_instructions_length = len(instructions)
|
|
print(f"Solved with {len(instructions)} instructions.")
|
|
|
|
solution_path = get_solution_path(simulation, best_instructions)
|
|
d = get_solution_preview(simulation, solution_path, "Green")
|
|
d.save_svg(f"{task}/solution.svg")
|
|
save_instructions(f"{task}/solution.txt", best_instructions)
|
|
|
|
print(f"Best solution: {len(best_instructions)} instructions.")
|