## Help : A* algorythm

### Help : A* algorythm

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?

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?

### 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