Diskuze: A star ( A* ) algoritmus v GML - zkuste si, je to docela zábava

V předchozím kvízu, Online test znalostí GameMakeru, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity

TomBen

Tvůrce

TomBen:11.10.2020 12:26

A star algoritmus slouží k hledání optimální cesty k cíli.
Používá se ve hrách stejně jako při jakémkoli navigování.
Pro fungování je potřeba mít definovány jakákoli místa přes která lze procházet a jejich spojnice.
Čili něco jako: máme bod A, z něj vede cesta do bodů B a C. K bodu B je to 12 jednotek daleko, k bodu C 10 jednotek.
Algoritmus prochází jednotlivé spojnice a hledá nejkratší cestu k cíli.
Bylo matematicky prokázáno, že A* algoritmus je nejlepší způsob jak to udělat správně bez zbytečných průchodů.

Jako nejkratší cestu v daném okamžiku rozpracování považuje algoritmus tu, která má nejmenší hodnotu součtu
své dosavadní dráhy a vzdušné vzdálenosti k cíli. Prostě např. ze dvou stejných cest vybere na křižovatce tu,
která se nejvíc blíží vzdušné čáře k cíli.

Prakticky si A* zapisuje všechny cesty z konkrétního bodu, ale věnuje se jen té nejkratší v tom daném okamžiku.
Pokud postup nejkratší předpokládanou cestou začne být delší než jakýkoli kousek cesty, kterou pro délku opustil,
vrátí se tam. Takže hledá ve větvích pomyslného stromu cest vždy tu nejkratší v té dané chvíli a tu rozvine dál.

Ovládání spustitelné verze:
levá myš na bodu: start
pravá myš na bodu: cíl
levá myš na tlačítko A*: spustí hledání cesty mezi startem a cílem
pravá myš na tlačítko A*: smaže start i cíl a záznam o cestě, pokud existuje
kurzor myši nad bodem, klávesa DELETE: smaže bod
prostřední myš tažení: vytvoří novou spojnici a pokud na ní chybí začáteční či koncový bod, vytvoří je

Otestováno na Windows 10.**

http://codegarage.cz/…r/A_star.exe
http://codegarage.cz/…r/A_star.gmz

Odpovědět

11.10.2020 12:26

Za posledních 200 miliónů let se nic zvláštního nestalo, akorát dinosauři vymřeli a opice se naučily programovat.

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 1 zpráv z 1.