Pathfinding systém u hry typu had

[Witiko]

Dělám remake klasického hada s několika vychytávkami a mám zde menší problém. Konkrétně je zde určitý typ jídla, který po určitém počtu tahů mizí. Počet tahů je vypočítaný podle počtu políček mezi hadem a jídlem. Často je ovšem mezi hadem a jídlem překážka ve formě hadova těla a proto jsem si uvědomil, že by byl vhodnější trackfinding systém.

Vezměme si následující příklad:


Bylo by asi dobré říci, že had umí procházet zdí, takže to samé se očekává i po trackfinding systému. První problém, který zdánlivě znemožňuje využití algorytmu typu šíření do šířky je tělo hada. Kontrola, jestli je v daném tahu již daný segment těla pryč by neměla být složitá a spočívá v přiřazení jednotlivým segmentům čísla, které bude reprezentovat životnost políčka. Nějak takto:



Daný algoritmus by tedy bylo možné použít, přičemž kontrola, je-li na daném políčku tělo by probíhala ve formě porovnání "aktuálního tahu" trackfinding systému a daného čísla životnosti. Je-li číslo určující tah vyšší, je již políčko volné. Nicméně je zde i druhý problém. Není možné nebrat v potaz políčka těla, která hlavu hada následují, jinak bychom s každým simulovaným tahem trackfindingu "ztratili" jeden segment těla, který se vytvoří tam, kde byla v minulém tahu hlava.

Abych řekl pravdu, věřím tomu, že bych to nějak uplácat dokázal, ačkoliv nároky scriptu by nejspíš nebyly ideální. Problém je v tom, že je celkem jasné, že bych znovu objevoval kolo. Neví někdo, jak přesně na to? Metoda by měla logicky dojít k následujícímu výsledku:

[Mem]

Vzhledem k tomu, že ten had se bude hýbat, mi přijde jako nejjednodušší řešení (ale rozhodně ne optimální) odsimulovat pohyb na tahy formou stromu. Jsou sice až 3 možnosti pohybu v jednom tahu, ale i pokud se ti nepovede odsekávat některé větve, tak to je na 10 tahů necelých 60 tisíc listů, a to se imho dá v pohodě projít... A naprogramovat je to triviální a máš jistotu, že najdeš správné řešení

[Witiko]

[Mem]

[Witiko]

[Weny Sky]

Rekl bych, ze se na problem divas ze spatneho uhlu. Co tak generovat jidlo do patricne vzdalenosti? Tedy prohledavani do sirky a v urcite vzdalenosti vybrat uzly a nahodne z nich vybrat jeden.

Jinak puvodni problem by sel vyresit klidne A*, kdy by si kazdy uzel uchovaval informaci o sve hloubce. Startovni by mel hloubku 0. Tri nove vznikle hloubku 1, z tech by vychazely uzly s hlubkou 2 ... Pak by si hada chapal jako prekazku v pripade, ze telo hada ma cislo vetsi nez je hloubka aktualniho uzlu, v pripade, ze by byl ocislovan od ocasu smerem k hlave.

[Mem]

Ten první wenyho nápad zní dobře

U toho druhého si nejsem jistý, jestli je schopen podchytit i případ, kdy stejným políčkem může had projet v různou dobu (na základě předchozích tahů), nebo nedejbože vícekrát.. a případně, jestli to něčemu vadí

[Witiko]

[Weny Sky]

Jinak metody po kterych patras se obecne oznacuji spis pathfinding nez trackfinding, to jen aby si treba na googlu nasel nejake relevantni odkazy

No a ted k veci. Kdyz se vam nelibi navrh s A*, ktery je IMHO pro prostredi bez jinych prekazek dostacujici, tak mam jeste jeden navrh:
- cislovat policka jako delka hada + hlubka prohledavani
- pruchod je mozny kdyz je vyraz "aktualni hodnota uzlu - delka hada" vetsi nez policko na ktere chce vstoupit
- na prohledavani pouzit iterativni prohledavani do hloubky

[Witiko]

[Witiko]

Mám ještě jeden dotaz k tématu a sice výpočet maximální možné hloubky vyhledávání podle algoritmu hvězdičky (v našem případě pluska) na 2D poli s danými rozměry. Osobně bych si myslel, že maximální možná hloubka je například na herním poli 8 x 8 takováto:


38 při neprůchozích stěnách


18 při průchozích stěnách

Pro výpočet pro libovolné rozměry herního pole používám následující kód (schematizováno):

Při neprůchozích stěnách

[Weny Sky]

Zvyk pri psani algoritmu je takovy, ze je algoritmus, pokud je to mozne, co nejvice obecny . Proto mi zavadeni nejakych konstant hloubky neprijde zrovna jako stastne reseni. Ani si nejak nedokazu predstavit, kde v algoritmu A* jde neco takoveho pouzit, aby se jednalo o efektivni implementaci.

[Witiko]

[Weny Sky]

Jenze ty zadnou specifickou potrebu nemas, ty dostanes horsi cas a vysledky prave tehdy, pokud se budes snazit vymyslet nejaka vylepseni. Neber to nejak spatne, je to proste muj nazor.

Ten algoritmus je pro tve potreby dostatecne optimalizovany a vhodny. Stejne tak proflaknuta heuristika F = G + H.

Zamer se na jeho spravnou implementaci a az te bude brzdit, tak se zacni zabyvat nejakou silenou optimalizaci

[satik]

jen mala oprava, pri pruchozich stenach se da na uvedenem obrazku najit i kratsi cesta, o dve policka:




a da se urcite najit i bludiste, kde nejkratsi cesta bude delsi, napr. v bludisti, kde se da prochazet stenami takto:


(EDIT: v tomhle pripade by se dala vymyslet i jeste delsi cesta)


(v bludisti s nepruchozimi stenami pak analogicky)