Hvis du er spiludvikler, har du måske altid ønsket at implementere A* som en karakter (eller fjende) pathfinding. Jeg ved, at jeg for et par år siden gjorde det, men med mit niveau af programmering på det tidspunkt havde jeg problemer med de aktuelle artikler derude. Jeg ønskede at skrive dette som en let introduktion med et klart kildekodeeksempel til A* pathfinding, så alle nemt kan samle det op og bruge det i deres spil.
Et vigtigt aspekt af A* er f = g + h. Variablerne f, g og h er i vores Node-klasse og bliver beregnet, hver gang vi opretter en ny node. Jeg vil hurtigt gennemgå, hvad disse variabler betyder.
- F er den samlede omkostning for knuden.
- G er afstanden mellem den aktuelle knude og startknuden.
- H er den heuristiske – estimerede afstand fra den aktuelle knude til slutknuden.
Lad os tage et kig på en hurtig grafik for at illustrere dette.
Awesome! Lad os sige, at node(0) er vores startposition, og node(19) er vores slutposition. Lad os også sige, at vores nuværende knude er på den røde firkant node(4).
G
G er afstanden mellem den nuværende knude og startknuden.
Hvis vi tæller tilbage kan vi se, at node(4) er 4 felter væk fra vores startknude.
Vi kan også sige, at G er 1 mere end vores moderknude (node(3)). Så i dette tilfælde for node(4) er currentNode.g = 4.
H
H er den heuristiske – estimerede afstand fra den aktuelle knude til slutknuden.
Så lad os beregne afstanden. Hvis vi kigger efter, vil vi se, at hvis vi går over 7 felter og 3 felter opad, har vi nået vores slutknudepunkt (node(19)).
Lad os anvende Pythagoras’ sætning! a² + b² = c². Når vi har anvendt denne, vil vi se, at currentNode.h = 7² + 3². Eller currentNode.h = 58.
Men skal vi ikke anvende kvadratroden på 58? Niks! Vi kan springe denne beregning over på hver enkelt knude og stadig få det samme resultat. Smart!
Med en heuristik skal vi sikre os, at vi rent faktisk kan beregne den. Det er også meget vigtigt, at heuristikken altid er en undervurdering af den samlede vej, da en overvurdering vil føre til, at A* søger efter gennemgående knudepunkter, som måske ikke er de “bedste” med hensyn til f værdi.
F
F er de samlede omkostninger for knudepunktet.
Så lad os lægge h og g sammen for at få de samlede omkostninger for vores knudepunkt. currentNode.f = currentNode.g + currentNode.h. Eller currentNode.f = 4+ 58. Eller currentNode.f = 62.
Tid til at bruge f = g + h
Okay, det var altså en masse arbejde. Nu med alt det arbejde, hvad skal jeg så bruge denne f-værdi til?
Med denne nye f-værdi kan vi se på alle vores knuder og sige: “Hej, er dette den bedste knude, jeg kan vælge at gå videre med lige nu?”. I stedet for at køre alle knuder igennem, kan vi vælge dem, der har den bedste chance for at føre os til vores mål.
Her er en grafik til at illustrere det. Øverst har vi Dijkstras algoritme, som søger uden denne f-værdi, og nederst har vi A*, som bruger denne f-værdi.
Dijkstras Algoritme
Så tager vi et kig på Dijkstras algoritme, ser vi, at den bare bliver ved med at søge. Den har ingen idé om, hvilken knude der er “bedst”, så den beregner stier for dem alle.
A*-algoritme
Med A* ser vi, at når vi kommer forbi forhindringen, prioriterer algoritmen den knude, der har den laveste f og den “bedste” chance for at nå frem til målet.