Help : A* algorythm

[ArtBlink]

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?

[djrikki]

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?

[ArtBlink]

Hello,

A* is search algorythm, it use in pathfinding

you can see what is it here :

http://en.wikipedia.org/wiki/A*_search_algorithm

[Tarzin]

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!

[ArtBlink]

Yes, it's for match it

[jalih]

Here you are:

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

If you need diagonal movement, it should be quite easy to add. Have fun!

[jalih]

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!

[jalih]

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

[ArtBlink]

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

[Tarzin]

@jalih
Very amazing!

Thank you so much!