algorithm
En * sökvägsalgoritm

Introduktion

Enkelt exempel på A * Pathfinding: En labyrint utan hinder

Låt oss säga att vi har följande fyra med fyra rutnät:

Låt oss anta att det här är en labyrint . Det finns dock inga väggar / hinder. Vi har bara en startpunkt (det gröna torget) och en slutpunkt (den röda fyrkanten). Låt oss också anta att vi inte kan röra oss diagonalt för att komma från grönt till rött. Så från det gröna torget, låt oss se vilka rutor vi kan flytta till och markera dem med blått:

För att välja vilken kvadrat som ska flyttas till nästa måste vi ta hänsyn till 2 heuristik:

1. "G" -värdet - Det är så långt bort denna nod är från den gröna fyrkanten.
2. Värdet "h" - Det är så långt bort denna nod är från den röda fyrkanten.
3. Värdet "f" - Detta är summan av "g" -värdet och "h" -värdet. Detta är det sista numret som säger till vilken nod vi ska flytta till.

För att beräkna dessa heuristik är detta formeln vi kommer att använda: distance = abs(from.x - to.x) + abs(from.y - to.y)

Detta kallas formeln "Manhattan Distance" .

Låt oss beräkna "g" -värdet för den blå fyrkanten omedelbart till vänster om den gröna fyrkanten: abs(3 - 2) + abs(2 - 2) = 1

Bra! Vi har värdet: 1. Nu, låt oss försöka beräkna "h" -värdet: abs(2 - 0) + abs(2 - 0) = 4

Perfekt. Låt oss nu få "f" -värdet: 1 + 4 = 5

Så det slutliga värdet för denna nod är "5".

Låt oss göra samma sak för alla andra blå rutor. Det stora siffran i mitten av varje kvadrat är "f" -värdet, medan siffran uppe till vänster är "g" -värdet och siffran uppe till höger är "h" -värdet:

Vi har beräknat g-, h- och f-värdena för alla blå noder. Vad väljer vi nu?

Vilken som helst har det lägsta f-värdet.

Men i det här fallet har vi två noder med samma f-värde, 5. Hur väljer vi mellan dem?

Välj helt enkelt antingen en slumpmässig eller ställ in en prioritetsuppsättning. Jag föredrar vanligtvis att ha en prioritering så: "Höger> Upp> Ner> Vänster"

En av noderna med f-värdet 5 tar oss i "Ned" -riktningen, och den andra tar oss "Vänster". Eftersom Down har högre prioritet än vänster väljer vi torget som tar oss "Down".

Jag markerar nu de noder som vi beräknade heuristiken för, men flyttade inte till, som orange och den nod som vi valde som cyan:

Okej, låt oss nu beräkna samma heuristik för noderna kring cyannoden:

Återigen väljer vi noden som går ner från cyannoden, eftersom alla alternativ har samma f-värde:

Låt oss beräkna heuristiken för den enda granne som cyanoden har:

Okej, eftersom vi kommer att följa samma mönster som vi har följt:

Låt oss beräkna heuristiken för nodens granne ännu en gång:

Låt oss flytta dit:

Slutligen kan vi se att vi har ett vinnande torg bredvid oss, så vi flyttar dit och vi är klara.