Căutare de drumuri pe bază de grid

În acest tutorial vom realiza o simulare a găsirii unei căi bazate pe un grid de matrice bidimensională. Aceasta ne va oferi idea de bază pentru a crea activități de găsire a căii pentru jocurile noastre. Vom vizualiza gridul folosind obiecte pătrate goale ca plăci și un obiect rotund ca avatarul nostru care poate să se miște în această zonă de grid la comanda noastră.

I. Configurarea obiectelor

Vom folosi doar patru obiecte în proiectul nostru. Avatarul nostru verde, o placă albastră, o barieră albă și eticheta gridului pentru configurarea și vizualizarea gridului nostru.

Avatar

Avatarul nostru este un obiect gol care are o scală de x și y de 50%. Setați coliziunea să aibă o formă rotundă astfel încât să arate ca cel din imaginea de mai jos. Acest obiect va avea trei atribute predefinite: pe placă, placa anterioară și placa țintă. Setați valorile implicite ale acestor atribute la zero pentru a nu avea o valoare nulă când vom încerca să le recuperăm mai târziu.

Obiect Placă

Creează un alt obiect gol care va fi folosit pentru a vizualiza plăcile din gridul nostru. Scalarea sa este de asemenea 50% și are un singur atribut predefinit: pe placă. Setați, de asemenea, această valoare la zero.

Obiect Barieră

Creează un alt obiect gol care va servi ca barieră în gridul nostru. Acesta este un obiect gol alb cu o scală de 40%. Avatarul nostru nu va putea traversa o placă care are o barieră deasupra.

Eticheta Grid

Aceasta este doar o eticheta care va avea comportamentele care vor permite configurarea și vizualizarea gridului nostru. Are atribute predefinite: start x cu o valoare de 4 și start y cu o valoare de 3. Aceste valori sunt offseturi care vor fi folosite ca referințe atunci când vom crea plăcile noastre pentru a poziționa gridul nostru ordonat în centru.

Atribute predefinite Avatar/Placă:

Definim o placă aici ca un array de dimensiune 2 care va avea o valoare x și y bazată pe gridul nostru.

• pe placă - aceasta este valoarea plăcii pe care obiectul nostru se află în prezent în gridul nostru
• placa anterioară - o placă care a fost traversată anterior de avatarul nostru
• placa țintă - placa pe care avatarul nostru va merge

II. Configurarea gridului

În interiorul etichetei gridului este locul unde vom defini arrayul nostru 2D și generarea gridului nostru. Există 2 puncte cheie principale în acest obiect: configurarea arrayului și vizualizarea arrayului. Să facem mai întâi pachetul de setare a arrayului.

Setați arrayul - pachet

Primul lucru este să creezi un array gol numit 'Grid'. Acest array va conține arrayul nostru bidimensional. Vor fi un container de cutie numit 'numărul de linii x' care are o valoare de 24 și un alt array gol numit 'linie y' care are 18 valori goale.

Primul comportament din pachetul nostru este o buclă cu un număr de repetări de 'numărul de linii x'. Pentru fiecare pas al acestei bucle, vom adăuga o linie y goală în arrayul 'Grid'. Aceasta va crea un array în interiorul unui array cu o dimensiune de 24x18.

Observați că am conectat un comentariu inactiv la începutul pachetului nostru pentru a negata executarea automată a acestui comportament rădăcină. Un comportament rădăcină este un comportament care nu se declanșează pe baza niciunui eveniment și este plasat deschis în interfață.

Vizualizați gridul - pachet

Ceea ce vom face aici este să traversăm fiecare valoare a arrayului nostru 'Grid' și să generăm un obiect de tip placă. Vom adăuga de asemenea o condiție în bucla noastră care va permite generarea unei bariere albe deasupra obiectului de tip placă.

Primul lucru este să obținem numărul de elemente din arrayul nostru 'linie y', valoarea atributului 'start x' a acestui obiect și 'start y'.

Creează o buclă care are un număr de repetări de 'numărul de linii x' și pentru fiecare pas al acestei bucle, vom adăuga valoarea indexului acelei bucle și valoarea atributului 'start x'. Aceasta va duce la o poziție x absolută pe care o vom folosi pentru a poziționa plăcile generate mai târziu. Următoarea este bucla 'linie y' care are un număr de repetări de 'numărul de linii y'. Pentru fiecare pas al acestei bucle, vom adăuga valoarea indexului acelei bucle și valoarea atributului 'start y', ceea ce acum va duce la poziția y absolută.

După adăugarea valorilor sub bucla 'linie y' este să generăm obiectul albastru. Setează numărul de obiecte active la 999 pentru că vom avea nevoie de multe dintre ele pentru gridul nostru, și de asemenea cu o durată de 0. Apoi mutați obiectul generat la un punct x cu o valoare din adăugarea valorilor din bucla x și punctul y cu valoarea din adăugarea valorilor din bucla y.

Următorul pas este să adăugați un array cu 2 valori goale numit 'Pe placă' pe care îl vom folosi doar ca un loc de rezervă pentru array. După ce am mutat obiectul de tip placă, modificăm arrayul 'Pe placă' înlocuind valoarea sa de la indexul 0 cu valoarea buclei x. Apoi adăugăm o altă modificare a arrayului care înlocuiește valoarea de la indexul 1 cu indexul buclei y. Acestea sunt coordonatele x și y ale gridului nostru pe care obiectul le va avea ca atribut 'pe placă'.

Acum, setați atributul obiectului generat cu o cheie dinamică, 'pe placă', și cu o valoare de 'Array Pe placă'.

Încă sub bucla linie y, este condiția de generare a barierei albe. Vom avea o șansă de 2 din 5 de a executa acest pachet care va adăuga la randomizarea gridului nostru. Apoi vom marca o valoare de 1 pentru coordonatele x și y în arrayul nostru 'Grid' care ne spune că acel punct a fost ocupat de o barieră.

Primul lucru este să avem un număr aleatoriu de la 1 la 5. Dacă acel număr este mai mic sau egal cu 2, vom genera bariera. Setează-i numărul de obiecte active la 999 și mutați acel obiect la același punct ca și placa albastră pe care am generat-o mai devreme, și de asemenea cu o durată de 0.

Următoarea etapă este să stocăm informația că această coordonată a fost ocupată de o barieră, dacă a fost generată. Facem acest lucru marcând acea coordonată cu valoarea 1. Primul lucru este să obținem valoarea de la indexul 'bucla linii x' din arrayul 'Grid'. Această valoare ne va oferi un array de o 'linie y'. Vom modifica această 'linie y' înlocuind valoarea sa de la indexul 'bucla y' cu valoarea 1, care este valoarea marcată. Deoarece această modificare a valorii se aplică doar acelei valori și nu la 'Grid', trebuie să modificăm și arrayul 'Grid'. Să înlocuim valoarea de la indexul 'bucla linii x' din arrayul 'Grid' cu valoarea 'modifica linia y - array'.

Odată ce a fost jucat, ar trebui să rezulte într-o formă de acest fel.

III. Când se apasă pe Placă

Pentru a putea interacționa cu gridul, va trebui să avem un comportament de pachet de fiecare dată când apăsăm o placă albastră. Prima apăsare va duce la apariția avatarului nostru în gridul nostru, și orice apăsare succesivă după acel eveniment va începe căutarea căii sale.

În interiorul obiectului albastru este un pachet de comportament care are 3 puncte principale: resetarea plăcii anterioare a avatarului nostru, setarea plăcii sale/setarea plăcii sale țintă, apoi setarea unei animații de culoare pentru a vizualiza evenimentul de atingere pe ecran.

Primul pas este să obținem atributul 'pe placă' al obiectului de tip placă. Setați atributul 'placa anterioară' al avatarului nostru la 0. Avatarul nostru va fi setat astfel încât să evite să revină la o 'placă anterioară', de aceea resetăm 'placa anterioară' la fiecare apăsare a plăcii.

Următorul pas este să obținem atributul 'pe placă' al avatarului nostru. Prima condiție dacă este ca valoarea 'pe placă' să fie egală cu zero. Acest lucru înseamnă că dacă avatarul nu a apărut încă, atunci acest lucru va rezulta adevărat. Dacă este adevărat, atunci setăm atributul său 'pe placă' cu o valoare a atributului 'pe placă' al obiectului de tip placă. Apoi mutăm poziția avatarului nostru obținând poziția obiectului de tip placă, indicând valorile sale x și y la acel punct cu o durată de 0.

Dacă valoarea 'pe placă' nu este egală cu zero, vom seta atributul 'placa țintă' al avatarului nostru la valoarea atributului 'pe placă' al obiectului de tip placă. Aceasta înseamnă că avatarul nostru este deja în gridul nostru, și apoi putem executa pachetul de comportamente 'găsește calea'. Nu avem încă acest comportament, dar vom repara asta din nou după ce vom face partea ulterioară a acestui tutorial pentru pachetul 'găsește calea'.

Acum că am setat corect avatarul nostru în gridul nostru, trebuie doar să vizualizăm acest eveniment de apăsare. Primul pas este să avem un comportament de rădăcină 'obține culoarea' pentru a obține culoarea sa originală. Apoi, după evenimentul de apăsare, vom seta culoarea obiectului de tip placă la negru cu o durată de 0, apoi vom seta culoarea sa înapoi din nou la valoarea sa originală cu o durată de 0.2.

Apăsând pe o placă albastră ar trebui să rezulte în acest lucru.

IV. Execută Pachetul Găsește Calea

Pentru ultima parte a tutorialului nostru, vom face algoritmul care ne permite să găsim cea mai apropiată placă pe care avatarul nostru o poate lua pentru a ajunge la destinația sa. Acest pachet va fi executat repetat pentru fiecare pas de placă pe care avatarul nostru se mișcă pe gridul nostru.

Vom seta algoritmul în interiorul obiectului nostru avatar și acest lucru va avea trei puncte principale: găsirea plăcilor adiacente, găsirea celei mai apropiate plăci adiacente și mișcarea către acea placă adiacente.

Găsirea plăcilor adiacente

În această parte, vom colecta toate plăcile adiacente la care avatarul nostru ar putea traversa. Vom verifica cele patru plăci adiacente direcționale și vom vedea dacă acele plăci au o barieră deasupra lor sau dacă au fost călcate anterior.

Primul pas este să adăugăm arrayul nostru 'Plăci adiacente'. Un array 'Direcție' cu 2 valori goale și cele patru arrayuri direcționale care au 2 valori pentru fiecare: N (0,1), S (0,-1), E (1,0), W( -1,0).

Primul comportament din pachetul nostru este să curățăm plăcile adiacente. Deoarece vom face acest pachet repetat, trebuie să avem plăcile adiacente colectate resetate de fiecare dată. Următoarele patru comportamente sunt modificări ale arrayului 'Direcție'. Setăm arrayul arrayului 'Direcție' de patru ori cu cele patru arrayuri direcționale, apoi executăm pachetul de mai jos. Facem acest lucru pentru a crea o buclă cu valori diferite ale arrayului 'Direcție' de fiecare dată.

Acum că avem direcția, trebuie doar să combinăm valorile lor x și y cu atributul 'pe placă' al avatarului nostru. Apoi vom putea obține valoarea țintă din arrayul 'Grid' pentru a ști dacă acea placă a fost marcată cu o barieră.

'Direcție x' este valoarea arrayului 'Direcție' la indexul 0, 'obține pe placă' x este valoarea din 'obține pe placă' la indexul 0. Valoarea țintă x este suma valorilor 'direcție x' și 'obține pe placă x'. La fel și pentru valorile y, dar cu un index țintă de 1.

'Linia țintă y' este valoarea arrayului 'Grid' la indexul 'Valoarea țintă x'. Apoi indexul țintă în linia y va fi valoarea arrayului 'Linia țintă y' la indexul 'Linia țintă y'. Aceasta este coordonata din gridul nostru care va putea să ne spună dacă a fost marcată cu o barieră.

Dacă valoarea din 'Indexul țintă în linia y' este 1, atunci acea placă țintă a fost marcată ca blocată. Dar dacă valoarea nu este egală cu 1, atunci putem continua în pachetul nostru.

Pentru că x și y valorile țintă au trecut condiția noastră, am adăugat un nou array gol numit 'Nouă placă adiacente'. Acesta va stoca valorile x și y ca un array de placă. Vom seta valoarea țintă x la indexul 0 al 'Nouă placă adiacente' și valoarea țintă y la indexul său 1.

Acum obțineți atributul 'placa anterioară' al avatarului nostru. Dacă 'placa anterioară' nu este egală cu 'noua placă adiacente', aceasta ar însemna că noua placă nu a fost traversată anterior. Atunci, putem adăuga cu siguranță 'Nouă placă adiacente' în arrayul 'Plăci adiacente' prin adăugarea acesteia. Vom seta valoarea 'placa anterioară' mai târziu, după ce am mutat cu succes avatarul nostru pe o altă placă.

"Poți extinde acest pachet făcând un array de 8 direcții care le permite avatarului tău să se miște în direcții diagonale."

Găsirea celei mai apropiate plăci adiacente

Acum că am colectat plăcile noastre adiacente de încredere, trebuie doar să obținem placa adiacentă care este cea mai apropiată de placa țintă a avatarului nostru. Vom face calculul folosind o formulă de distanță oferită de valorile x și y ale plăcii noastre țintă și plăcile adiacente.

Există două puncte cheie în acest pachet: inițializarea variabilelor pentru calcul și calcularea distanțelor plăcilor în interiorul unei bucle.

a. Inițializarea variabilelor

Primul pas este să obținem numărul de elemente din plăcile noastre adiacente. Apoi obținem atributul 'placa țintă' al avatarului nostru și să-i obținem valorile x și y. Vom adăuga 2 noi containere de tip cutie: 'Distanța Min' și 'Indexul Plăcii Țintă'. Setați valoarea inițială a 'Distanței Min' la 9999 și valoarea 'Indexului Plăcii Țintă' la 0. Distanța min este setată la un număr mare pentru că avem nevoie de cea mai mică distanță de la început. Indexul plăcii țintă este indexul nostru de referință în arrayul 'Plăci adiacente' care are cea mai mică distanță față de 'placa țintă'.

Obiectivul nostru principal aici este să obținem indexul plăcii din arrayul nostru 'Plăci adiacente' care este cea mai apropiată de 'placa țintă'.

b. Calcularea distanțelor plăcilor

În acest pachet, vom face calculul într-o buclă pe care o vom face pentru fiecare placă adiacente. Bucla se repetă prin 'numărul de plăci adiacente' și vom obține valoarea plăcii din arrayul 'Plăci adiacente' folosind indexul acelei bucle.

Obțineți valorile x și y ale acelei plăci adiacente și apoi vom obține distanța dintre 'placa țintă' și 'placa adiacente' folosind această formulă:

distanță = sqrt((x2 - x1)^2+(y2 - y1)^2)
x1 = Valoarea țintă x
x2 = Valoarea adiacentă x
y1 = Valoarea țintă y
y2 = Valoarea adiacentă y

Mai întâi scădem valorile lor x și y, le multiplicăm pentru a obține valorile lor exponențiale, adăugăm acele valori, și apoi extragem rădăcina pătrată a valorilor adăugate, pentru a obține valoarea distanței.

Dacă valoarea 'Distanță' este mai mică decât valoarea containerului 'Distanță Min', vom seta valoarea 'indexului plăcii țintă' la indexul curent al buclei, care este indexul plăcii obținut din arrayul 'Plăci adiacente'. De asemenea, setăm valoarea containerului 'Distanță Min' cu valoarea 'Distanță' pentru a o compara cu următoarea placă din bucle.

După terminarea buclei, am comparat fiecare dintre plăcile noastre adiacente și am obținut valoarea indexului plăcii adiacente care este cea mai apropiată de 'placa țintă'.

Mișcarea către placa adiacentă

În acest ultim pachet al tutorialului nostru, vom muta avatarul nostru către cea mai apropiată placă adiacentă și vom repeta întregul pachet 'Găsește Calea' dacă nu ne-am mutat deja în 'placa țintă'.

Primul lucru este să verificăm dacă 'Numărul de plăci adiacente' este mai mare decât 0. Acest lucru pentru a ne asigura că ne vom mișca doar dacă am obținut cel puțin o placă adiacentă de încredere.

Apoi 'Obține placa cea mai apropiată' folosind valoarea 'Indexului Plăcii Țintă' din pachetul anterior pentru a obține valoarea arrayului 'Plăci adiacente'.

Pentru a obține exact punctul în care avatarul nostru se va muta, vom avea nevoie de valorile plăcii x și y ale acelei plăci, și de asemenea obținem valorile atributului 'start x' și 'start y' al etichetei noastre 'Grid'. Apoi adăugăm valoarea x a 'plăcii celei mai apropiate' și valoarea 'start x', și de asemenea același lucru și pentru valorile y. Aceste valori adunate sunt punctele noastre țintă x și y unde avatarul nostru se va muta.

Înainta de a ne muta la acel punct, setăm 'placa anterioară' a avatarului nostru la valoarea sa curentă a atributului 'pe placă'. Putem obține această valoare 'pe placă' din pachetele anterioare. Apoi, mutăm avatarul nostru la punctele noastre țintă, cu o durată de 0.2.

După finalizarea comportamentului 'Mutare la punct', acum setăm valoarea atributului 'pe placă' al avatarului la valoarea arrayului 'Obține placa cea mai apropiată'. Dacă valoarea din arrayul 'Obține placa cea mai apropiată' nu este egală cu valoarea noastră țintă, atunci vom executa pachetul 'Găsește Calea', astfel revedem întregul pachet din nou. Valoarea atributului 'placa țintă' poate fi obținută din pachetul anterior.

Prin apăsarea oricărei plăci albastre, și după apariția avatarului nostru în grid, pachetul 'Găsește Calea' va fi executat. Acest lucru va declanșa mișcarea avatarului din placă în placă.

Concluzie

În acest tutorial, am învățat să facem o activitate de găsire a căii obiectului folosind un array pe care l-am numit 'Grid', care este folosit pentru a stoca informațiile dacă acea placă a fost ocupată sau nu. Poți extinde această idee, folosind id-uri de obiecte ca stocare a informațiilor în loc de doar un număr pentru arrayul 'Grid'. Acest lucru ne va oferi informații mai de încredere pe care le putem folosi atunci când facem găsirea căii. De exemplu, putem obține atributele acelei id de obiect pentru a ști dacă este vie sau nu, dacă ne va permite să pășim pe placa sa sau nu.

Acest tutorial a servit doar idee fundamentală din spatele găsirii căii. O neajunsă din aceasta este că nu creează cea mai scurtă cale posibilă către o placă țintă, și doar verifică plăcile adiacente curente. Acest lucru poate duce la un comportament de mișcare care nu ajunge nicăieri.

Cu toate acestea, aceasta poate fi rezolvată prin extinderea algoritmului nostru de căutare a căii. Putem face acest lucru iterând pe plăcile noastre adiacente obținute pentru a obține plăcile sale adiacente până când găsim placa noastră țintă. Fiecare placă adiacentă găsită va fi adăugată la o listă. Pentru a preveni o buclă infinită, adăugați o condiție că dacă acea placă adiacente a fost deja verificată, acea placă nu va fi adăugată la lista noastră. De asemenea, adăugați o limită maximă la numărul de iterații pentru a preveni o buclă infinită care este cauzată de placa țintă dacă este prea departe sau nu este posibil să fie găsită. Odată ce acea iterație găsește placa țintă, ieșim din iterație și începem să mutăm avatarul pe la plăci folosind lista de plăci.