Hello all,
I try since 1 month to create this A star algo with hollywood, i can't make it because it's too difficult, i have C source code and Python source code but it don't work.
In this forum, someone have made this algo in hollywood? or try to make it?
Help : A* algorythm
Re: Help : A* algorythm
Hi Art,
I think you may have better luck if you ask more clearly what algorithm you are trying to create?
What is an A* algorithm?
I think you may have better luck if you ask more clearly what algorithm you are trying to create?
What is an A* algorithm?
Evolve - Rapid GUI Development tool for MUI Royale and RapaGUI
http://myevolve.wordpress.com
http://myevolve.wordpress.com
Re: Help : A* algorythm
Hello,
A* is search algorythm, it use in pathfinding
you can see what is it here :
http://en.wikipedia.org/wiki/A*_search_algorithm
A* is search algorythm, it use in pathfinding
you can see what is it here :
http://en.wikipedia.org/wiki/A*_search_algorithm
Re: Help : A* algorythm
Artblink, is it for Match It! ? (help function and pathfinding between two tiles)
As you can see, it's no so easy!
Keep the faith!
As you can see, it's no so easy!
Keep the faith!
A500 / A600 / A1200 / SAM440
WinUAE OS3.9 (AmiKit) / OS4.1FE (FlowerPot)
---
https://twitter.com/TarzinCDK
WinUAE OS3.9 (AmiKit) / OS4.1FE (FlowerPot)
---
https://twitter.com/TarzinCDK
Re: Help : A* algorythm
Yes, it's for match it
Re: Help : A* algorythm
Here you are:
If you need diagonal movement, it should be quite easy to add. Have fun!
Code: Select all
; Hollywood port of the
;
; A* algorithm For LUA
; Ported To LUA by Altair
; 21 septembre 2006
;
;
; Ported to Hollywood by jalih, it took 20 mins and two beers.
;
; Bugs are mine naturally.
;
;
Function CalcMoves(mapmat, px, py, tx, ty)
Local openlist = {}
Local closedlist = {}
Local listk = 0
Local closedk = -1
Local tempH = Abs(px - tx) + Abs(py - ty)
Local tempG = 0
Local xsize = ListItems(mapmat[0]) - 1
Local ysize = ListItems(mapmat) - 1
Local curbase = {}
Local basis = 0
InsertItem(openlist, { x = px, y = py, g = 0, h = tempH, f = 0 + tempH, par = 0 } )
While listk > -1
Local lowestF = openlist[listk].f
basis = listk
For Local k = listk To 0 Step -1
If openlist[k].f < lowestF
lowestF = openlist[k].f
basis = k
EndIf
Next
closedk = closedk + 1
InsertItem(closedlist, openlist[basis], closedk)
curbase = closedlist[closedk]
Local rightOK = True
Local leftOK = True
Local downOK = True
Local upOK = True
If closedk > -1
For k = 0 To closedk
If closedlist[k].x = curbase.x + 1 And closedlist[k].y = curbase.y Then rightOK = False
If closedlist[k].x = curbase.x - 1 And closedlist[k].y = curbase.y Then leftOK = False
If closedlist[k].x = curbase.x And closedlist[k].y = curbase.y + 1 Then downOK = False
If closedlist[k].x = curbase.x And closedlist[k].y = curbase.y - 1 Then upOK = False
Next
EndIf
If curbase.x + 1 > xsize Then rightOK = False
If curbase.x - 1 < 0 Then leftOK = False
If curbase.y + 1 > ysize Then downOK = False
If curbase.y - 1 < 0 Then upOK = False
If curbase.x + 1 <= xsize And mapmat[curbase.y][curbase.x + 1] <> 0 Then rightOK = False
If curbase.x - 1 >= 0 And mapmat[curbase.y][curbase.x - 1] <> 0 Then leftOK = False
If curbase.y + 1 <= ysize And mapmat[curbase.y + 1][curbase.x] <> 0 Then downOK = False
If curbase.y - 1 >= 0 And mapmat[curbase.y - 1][curbase.x] <> 0 Then upOK = False
tempG = curbase.g + 1
For Local k = 1 To listk
If rightOK And openlist[k].x = curbase.x + 1 And openlist[k].y = curbase.y And openlist[k].g > tempG
tempH = Abs((curbase.x + 1) - tx) + Abs(curbase.y - ty)
InsertItem(openlist, {x = curbase.x + 1, y = curbase.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk}, k)
rightOK = False
EndIf
If leftOK And openlist[k].x = curbase.x - 1 And openlist[k].y = curbase.y And openlist[k].g > tempG
tempH = Abs((curbase.x - 1) - tx) + Abs(curbase.y - ty)
InsertItem(openlist, {x = curbase.x - 1, y = curbase.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk}, k)
leftOK = False
EndIf
If downOK And openlist[k].x = curbase.x And openlist[k].y = curbase.y + 1 And openlist[k].g > tempG
tempH = Abs(curbase.x - tx) + Abs((curbase.y + 1) - ty)
InsertItem(openlist, {x = curbase.x, y = curbase.y + 1, g = tempG, h = tempH, f = tempG + tempH, par = closedk}, k)
downOK = False
EndIf
If upOK And openlist[k].x = curbase.x And openlist[k].y = curbase.y - 1 And openlist[k].g > tempG
tempH = Abs(curbase.x - tx) + Abs((curbase.y - 1) - ty)
InsertItem(openlist, {x = curbase.x, y = curbase.y - 1, g = tempG, h = tempH, f = tempG + tempH, par = closedk}, k)
upOK = False
EndIf
Next
If rightOK
listk = listk + 1
tempH = Abs((curbase.x + 1) - tx) + Abs(curbase.y - ty)
InsertItem(openlist, {x = curbase.x + 1, y = curbase.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk }, listk)
EndIf
If leftOK
listk = listk + 1
tempH = Abs((curbase.x - 1) - tx) + Abs(curbase.y - ty)
InsertItem(openlist, {x = curbase.x - 1, y = curbase.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk }, listk)
EndIf
If downOK
listk = listk + 1
tempH = Abs(curbase.x - tx) + Abs((curbase.y + 1)- ty)
InsertItem(openlist, {x = curbase.x, y = curbase.y + 1, g = tempG, h = tempH, f = tempG + tempH, par = closedk }, listk)
EndIf
If upOK
listk = listk + 1
tempH = Abs(curbase.x - tx) + Abs((curbase.y - 1)- ty)
InsertItem(openlist, {x = curbase.x, y = curbase.y - 1, g = tempG, h = tempH, f = tempG + tempH, par = closedk }, listk)
EndIf
RemoveItem(openlist, basis)
listk = listk - 1
If closedlist[closedk].x = tx And closedlist[closedk].y = ty Then Return(closedlist)
Wend
Return(Nil)
EndFunction
Function CalcPath(closedlist)
If closedlist = Nil Then Return(Nil)
Local path = {}
Local pathIndex = {}
Local last = ListItems(closedlist) - 1
InsertItem(pathIndex, last, 0)
Local i = 0
While pathIndex[i] > 0
i = i + 1
InsertItem(pathIndex, closedlist[pathIndex[i - 1]].par, i)
Wend
For Local n = ListItems(pathIndex) - 1 To 0 Step -1
InsertItem(path, { x = closedlist[pathIndex[n]].x, y = closedlist[pathIndex[n]].y })
Next
closedlist = Nil
Return(path)
EndFunction
map = {}
map[0] = { 0, 1, 0, 0, 0 }
map[1] = { 0, 1, 0, 0, 0 }
map[2] = { 0, 1, 0, 0, 0 }
map[3] = { 0, 1, 0, 1, 0 }
map[4] = { 0, 0, 0, 1, 0 }
moves = CalcMoves(map, 0, 0, 4, 4)
path = CalcPath(moves)
If path <> Nil
For i = 0 To ListItems(path) - 1
DebugPrint("move:", "(", path[i].x, ",", path[i].y, ")")
Next
Else
DebugPrint("Sorry, no path to target")
EndIf
Re: Help : A* algorythm
I made an small example for you to play with and experiment.
There is a lot of room for an improvement. For an example, you can add diagonal movement (it should be a little more costly than horizontal and vertical movement), also different tile types could be added with different costs.
Windows path finding demo
AmigaOS 4 path finding demo
source for path finding demo
In demo:
-Left mouse button adds or removes obstacles.
-Middle mouse button sets start location.
-Right mouse button sets goal location.
Like always, have fun!
There is a lot of room for an improvement. For an example, you can add diagonal movement (it should be a little more costly than horizontal and vertical movement), also different tile types could be added with different costs.
Windows path finding demo
AmigaOS 4 path finding demo
source for path finding demo
In demo:
-Left mouse button adds or removes obstacles.
-Middle mouse button sets start location.
-Right mouse button sets goal location.
Like always, have fun!
Re: Help : A* algorythm
There seems to be some bug in path finding. In certain conditions path is not found, even if it does exist. It seems to be somewhere, how it handles g ( g = distance travelled). Currently commenting line: "tempG = curbase.g + 1" out from demo code makes it always find a path, if it exist.
I will have a closer look at this....
I will have a closer look at this....
Re: Help : A* algorythm
Excellent friend.
I try to adapt it and i can give later a modified code
Thanks a lot
I think you can make a lot a super code in hollywood, i think we can make a lot of things
I try to adapt it and i can give later a modified code
Thanks a lot
I think you can make a lot a super code in hollywood, i think we can make a lot of things
Re: Help : A* algorythm
@jalih
Very amazing!
Thank you so much!
Very amazing!
Thank you so much!
A500 / A600 / A1200 / SAM440
WinUAE OS3.9 (AmiKit) / OS4.1FE (FlowerPot)
---
https://twitter.com/TarzinCDK
WinUAE OS3.9 (AmiKit) / OS4.1FE (FlowerPot)
---
https://twitter.com/TarzinCDK