Použitý algoritmus | |
Knihovna se skládá ze dvou úrovní: | |
Nízká úroveň
Tuto úroveň tvoří hledače cest. Hlavička hledače je následující: Úkolem hledače je najít a načasovat cestu ze Start do End v enginu PE a vrátit pointer na tuto cestu. Jeho úklolem je taky vyznačit stopy do mapy. Jsou implementovány zakladní dva algoritmy a jejich jednodué modifikace: 1. A* algoritmus - odkazy na jeho popis najdete v sekci závěr. Pro uchování a rychlý výběr minimální z otevřených nodů jsem použil haldu (implementace v heap.c). Tento algoritmus je ješťe modifikovaný o započítávání konstantního TC, k políčkům přes které je naplánovaná cesta. To způsobí efekt raději neplánovat cesty přes už naplánované cesty, pokud existuje stejně dlouhá cesta bez cest, které ji křižují. 2. Bressenhamův algoritmus kreslení čáry - tato rychlá metoda je použita na plánování provizorní cesty. |
|
Vysoká úroveň
Vysokou úrovní myslím funkci peTimeTick, která se stará o logiku chodících postav. peTimeTick volá peManageRequests pro vyřízení požadavků pro aktuální časový tik. Poté prochází přes všechny walkery a obslouží je: 1. je čas udělat nový krok ? - ano provede test kolize s jiným walkerem - pokud nenastala kolize provede krok pokud nastala kolize provedu testy: a) kolize se stojícím walkerem b) kolize s jdoucím walkerem 2. jsem blokován ? |
|