Jäi vaivaamaan, kun en aikanaan saanut A*ia CB:lle, ja nyt kun sitä vielä joku kysyi niin en saanut unta ennen kuin kirjoitin sen. Eli epäselvää purkkaa, olkaa hyvät. (mutta se toimii, mwohoo)
Code: Select all
Dim map(39, 29, 5)
//constants for easier array handling
Const OPEN = 0'unused = 0, open = 1, closed = 2
Const G = 1
Const H = 2
Const MX = 3
Const MY = 4
Const STYLE = 5 //0=empty, 1=wall, 2=start, 3=goal, 4 = inroute
ClsColor 255, 255, 255
Cls
Color 0, 0, 0
While True
//reset
For i = 0 To 39
For j = 0 To 29
For p = 0 To 5
map(i,j,p)=0
Next p
Next j
Next i
//"editor"
While KeyHit(28) = 0
If MouseHit(1) Then
map(Int(MouseX()/10), Int(MouseY()/10), STYLE) = map(Int(MouseX()/10), Int(MouseY()/10), STYLE)+1
If map(Int(MouseX()/10), Int(MouseY()/10), STYLE) = 4 Then map(Int(MouseX()/10), Int(MouseY()/10), STYLE) = 0
EndIf
draw()
DrawScreen
Wend
//check that we find a start and a goal
startfound = 0:goalfound = 0
For i = 0 To 39
For j = 0 To 29
If map(i,j,STYLE) = 2 Then
startx = i
starty = j
If startfound = 1 Then MakeError "invalid map!"
startfound = 1
EndIf
If map(i,j,STYLE) = 3
goalx = i
goaly = j
If goalfound = 1 Then MakeError "invalid map!"
goalfound = 1
EndIf
Next j
Next i
If startfound = 0 Or goalfound = 0 Then MakeError "invalid map!"
curx = startx
cury = starty
map(curx, cury, MX) = curx
map(curx, cury, MY) = cury
found = 0
While found = 0
If curx<39 Then
If map(curx+1,cury,STYLE) <> 1 And map(curx+1, cury,OPEN) = 0 Then
map(curx+1, cury, OPEN) = 1
map(curx+1, cury, G) = map(curx, cury, G)+1
map(curx+1, cury, H) = Abs(curx+1-goalx)+Abs(goaly-cury)
map(curx+1, cury, MX) = curx
map(curx+1, cury, MY) = cury
Else
If map(curx+1, cury, OPEN) >0 Then
xm = map(curx+1, cury, MX)
ym = map(curx+1, cury, MY)
If (map(xm, ym, H)+map(xm, ym, G))>(map(curx, cury, H)+map(curx, cury, G)) Then
map(curx+1, cury, G) = map(curx, cury, G)+1
map(curx+1, cury, MX) = curx
map(curx+1, cury, MY) = cury
EndIf
EndIf
EndIf
EndIf
If cury<29 Then
If map(curx,cury+1,STYLE) <> 1 And map(curx, cury+1,OPEN) = 0 Then
map(curx, cury+1, OPEN) = 1
map(curx, cury+1, G) = map(curx, cury, G)+1
map(curx, cury+1, H) = Abs(curx-goalx)+Abs(cury+1-goaly)
map(curx, cury+1, MX) = curx
map(curx, cury+1, MY) = cury
Else
If map(curx, cury+1, OPEN) >0 Then
xm = map(curx, cury+1, MX)
ym = map(curx, cury+1, MY)
If (map(xm, ym, H)+map(xm, ym, G))>(map(curx, cury, H)+map(curx, cury, G)) Then
map(curx, cury+1, G) = map(curx, cury, G)+1
map(curx, cury+1, MX) = curx
map(curx, cury+1, MY) = cury
EndIf
EndIf
EndIf
EndIf
If cury>0 Then
If map(curx,cury-1,STYLE) <> 1 And map(curx, cury-1,OPEN) = 0 Then
map(curx, cury-1, OPEN) = 1
map(curx, cury-1, G) = map(curx, cury, G)+1
map(curx, cury-1, H) = Abs(curx-goalx)+Abs(cury-1-goaly)
map(curx, cury-1, MX) = curx
map(curx, cury-1, MY) = cury
Else
If map(curx, cury-1, OPEN) >0 Then
xm = map(curx, cury-1, MX)
ym = map(curx, cury-1, MY)
If (map(xm, ym, H)+map(xm, ym, G))>(map(curx, cury, H)+map(curx, cury, G)) Then
map(curx, cury-1, G) = map(curx, cury, G)+1
map(curx, cury-1, MX) = curx
map(curx, cury-1, MY) = cury
EndIf
EndIf
EndIf
EndIf
If curx>0 Then
If map(curx-1,cury,STYLE) <> 1 And map(curx-1, cury,OPEN) = 0 Then
map(curx-1, cury, OPEN) = 1
map(curx-1, cury, G) = map(curx, cury, G)+1
map(curx-1, cury, H) = (Abs((curx-1)-goalx)+Abs(cury-goaly))
map(curx-1, cury, MX) = curx
map(curx-1, cury, MY) = cury
Else
If map(curx-1, cury, OPEN) >0 Then
xm = map(curx-1, cury, MX)
ym = map(curx-1, cury, MY)
If (map(xm, ym, H)+map(xm, ym, G))>(map(curx, cury, H)+map(curx, cury, G)) Then
map(curx-1, cury, G) = map(curx, cury, G)+1
map(curx-1, cury, MX) = curx
map(curx-1, cury, MY) = cury
EndIf
EndIf
EndIf
EndIf
If ((curx = goalx) And (cury = goaly)) Then found = 1
map(curx, cury, OPEN) = 2
first_ = 1
For i = 0 To 39
For j = 0 To 29
If map(i,j,OPEN) = 1 And ((map(i, j, G) + map(i, j, H)<tempf) Or (first_=1))
tempf = map(i, j, G) + map(i, j, H)
curx = i
cury = j
first_ = 0
EndIf
Next j
Next i
Wend
curx = map(goalx, goaly, MX)
cury = map(goalx, goaly, MY)
While Not ( curx = startx And cury = starty )
map(curx, cury, STYLE) = 4
curx2 = map(curx, cury, MX)
cury2 = map(curx, cury, MY)
curx = curx2
cury = cury2
Wend
draw()
DrawScreen
WaitKey
ClearKeys
Wend
Function draw()
For x = 0 To 39
For y = 0 To 29
If map(x,y,STYLE) = 2 Then Color 0, 255, 0
If map(x,y,STYLE) = 3 Then Color 255, 0, 0
If map(x,y,STYLE) = 4 Then Color 0, 0, 255
If map(x,y,STYLE) Then Box x*10+1, y*10+1, 9, 9
Color 0, 0, 0
Line 0, y*10, 400, y*10
Next y
Line x*10, 0, x*10, 300
Next x
EndFunction
1. Ota nykyinen piste. (alussa vihreä starttiruutu)
2. Merkitse kaikki sen ympärillä olevat (en jaksanut vääntää diagonaalisia liikkeitä tähän, joten neljä suuntaa) "auki oleviksi". Laske matka niihin alkupisteestä (nykyisen matka + 1 ruutu, siis.). Laske vaakasuora matka niistä maaliin, pystysuora matka maaliin ja ynnää. Tämä on niin sanottu heuric-arvo, eli arvio jäljellä olevasta matkasta. Tämän voisi toki laskea hienomminkin, mutta tämäkin on ihan ok. Sitten asetetaan näiden pisteiden "äidiksi" nykyinen piste. Mikäli joku oli jo valmiiksi auki, tarkistetaan onko uusi reitti lyhyempi kuin vanha. Jos on, äitiä vaihdetaan.
3. Nyt menee jännäksi: verrataan kaikkien avoimien pisteiden F-arvoa (F=H+G, eli heuric + jo kuljettu) keskenään, ja asetetaan pieniarvoisin nykyiseksi pisteeksi.
4. Jos nykyinen piste on maali, ollaan perillä. Seuraamalla kaikkien solujen äidit maalista starttiin, saadaan kuljettu reitti.