Căutarea unei căi de la punctul A la punctul B este una dintre cele mai comune sarcini în dezvoltarea jocurilor. Pentru a rezolva această problemă, există mulți algoritmi, dar cel mai frecvent utilizat este A * (A stea). Postul de astăzi este dedicat lui.
- Două liste de vârfuri sunt create - în așteptare și deja luate în considerare. În așteptare, se adaugă un punct de început, lista examinată este încă goală.
- Pentru fiecare punct, calculați F = G + H. G este distanța de la început până la punct, H este distanța aproximativă de la punctul la țintă. Voi vorbi mai târziu despre calculul acestei cantități. De asemenea, fiecare punct stochează o referință la punctul din care a venit.
- Din lista de puncte pentru examinare, este aleasă punctul cu cel mai mic F. Indicați-l cu X.
- Dacă X este ținta, atunci am găsit traseul.
- Transferăm X din lista de așteptare în lista considerată deja.
- Pentru fiecare dintre punctele adiacente lui X (vom desemna acest punct vecin Y), facem urmatoarele:
- Dacă Y este deja în considerare - săriți-l.
- Dacă Y nu este încă pe lista de așteptare, adăugați-l acolo, amintiți-vă referința la X și calculând Y.G (aceasta este distanța X.G + de la X la Y) și Y.H.
- Dacă Y este în listă pentru examinare, verificăm dacă X.G + este distanța de la X la Y
- Dacă lista de puncte pentru examinare este goală și nu am atins scopul - ruta nu există.
Funcția unei estimări aproximative a distanței față de țintă.
Această funcție trebuie să îndeplinească mai multe condiții:
- Funcția nu supraestimă distanța până la țintă.
- Pentru această funcție de distanțe, inegalitatea triunghiului se păstrează. Voi explica în detaliu: să presupunem că avem trei puncte - A, B și C. Pentru căile A-B B-C și A-C, următoarea inegalitate trebuie să fie adevărată: A-B + B-C> = A-C.
Realizare.
Am implementat un algoritm pentru o hartă rectangulară formată din celule.
Mai întâi, creați o clasă de puncte:
Rămâne să adăugați câteva funcții de serviciu.
Prima dintre acestea este funcția de distanță de la X la Y:
Distanța dintre celulele vecine este întotdeauna 1.
Funcția unei estimări aproximative a distanței față de ținta:
Pentru a estima distanța, utilizez lungimea căii fără obstacole.
Obținerea unei liste de vecini pentru un punct:
Obținerea rutei. Traseul este reprezentat ca o listă de coordonate de puncte.
Pentru aceasta am păstrat referințele la punctul din care am venit.
Pentru a schimba algoritmul într-un alt mod de reprezentare a punctelor (de exemplu, un grafic al distanțelor dintre orașe), trebuie să redeschizați recepția vecinilor și calcularea distanțelor.
Iată ce sa întâmplat:
Apropo, patratele deja știu cum să meargă și să lupte :-)
Funcția unei estimări aproximative a distanței față de ținta:
1
2
3
4Private static int GetHeuristicPathLength (punct de la, punct la)
retur Math.Abs (de la X - to.X) + Math.Abs (de la Y - to Y);
>
eronată. aparent cu geometrie destul de rău. Cea mai mică cale este calea de-a lungul liniei
private static int GetHeuristicPathLength (punct de la, punct la)
var DeltaX = Math.Abs (de la X la X);
var DeltaY = Math.Abs (de la Y până la Y);
var Dist = Math.sqrt (DeltaX * DeltaX + DeltaY * DeltaY);
Și unde este codul sursă?