algorithm
A * Pathfinding-algoritme

Invoering

Eenvoudig voorbeeld van A * Pathfinding: een doolhof zonder obstakels

Laten we zeggen dat we het volgende 4 bij 4 raster hebben:

Laten we aannemen dat dit een doolhof is . Er zijn echter geen muren / obstakels. We hebben alleen een beginpunt (het groene vierkant) en een eindpunt (het rode vierkant). Laten we ook aannemen dat we niet diagonaal kunnen bewegen om van groen naar rood te gaan. Laten we dus vanaf het groene vierkant kijken naar welke vierkanten we kunnen gaan en deze blauw markeren:

Om te kiezen naar welk vierkant we moeten gaan, moeten we rekening houden met 2 heuristieken:

1. De "g" -waarde - Dit is hoe ver deze knoop van het groene vierkant verwijderd is.
2. De "h" -waarde - Dit is hoe ver deze knoop van het rode vierkant is.
3. De "f" -waarde - Dit is de som van de "g" -waarde en de "h" -waarde. Dit is het laatste nummer dat ons vertelt naar welk knooppunt we moeten gaan.

Om deze heuristieken te berekenen, is dit de formule die we zullen gebruiken: distance = abs(from.x - to.x) + abs(from.y - to.y)

Dit staat bekend als de "Manhattan Distance" -formule.

Laten we de "g" -waarde berekenen voor het blauwe vierkant direct links van het groene vierkant: abs(3 - 2) + abs(2 - 2) = 1

Super goed! We hebben de waarde: 1. Laten we nu proberen de "h" -waarde te berekenen: abs(2 - 0) + abs(2 - 0) = 4

Perfect. Laten we nu de "f" -waarde krijgen: 1 + 4 = 5

De uiteindelijke waarde voor dit knooppunt is dus "5".

Laten we hetzelfde doen voor alle andere blauwe vierkanten. Het grote getal in het midden van elk vierkant is de waarde "f", terwijl het getal linksboven de waarde "g" is en het getal rechtsboven de waarde "h":

We hebben de g-, h- en f-waarden berekend voor alle blauwe knooppunten. Welke kiezen we nu?

Welke heeft de laagste f-waarde.

In dit geval hebben we echter 2 knooppunten met dezelfde f-waarde, 5. Hoe kiezen we hiertussen?

Kies eenvoudig een willekeurige of stel een prioriteit in. Meestal heb ik liever zo'n prioriteit: "Rechts> Omhoog> Omlaag> Links"

Een van de knooppunten met de f-waarde van 5 neemt ons mee in de richting "Omlaag" en de andere brengt ons "Links". Omdat Down een hogere prioriteit heeft dan Left, kiezen we het vierkant dat ons "Down" brengt.

Ik markeer nu de knooppunten waarvoor we de heuristiek hebben berekend, maar niet zijn verplaatst naar, als oranje, en de knoop die we hebben gekozen als cyaan:

Oké, laten we nu dezelfde heuristieken berekenen voor de knooppunten rond de cyaanknoop:

Nogmaals, we kiezen het knooppunt dat omlaag gaat vanaf het cyaanknooppunt, omdat alle opties dezelfde f-waarde hebben:

Laten we de heuristieken berekenen voor de enige buurman die de cyaanknoop heeft:

Oké, omdat we hetzelfde patroon zullen volgen dat we hebben gevolgd:

Laten we nogmaals de heuristiek voor de buurman van de knoop berekenen:

Laten we daarheen gaan:

Eindelijk kunnen we zien dat we een winnend vierkant naast ons hebben, dus we gaan daarheen en we zijn klaar.