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:

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

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

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

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

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

A tyto funkce:

```python
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
```

```python
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](https://kvaleya.gitlab.io/asteracer/) 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.