asteracer/specifikace.md

Specifikace

Následující dokument obsahuje specifikaci závodu, pokud ji chcete implementovat ve vašem oblíbeném jazyce. Aby závod fungoval stejně v každé implementaci, všechny výpočty jsou prováděny pomocí 64-bitových celých čísel.

Objekty

V rámci závodu definujeme tyto objekty:

class Racer:  # (loď)
    x: int
    y: int
    vx: int
    vy: int
    radius: int

class Asteroid:  # (asteroid)
    x: int
    y: int
    radius: int

class Goal:  # (gól)
    x: int
    y: int
    radius: int

class Instruction:  # (instrukce)
    vx: InstType
    vy: InstType

class BoundingBox:  # (okraj)
    min_x: int
    min_y: int
    max_x: int
    max_y: int

A tyto funkce:

def distance_squared(x1, y1, x2=0, y2=0) -> int:
    """Squared Euclidean distance between two points."""
    return (int(x1) - int(x2)) ** 2 + (int(y1) - int(y2)) ** 2

def euclidean_distance(x1, y1, x2=0, y2=0):
    """Integer Euclidean distance between two points. Uses integer square root."""
    return int(isqrt(distance_squared(x1, y1, x2, y2)))

Simulace

Každý krok simulace lze rozdělit do následujících tří fází:

1. pohyb lodi podle zadané instrukce
2. řešení kolizí
3. kontrola dosažení cíle (označení splněných cílů)

Tyto kroky jsou podrobně vysvětleny v následujících sekcích.

Poznámka 1: Pro účely optimalizace je k ukládání asteroidů a cílů vhodné použít nějakou datovou strukturu (například 2D slovník nebo K-d strom), aby stačilo kontrolovat kolize pouze okolo aktuální pozice lodi. Nezapomeňte zohlednit poloměr lodi!

Poznámka 2: Celá část druhé odmocniny, kterou simulace používá, odpovídá Python funkci math.isqrt, která vrací „největší celé číslo takové, že a² ≤ n.“ Tato implementace je přesná a nevyužívá plovoucí desetinnou čárku.

1) Pohyb lodi

S danou instrukcí (vx, vy) se loď pohybuje podle následujících pravidel:

• zpomalí se o 10 %: racer.velocity = (racer.velocity * 9) // 10
• k její rychlosti se přidá instrukce: racer.velocity += (vx, vy)
• závodník se posune podle své rychlosti: racer.position += racer.velocity

Je důležité poznamenat, že operátor dělení zahodí desetinnou část čísla. To znamená, že Pythoní celočíselné dělení nefunguje korektně pro záporná čísla (-5 // 2 = -3), což je v našem případě špatně. Jedním ze způsobů, jak to napravit, je použít abs(x) // v * signum(x), což zajistí správný výsledek.

Instrukce je platná pouze tehdy, pokud její délka (euklidovská vzdálenost) nepřesáhne 127. Kontrola délky instrukce se provádí porovnáním čtverců délky instrukce a maximálního zrychlení (distance_squared(vx, vy) > 127 ** 2).

2) Řešení kolizí

Kolize se řeší v 1 až 5 podkrocích. Každý podkrok má dvě fáze:

• kontrola kolizí s asteroidy - v této fázi dojde k nejvýše jedné kolizi
• kontrola kolizí s okraji mapy - kontrolujeme každý ze čtyř okrajů mapy

Pokud v podkroku nedojde k žádné kolizi (ani s asteroidem, ani s okrajem mapy), považujeme kolize za vyřešené. Pokud ke kolizi dojde, provedeme další podkrok. Podkroků provedeme maximálně 5.

Pokud v aspoň jednom podkroku dojde ke kolizi (ať už s asteroidem nebo s okrajem mapy), rychlost závodníka se sníží na polovinu. Toto zpomalení může tedy nastat nejvýše jednou za krok, bez ohledu na počet kolizí v individuálních podkrocích.

Asteroidy

Iterujeme přes všechny asteroidy asteroid v pořadí, v jakém byly přidány do simulace, a pro každý provádíme následující kroky:

• Pokud euclidean_distance(asteroid, racer) > (asteroid.radius + racer.radius), kolize nenastala (pokračujeme k dalšímu asteroidu).
• V případě kolize provedeme následující:
  • Spočítáme vzdálenost: distance = euclidean_distance(asteroid, racer)
  • Vektor k vytlačení závodníka: vn = racer.position - asteroid.position.
  • Vzdálenost posunutí: push_by = (asteroid.radius + racer.radius) - distance.
  • Posuneme závodníka: racer.position += (push_by * vn) / distance.
  • Přestaneme iterovat přes asteroidy a posuneme se do další fáze podkroku (řešení kolize s okrajem mapy).

Pokud by tedy loď kolidovala s více asteroidy, vyhodnotíme kolizi pouze s tím, který má nejnižší index.

Ohraničující box

Pro každou stranu boxu zkontrolujeme kolizi (například pokud racer.x - racer.radius < box.min_x pro levou stranu). Pokud ke kolizi dojde, posuneme závodníka zpět k hranici boxu.

3) Kontrola dosažení cíle

Iterujeme přes všechny cíle goal a označíme je jako dosažené, pokud euclidean_distance(racer, goal) <= (racer.radius + goal.radius), tedy pokud dochází k jejich průniku.

Poznámky

Všimněte si, že simulace má několik neintuitivních zjednodušení a vlastností:

• Při úvodním posunu lodi o její rychlost nekontrolujeme kolize.
• Kolize kontrolujeme až jako průsečík finální pozice lodi s asteroidy či cíly.
• Při kolizi s asteroidem se loď neodrazí, tedy nezmění se směr její rychlosti.
• Při řešení kolizí loď pouze posouváme ven z asteroidů.
• Při kolizi nezáleží na tom, v jaké fázi řešení podkroků vydělíme rychlost lodi dvěma.

Dále, pro detekci průsečíku lodi s asteroidem či cílem schválně používáme euclidean_distance, která má odmocninu zaokrouhlenou dolů. Sice by kolize šly počítat exaktně pomocí druhých mocnin vzdálenosti, ale v okrajových případech bychom naráželi na limity velikosti čísel. Dejte pozor, že toto neexaktní počítání kolizí je třeba implementovat i do akcelerační struktury pro hledání blízkých asteroidů a cílů, pokud nějakou budete používat.

Naše rustová (vyhodnocovadlo) i typescriptová (webová vizualizace) implementace používá místo exaktní isqrt klasickou "float64" odmocninu, kterou poté zaokrouhlí dolů na celé číslo. Pro rozsahy hodnot relevantní v této úloze dávají obě funkce stejné výsledky.

Debugování pomocí webové vizualizace

Do webové vizualizace můžete nahrát svou sadu instrukcí, kterou stránka poté vyhodnotí. Pro debugování se může hodit stáhnout si z ní "záznam simulace" následujícího formátu:

Záznam obsahuje jeden řádek pro každou vstupní instrukci. Každý řádek popisuje stav světa po vykonání dané instrukce. První dvě čísla jsou X a Y pozice lodi, třetí a čtvrté číslo je X a Y rychlost lodi. Poté následuje několik jedniček nebo nul, kdy každá odpovídá jednomu cíli. Pokud už byl v simulaci daný cíl dosažen, má hodnotu 1, jinak má hodnotu 0.