Help : A* algorythm

Discuss any general programming issues here
Post Reply
ArtBlink
Posts: 437
Joined: Mon Nov 01, 2010 10:37 am
Location: Albert - France
Contact:

Help : A* algorythm

Post by ArtBlink » Sat Jun 18, 2011 9:55 pm

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
Posts: 682
Joined: Wed Apr 06, 2011 12:26 am

Re: Help : A* algorythm

Post by djrikki » Sun Jun 19, 2011 12:48 am

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?
Evolve - Rapid GUI Development tool for MUI Royale and RapaGUI
http://myevolve.wordpress.com

ArtBlink
Posts: 437
Joined: Mon Nov 01, 2010 10:37 am
Location: Albert - France
Contact:

Re: Help : A* algorythm

Post by ArtBlink » Sun Jun 19, 2011 10:41 am

Hello,

A* is search algorythm, it use in pathfinding

you can see what is it here :

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

User avatar
Tarzin
Posts: 68
Joined: Mon Feb 15, 2010 11:46 am
Location: Dunkerque / FRANCE
Contact:

Re: Help : A* algorythm

Post by Tarzin » Tue Jun 21, 2011 12:29 pm

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! ;)
A500 / A600 / A1200 / SAM440
WinUAE OS3.9 (AmiKit) / OS4.1FE (FlowerPot)
---
https://twitter.com/TarzinCDK

ArtBlink
Posts: 437
Joined: Mon Nov 01, 2010 10:37 am
Location: Albert - France
Contact:

Re: Help : A* algorythm

Post by ArtBlink » Tue Jun 21, 2011 7:36 pm

Yes, it's for match it ;-)

jalih
Posts: 254
Joined: Fri Jun 18, 2010 8:08 pm
Location: Finland

Re: Help : A* algorythm

Post by jalih » Sun Jun 26, 2011 12:08 am

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
Posts: 254
Joined: Fri Jun 18, 2010 8:08 pm
Location: Finland

Re: Help : A* algorythm

Post by jalih » Sun Jun 26, 2011 10:12 pm

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! :D

jalih
Posts: 254
Joined: Fri Jun 18, 2010 8:08 pm
Location: Finland

Re: Help : A* algorythm

Post by jalih » Mon Jun 27, 2011 8:51 am

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
Posts: 437
Joined: Mon Nov 01, 2010 10:37 am
Location: Albert - France
Contact:

Re: Help : A* algorythm

Post by ArtBlink » Tue Jun 28, 2011 10:44 am

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 ;-)

User avatar
Tarzin
Posts: 68
Joined: Mon Feb 15, 2010 11:46 am
Location: Dunkerque / FRANCE
Contact:

Re: Help : A* algorythm

Post by Tarzin » Thu Jun 30, 2011 1:25 pm

@jalih
Very amazing!

Thank you so much!
A500 / A600 / A1200 / SAM440
WinUAE OS3.9 (AmiKit) / OS4.1FE (FlowerPot)
---
https://twitter.com/TarzinCDK

Post Reply