Hľadanie ciest na základe mriežky

V tomto tutoriáli vytvoríme simuláciu hľadania cesty na základe dvojrozmernej mriežky. To nám poskytne základnú predstavu o vytváraní aktivít hľadania ciest pre naše hry. Vizualizujeme mriežku pomocou prázdnych štvorcových objektov ako dlaždíc a okrúhleho objektu ako našej avatar, ktorý sa môže pohybovať po tejto oblasti mriežky na našu príkaz.

I. Nastavovanie objektov

Našom projekte použijeme iba štyri objekty. Naša zelená avatar, modrá dlaždica, biela prekážka a označenie mriežky na nastavenie a vizualizáciu našich dlaždíc.

Avatar

Naša avatar je prázdny objekt, ktorý má x a y škálu 50%. Nechajte jeho kolíziu nastavenú na okrúhly tvar, aby vyzeral ako ten na obrázku nižšie. Tento objekt bude mať tri preddefinované atribúty: na dlaždici, predchádzajúca dlaždica a cieľová dlaždica. Nastavte predvolené hodnoty týchto atribútov na nulu, aby nemali nulovú hodnotu, keď sa ich pokúsime získať neskôr.

Dlaždicový objekt

Vytvorte ďalší prázdny objekt, ktorý sa bude používať na vizualizáciu dlaždíc v našej mriežke. Jeho škála je tiež 50% a má iba jeden preddefinovaný atribút: na dlaždici. Nastavte aj túto hodnotu na nulu.

Prekážkový objekt

Vytvorte ďalší prázdny objekt, ktorý bude slúžiť ako prekážky v našej mriežke. Toto je biely prázdny objekt so škálou 40%. Naša avatar sa nebude môcť pohybovať na dlaždici, ktorá má na sebe prekážku.

Označenie mriežky

To je len označenie, ktoré bude mať správanie, ktoré umožni nastaviť a vizualizovať našu mriežku. Má preddefinované atribúty: štart x s hodnotou 4 a štart y s hodnotou 3. Tieto hodnoty sú odchýlky, ktoré sa použijú ako referencie pri spánku našich dlaždíc, aby sme správne umiestnili našu mriežku doprostred.

Atribúty avataru/dlaždíc:

Definujeme dlaždicu tu ako dvojrozmerné pole, ktoré bude mať x a y hodnotu na základe našej mriežky.

• na dlaždici - to je hodnota dlaždice, na ktorej sa náš objekt aktuálne nachádza v našej mriežke
• predchádzajúca dlaždica - dlaždica, ktorou predtým prešiel náš avatar
• cieľová dlaždica - dlaždica, na ktorú sa náš avatar presunie

II. Nastavovanie mriežky

Vnútri označenia mriežky je miesto, kde definujeme naše dvojrozmerné pole a spánok našich dlaždíc. Existujú dve hlavné kľúčové body v tomto objekte: nastavenie poľa a vizualizácia poľa. Poďme najprv urobiť nastavenie balíčka poľa.

Nastaviť pole - balík

Najprv vytvorte prázdne pole s názvom 'Mriežka'. Toto pole bude obsahovať naše dvojrozmerné pole. Budeme mať škatulu s názvom 'x počet riadkov', ktorá má hodnotu 24 a ďalšie prázdne pole s názvom 'y riadok', ktoré má 18 prázdnych hodnôt.

Prvé správanie v našom balíčku je slučka s počtom opakovaní 'x počet riadkov'. Na každý krok tejto slučky pridáme prázdny y riadok do poľa 'Mriežka'. Tým sa vytvorí pole v poli s rozmerom 24x18.

Všimnite si, že sme pripojili neaktívny komentár na začiatku nášho balíčka, aby sme znegovali automatické vykonanie tohto koreňového správania. Koreňové správanie je správanie, ktoré sa nespúšťa na základe žiadnej udalosti a umiestňuje sa otvorene do rozhrania.

Vizualizovať mriežku - balík

Hlavná vec, ktorú tu urobíme, je prechádzať na každú hodnotu nášho 'poľa mriežky' a spánkový objekt dlaždice. Takisto pridáme podmienku do našej slučky, ktorá umožní spánok bielej prekážky na vrchole objektu dlaždice.

Najprv získame počet prvkov v našom 'y riadkovom poli', hodnotu atribútu 'štart x' tohto objektu a 'štart y'.

Vytvoríme slučku, ktorá má počet opakovaní 'x počet riadkov' a na každý krok tejto slučky pridáme indexovú hodnotu tejto slučky a hodnotu atribútu 'štart x'. To vedie k absolútnej pozícii x, ktorú použijeme na umiestnenie našich spánkových dlaždíc neskôr. Ďalej je slučka 'y riadok', ktorá má počet opakovaní 'y počet riadkov'. Na každý krok tejto slučky pridáme indexovú hodnotu tejto slučky a hodnotu atribútu 'štart y', čo teraz vedie k absolútnej pozícii y.

Po pridaní hodnôt pod slučkou 'y riadok' je potrebné spánkovať modrý objekt. Nastavte počet aktívnych objektov na 999, pretože ich budeme potrebovať veľa pre našu mriežku, a tiež s dobou trvania 0. Potom premiestnite spánkový objekt na bod x s hodnotou z 'y riadkovej slučky' a bod y s hodnotou z 'y riadkovej slučky'.

Ďalej pridáme pole s 2 prázdnymi hodnotami s názvom 'Na dlaždici', ktoré budeme používať iba ako zástupný symbol poľa. Po premiestnení objektu dlaždice sa modifikujeme pole 'Na dlaždici', nahradíme jeho hodnotu na indexe 0 hodnotou 'x riadková slučka'. Potom pridáme ďalšiu úpravu poľa, ktorá nahradí hodnotu na indexe 1 hodnotou 'y riadkový index'. Tými sú x a y súradnice našej mriežky, ktoré bude objekt mať ako atribút 'na dlaždici'.

Teraz nastavte atribút spánkového objektu s dynamickým kľúčom, 'na dlaždici' a s hodnotou 'Na dlaždici - pole'.

Stále pod slučkou 'y riadok' je podmienka na spánok bielej prekážky. Budeme mať 2 z 5 šancí na vykonanie tohto balíčka, čo pridá k náhodnosti našej mriežky. Potom označíme hodnotu 1 do súradníc x a y v našej 'Mriežke', ktorá nám hovorí, že táto súradnica má spánkovú prekážku.

Najprv musíme získať náhodné číslo 1 až 5. Ak je toto číslo menšie ako alebo rovné 2, spánkováme prekážku. Nastavte jej počet aktívnych objektov na 999 a premiestnite ten objekt na rovnaký bod ako modrá dlaždica, ktorú sme spánkovali predtým, a tiež s dobou trvania 0.

Potom musíme uložiť informácie, že táto súradnica bola obsadená prekážkou, ak bola spánkovaná. Urobíme to označením tejto súradnice hodnotou 1. Najprv získajte hodnotu na indexe 'x riadková slučka' v 'Mriežke'. Táto hodnota nám dá pole 'y riadu'. Modifikujeme tento 'y riadok' nahradením jeho hodnoty na indexe 'y riadková slučka' hodnotou 1, čo je označená hodnota. Pretože táto úprava hodnoty platí iba pre túto hodnotu, a nie pre 'Mriežku' samotnú, stále musíme upravit pole 'Mriežka'. Nahradíme hodnotu na indexe 'x riadková slučka' v 'Mriežke' hodnotou 'uprav y riadok - pole'.

Akonáhle sa zrealizuje, mala by to vyzerať takto.

III. Na stlačenie dlaždice

Aby sme mohli interagovať s mriežkou, budeme potrebovať balíčkové správanie, kedykoľvek stlačíme modrú dlaždicu. Prvé stlačenie spôsobí objavenie sa našej avatar na mriežke, a všetky ďalšie stlačenia po tomto udalosti začnú jeho hľadanie cesty.

Vnútri modrého objektu je balík správania, ktorý má 3 hlavné body: resetovanie predchádzajúcej dlaždice našej avatar, nastavenie jeho na dlaždici/nastavenie cieľovej dlaždice, potom nastavenie farebnej animácie na vizualizáciu dotykovej udalosti na obrazovke.

Najprv musíme získať atribút 'na dlaždici' objektu dlaždice. Nastavte atribút 'predchádzajúca dlaždica' našej avatar na 0. Naša avatar sa nastaví, aby sa vyhla návratu do 'predchádzajúcej dlaždice', preto to všetko resetujeme.

Ďalej, vezmeme attribút 'na dlaždici' našej avatar. Prvá podmienka je, či je hodnota 'na dlaždici' rovná nule. To znamená, že ak avatar ešte neobjavil, to sa stane pravdou. Ak je to pravda, nastavíme atribút 'na dlaždici' jeho avatar s hodnotou atribútu 'na dlaždici' objektu dlaždice. Potom premiestnime polohu našej avatar tak, že získame polohu objektu dlaždice, pričom jeho x a y hodnoty nastavíme na tento bod s dobou trvania 0.

Ak nie je hodnota 'na dlaždici' rovná nule, nastavíme atribút 'cieľová dlaždica' našej avatar s hodnotou atribútu položky objektu dlaždice. To znamená, že naša avatar sa už nachádza na našej mriežke a potom môžeme vykonať balíček správania, 'nájsť cestu'. Tento balíček správania ešte nemáme, ale opravíme to neskôr, po vykonaní ďalšej časti tohto tutoriálu pre balíček 'nájsť cestu'.

Teraz, keď sme správne umiestnili našu avatar na mriežku, stačí len vizualizovať túto udalosť stlačenia. Najprv pridáme koreňové správanie 'získať farbu', aby sme získali jeho pôvodnú farbu. Potom po udalosti dotyku nastavíme farbu objektu dlaždice na čiernu s dobou trvania 0, potom nastavíme späť jeho farbu na pôvodnú hodnotu s dobou trvania 0.2.

Stlačenie modrej dlaždice by malo vyzerať takto.

IV. Spustiť balíček nájsť cestu

Pre túto poslednú časť nášho tutoriálu urobíme algoritmus, ktorý nám umožní nájsť najbližšiu dlaždicu, ktorú môže naša avatar zobrať, aby dosiahla svoj cieľ. Tento balík sa bude opakovať pre každý krok dlaždice, na ktorých sa avatar pohybuje na mriežke.

Nastavíme algoritmus do nášho objektu avatar, ktorý bude mať tri hlavné body: nájdenie susedných dlaždíc, nájdenie najbližšej susednej dlaždice a pohyb k tejto susednej dlaždici.

Nájdenie susedných dlaždíc

V tejto časti zhromaždíme všetky susedné dlaždice, ktorými sa avatar bude môcť pohybovať. Skontrolujeme štyri smerové susedné dlaždice a zistíme, či tie dlaždice majú na sebe prekážku alebo ak na nich predtým stúpal.

Najprv pridáme naše pole 'Susedné dlaždice'. Pole 'Smer' s 2 prázdnymi hodnotami, a štyri smerové polia, ktoré majú 2 hodnoty pre každé: S (0,1), J (0,-1), V (1,0), Z(-1,0).

Prvé správanie v našom balíčku je vyčistenie susedných dlaždíc. Pretože túto súpravu budeme opakovať, musíme mať naše zhromaždené 'susedné dlaždice' resetované každýkrát. Ďalšie štyri správania sú úpravy poľa 'Smer'. Štyrikrát nastavíme pole poľa 'Smer' so štyrmi smerovými poľami a potom vykonáme balík nižšie. Urobíme to s cieľom vytvoriť slučku s rôznymi hodnotami poľa 'Smer' každýkrát.

Teraz, keď máme smer, len musíme spojiť ich x a y hodnoty s atribútom 'na dlaždici' našej avatar. Potom získame našu cieľovú hodnotu v 'Mriežke', aby sme zistili, či bola táto dlaždica označená prekážkou.

'Smer x' je hodnota poľa 'Smer' na indexe 0, 'získať na dlaždici' x je hodnota 'získať na dlaždici' na indexe 0. 'Cieľ x' je súčet hodnôt 'smer x' a 'získať na dlaždici x'. Rovnaké je to s hodnotami y, ale s cieľovým indexom 1.

'Cieľová y riadok' je hodnota poľa 'Mriežka' na indexe 'Cieľ x'. A potom 'Cieľový index v y riadku' bude hodnota hodnoty poľa 'Cieľová y riadok' na indexe 'Cieľ y'. To je súradnica v našej mriežke, ktorá nám môže povedať, či bola označená prekážkou.

Ak je hodnota v 'Cieľový index v y riadku' 1, znamená to, že táto cieľová dlaždica bola označená ako blokovaná. Ale ak hodnota nie je rovná 1, môžeme pokračovať v našom balíčku.

Pretože naše Cieľové x a y splnilo podmienku, pridali sme nové prázdne pole dlaždíc s názvom 'Nová susedná dlaždica'. To uloží hodnoty Cieľ x a y ako pole dlaždice. Nastavíme hodnotu Cieľ x na index 0 'Nová susedná dlaždica' a Cieľ y na index 1.

Teraz získame atribút 'predchádzajúca dlaždica' našich avatar. Ak je 'predchádzajúca dlaždica' rovná 'nová susedná dlaždica', to by znamenalo, že nová dlaždica nebola predtým prechádzaná. Potom môžeme bezpečne pridať 'Novú susednú dlaždicu' do poľa 'Susedné dlaždice' pridaním. 'Predchádzajúcu dlaždicu' nastavíme neskôr, až sa avatar úspešne presunie na ďalšiu dlaždicu.

"Tento balík môžete rozšíriť vytvorením 8 smerových polí, čo umožní vašej avatar pohybovať sa aj v diagonálnych smeroch."

Nájdenie najbližšej susednej dlaždice

Teraz, keď sme zozbierali naše spoľahlivé susedné dlaždice, stačí nájsť susednú dlaždicu, ktorá je najbližšie k cieľovej dlaždici našej avatar. Urobíme výpočty pomocou vzorca vzdialenosti, ktorý je založený na x a y hodnotách našej cieľovej dlaždice a susedných dlaždíc.

V tomto balíku sú dva kľúčové body: inicializácia premenných na výpočty a výpočty vzdialeností dlaždíc vo vnútri slučky.

a. Inicializácia premenných

Najprv získame číslo prvkov v našich susedných dlaždiciach. Potom získame atribút 'cieľová dlaždica' našich avatar a získať jej x a y hodnoty. Pridáme 2 nové škatule, 'Min vzdialenosť' a 'Index cieľovej dlaždice'. Nastavíme počiatočnú hodnotu 'Min vzdialenosť' na 9999 a hodnotu 'Index cieľovej dlaždice' na 0. Minimálna vzdialenosť je nastavená na vysoké číslo, pretože potrebujeme najmenšiu vzdialenosť od začiatku. Index cieľovej dlaždice je náš referenčný index v poli 'Susedné dlaždice', ktorý má najmenšiu vzdialenosť k 'cieľovej dlaždici'.

Našim hlavným cieľom je získať index dlaždice vo vnútri nášho 'Susedné dlaždice', ktorý sa nachádza najbližšie k nášmu 'cieľovému dlaždice'.

b. Vypočítanie vzdialeností dlaždíc

V tomto balíku budeme robiť výpočet vo vnútri slučky, ktorú budeme robiť pre každú susednú dlaždicu. Slučka sa opakuje podľa 'počet susedných dlaždíc' a získame hodnotu dlaždice z poľa 'Susedné dlaždice' pomocou indexu tejto slučky.

Získame x a y hodnoty tejto susednej dlaždice a potom získame vzdialenosť medzi našou 'cieľovou dlaždicou' a 'susednou dlaždicou' pomocou tohto vzorca:

vzdialenosť = sqrt((x2 - x1)^2+(y2 - y1)^2)
x1 = Cieľ x
x2 = Susedná x
y1 = Cieľ y
y2 = Susedná y

Najprv odčítame ich x a y hodnoty, vynásobíme ich samými so získaním ich exponenciálnych hodnôt, sčítať tie hodnoty a potom odmocniť pridané hodnoty, aby sme získali hodnotu vzdialenosti.

Ako je hodnota 'Vzdialenosť' menšia ako hodnota škatule 'Min vzdialenosť', nastavíme hodnotu 'index cielovej dlaždice' na aktuálny index slučky, čo je index našej získanej dlaždice v 'Susedné dlaždice'. Taktiež nastavíme hodnotu škatule 'Min vzdialenosť' na hodnotu 'Vzdialenosť', aby sme mohli porovnávať s ďalšou dlaždicou našich slučiek.

Na konci slučky sme porovnali každú jednu z našich susedných dlaždíc a získali sme indexovú hodnotu susednej dlaždice, ktorá je najbližšie k našej 'cieľovej dlaždici'.

Pohyb k susednej dlaždici

V tomto poslednom balíku nášho tutoriálu presunieme našu avatar ku najbližšej susednej dlaždici a opakujeme celý balík 'Nájsť cestu', ak sme sa ešte nenapravili k našej 'cieľovej dlaždici'.

Prvou vecou je skontrolovať, či je náš 'počet susedných dlaždíc' väčší ako 0. To zaistí, že sa presunieme iba vtedy, ak sme získali aspoň spoľahlivú susednú dlaždicu.

Potom 'Získať najbližšiu dlaždicu' pomocou našej hodnoty 'Index cielovej dlaždice' z predchádzajúceho balíka, aby získali hodnotu poľa 'Susedné dlaždice'.

Aby sme získali presný bod, kam sa naša avatar má presunúť, potrebujeme x a y hodnoty dlaždice a tiež získať hodnoty atribútov 'štart x' a 'štart y' našich 'Označení mriežky'. Potom pridáme x hodnotu našej 'najbližšej dlaždice' a hodnotu 'štart x', a tiež rovnako k y hodnotám. Tieto pridané hodnoty sú naše cieľové x a y body, kde sa bude naša avatar pohybovať.

Predtým, ako sa presunieme k tomu bodu, nastavíme atribút 'predchádzajúca dlaždica' našej avatar hodnotou jej aktuálnej hodnoty 'na dlaždici'. Túto hodnotu 'na dlaždici' môžeme získať z predchádzajúcich balíčkov. Potom presunieme našu avatar na naše cieľové body, s dobou trvania 0.2.

Po dokončení správania 'Presunúť na bod' nastavíme atribút 'na dlaždici' našej avatar s hodnotou poľa 'Získať najbližšiu dlaždicu'. Ak nie je tento 'Získať najbližšiu dlaždicu' rovná našej 'cieľovej dlaždici', opäť vykonáme balík 'Nájsť cestu', čím znovu zopakujeme celý balík. Atribút hodnoty 'cieľovej dlaždice' môžeme získať z predchádzajúceho balíčka.

Stlačením ktorejkoľvek modrej dlaždice a po objavení našej avatar na mriežke sa vykoná balík 'Nájsť cestu'. To spustí pohyb avataru z dlaždice na dlaždicu.

Záver

V tomto tutoriáli sme sa naučili vytvoriť aktivitu hľadania cesty pomocou objektu a poľa, ktoré sme nazvali 'Mriežka', ktoré slúži na ukladanie informácií o tom, či je táto dlaždica obsadená alebo nie. Túto myšlienku môžete rozšíriť použitím id objektu ako informácie namiesto iba digitálneho čísla pre naše pole 'Mriežka'. To nám poskytne presnejšie informácie, ktoré môžeme použiť pri hľadaní cesty. Napríklad, môžeme získať atribúty tohto objektu id, aby sme vedeli, či je živý alebo nie, a či nám umožní stúpať na jeho dlaždici alebo nie.

Tento tutoriál slúžil iba ako základná myšlienka hľadania cesty. Jednou z nevýhod tohto prístupu je, že nenašiel najkratšiu cestu k cieľovej dlaždici a kontroluje iba aktuálne susedné dlaždice. To môže viesť k slučke pohybu, ktorá niekam nepríde.

Avšak, tento problém môžeme vyriešiť rozšírením nášho algoritmu hľadania ciest. Môžeme to urobiť opakovaním našich nájdených susedných dlaždíc, aby sme získali aj ich susedné dlaždice, až kým nenájdeme našu cieľovú dlaždicu. Každá nájdená najbližšia susedná dlaždica bude pridaná na zoznam. Aby sme predišli nekonečnej slučke, pridáme podmienku, že ak už bola táto susedná dlaždica skontrolovaná, nebude pridaná na náš zoznam. Taktiež pridajte maximálny limit na počet iterácií, aby sa predišlo nekonečnej slučke, ktorá je spôsobená cieľovou dlaždicou, ak je príliš ďaleko alebo nie je možné ju nájsť. Akonaďe sa nájde cieľová dlaždica, ukončíme iteráciu a začneme pohybovať avatar od dlaždice k dlaždici pomocou tohto zoznamu dlaždíc.