Implementarea algoritmului de căutare a pe c #

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.







  1. 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ă.
  2. 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.
  3. Din lista de puncte pentru examinare, este aleasă punctul cu cel mai mic F. Indicați-l cu X.
  4. Dacă X este ținta, atunci am găsit traseul.
  5. Transferăm X din lista de așteptare în lista considerată deja.
  6. Pentru fiecare dintre punctele adiacente lui X (vom desemna acest punct vecin Y), facem urmatoarele:
  7. Dacă Y este deja în considerare - săriți-l.
  8. 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.
  9. Dacă Y este în listă pentru examinare, verificăm dacă X.G + este distanța de la X la Y
  10. 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:

Implementarea algoritmului de căutare a pe c #

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ă?







Articole similare

Pagina anterioară

Pagina următoare

Trimiteți-le prietenilor: