To help the enemy find me better...

What should I do? I'm referring to the AI enemy in my Blitz
game, of course! Here's what I have:

Multiple points in 2D space: each point is connected to a
few other points. This creates a sort of web of paths for
an AI to follow in my level.



I want to be able to pick any arbitrary point in the system
and have the AI find the quickest way to get to any other
point. The halflife games do this with great success.

Do any of you guys have resources for pathfinding algorithms
that would help me do this?

While you guys are all busy finding an answer for me (Haha
yeah right), I'll be busy learning the A* method.

What are your experiences with AStar? Has anyone here
successfully used it in a project recently?

I hear the method of implementaion for it varies wildly from game to game.

Look for Astar pathfindig algorithms. Although most are based on a uniform grid of points the same weighting/ cost can be applied here.

Try this excellent A* Blitz demo (well 5 actually):

http://www.blitzcoder.com/cgi-bin/showcase/showcase_showentry.pl?id=turtle177604062002002208&comments=no

Using A* with random lenght paths/points might be problematic though, as you need to calc the cost - maybe lenght of the edge or something might do?

Thanks Mustang, that would have been perfect, but I can't
run it because I don't have BB. and viewing it in notepad
doesn't do it for me.

I actually wasn't originally planning to use aStar with my
above web-like system, I was just going to scrap that and
write some code that would create a grid approximation of my
level, BUT you make a good point that it could still be
done with that web!

Here's a cool tutorial that's making AStar very clear to me,
though. Don't know A* yet? Check it out!

Personally, I precalculate everything - there is no computational time involved unlike most other AI systems.

Depends on your level though and just how many nodes there are. However, even for something like a Half-Life game, I would use critical nodes.

In your above example - I can precalc the quickest route from 1 to 9 as 1,2,8,9.

Quickest path from 1 to 5 is 1,2,4,7,5

Each of your nodes has 1, 2, 3, or 4 routes. So, precalc'ing is going to be simple.

..be my enemy and I'll find ya!

Great idea! We could learn the fundamentals of AStar
pathfinding by roleplaying Crazy Stalker/Helpless Victim! Ok,
my exact address is ....

heh heh.

Anyway, I just wanted to post and say:

WOOHOO, I DID IT!! I FIGURED OUT THE INFAMOUS A* PATHFINDING ALGORITHM!

See? Here's my first program showing this:

[edit: Updated]

'First pathfinding program using A*
'Based from this tutorial:   <a href="http://www.policyalmanac.org/games/aStarTutorial.htm" target="_blank">http://www.policyalmanac.org/games/aStarTutorial.htm</a>

'Import "drawThings.bmx"
SuperStrict
Graphics 1024, 768, ,60
Global mapX:Int = 11, mapY:Int = 8, heuristic:Int = 3, heuristicName:String = "Diagonal"



Type endsType
	Field startX:Int, startY:Int, endX:Int, endY:Int
	Method New()
		startX = 2
		startY = 2
		endX = 10
		endY = 2
	EndMethod
EndType
Global ends:endsType = New endsType


Type nodeType
	Field F:Int, G:Int, H:Int, open:Int=0, parentX:Int, parentY:Int
	Method New()
		open = 0
	EndMethod
EndType
Global map:Int[mapX+1,mapY+1]
Global node:nodeType[mapX+1,mapY+1]


For Local y:Int  = 0 To mapY
	For Local x:Int = 0 To mapX
		map[x,y] = 0
		node[x,y] = New nodeType
	Next
Next
For Local a:Int = 2 To 6
	map[6, a]=255
Next
map[ends.startX, ends.startY] = 256
map[ends.endX, ends.endY] = 257

SetClsColor 50, 60, 50
Repeat
	dokeys()
	drawmap()
	SetColor 255, 255, 255
	DrawText "Left mouse - set start, right mouse - set goal, middle mouse - draw wall, up arrow - floor stick", 40, 740
	DrawText "Heuristic: "+heuristicName+", (hit 1, 2, 3 to change)", 40, 754
	Flip;Cls
Forever
Function drawmap()
	For Local y:Int = 0 To mapY
		For Local x:Int = 0 To mapX
			'If map[x,y]
			SetColor map[x,y]*5, map[x,y]*5, map[x,y]*5
			Select map[x,y]
				Case 255										'wall
					SetColor 10, 30, 100
				Case 256										'starting node
					SetColor 20, 170, 30
				Case 257										'goal node
					SetColor 100, 30, 10
			EndSelect
			drawl(x*80, y*80, 79, 79, 1, FILL)
			'EndIf
			SetColor 75, 75, 75
			drawl(x*80, y*80, 79,79)
			Select node[x,y].open
				Case 1
					SetColor 170, 170, 170
					DrawText "F"+node[x,y].F, x*80+21, y*80+3
					DrawText "G"+node[x,y].G, x*80+1, y*80+63
					DrawText "H"+node[x,y].H, x*80+41, y*80+63
					SetColor 50, 150, 10
					DrawEllipse x*80+40, y*80+40,3,3
					SetColor 10, 200, 10
					DrawL (x*80+40, y*80+40, (node[x,y].parentX-x)*20, (node[x,y].parentY-y)*20,1,LINE)
				Case -1
					SetColor 185, 25, 25
					drawl(x*80+1, y*80+1, 77,77)
					drawl(x*80+3, y*80+3, 73,73)
					drawl(x*80+2, y*80+2, 76,76,2,corners)
					DrawEllipse x*80+40, y*80+40,3,3
					SetColor 10, 200, 10
					DrawL (x*80+40, y*80+40, (node[x,y].parentX-x)*20, (node[x,y].parentY-y)*20,1,LINE)
			EndSelect
		Next
	Next
EndFunction
Function dokeys()
	If KeyHit(key_1) Then heuristic = 1; heuristicName = "Manhattan *10"
	If KeyHit(key_2) Then heuristic = 2; heuristicName = "Manhattan"
	If KeyHit(key_3) Then heuristic = 3; heuristicName = "Diagonal"
	If KeyHit(key_up) Then
		Local colour:Int = 0
		For Local x:Int = 0 To mapX
			For Local y:Int = mapY To 0 Step -1
				If map[x,y] = 255 Then
					colour = 0
				Else
					If map[x,y]<255 map[x,y] = colour
					colour:+5
				EndIf
			Next
			colour=0
		Next
	EndIf
	If MouseDown(1) Then
		map[ends.startX, ends.startY]=0
		ends.startX = MouseX()/80
		ends.startY = MouseY()/80
		map[ends.startX, ends.startY]=256
	EndIf
	If MouseDown(2) Then
		map[ends.endX, ends.endY]=0
		ends.endX = MouseX()/80
		ends.endY = MouseY()/80
		map[ends.endX, ends.endY]=257
	EndIf
	If MouseHit(3) Then
		If map[MouseX()/80, MouseY()/80]<>255 Then 
			map[MouseX()/80, MouseY()/80]=255
		Else
			map[MouseX()/80, MouseY()/80]=0
		EndIf
		For Local y:Int = 0 To mapY
			For Local x:Int = 0 To mapX
				node[x,y].open = 0
				If map[x,y]<255 Then map[x,y] = 0
			Next
		Next
	EndIf
	If KeyHit(key_escape) End
	If KeyHit(key_space) Or MouseHit(1) Or MouseHit(2) Then
		For Local y:Int = 0 To mapY
			For Local x:Int = 0 To mapX
				node[x,y].open = 0
			Next
		Next
		Local currentX:Int = ends.startX, currentY:Int = ends.startY
		Local lowFX:Int, lowFY:Int
		For Local a:Int = 0 To 80
			createFGH(currentX, currentY)
			findLowF(currentX, currentY)
			If currentX = ends.endX And currentY = ends.endY Then Exit
		Next
'		SetColor 255, 255, 255
'		DrawText lowFX+", "+lowFY, 10, 587
'		Flip
'		WaitKey
	EndIf
EndFunction
Function createFGH(x:Int, y:Int)
	'Local x:Int = ends.StartX, y:Int = ends.startY
	Local xTarget:Int = ends.endX, yTarget:Int = ends.endY
	node[x,y].open = -1
	For Local yy:Int= -1 To 1
		For Local xx:Int = -1 To 1
			If x+xx < 0 Or x+xx > mapX Continue
			If y+yy < 0 Or y+yy > mapY Continue
			If node[x+xx, y+yy].open = -1 Or map[x+xx, y+yy] = 255 Continue	'If this node has been closed, skip To the Next one.
			If node[x+xx, y+yy].open = 1 Then
				'find the G score between current node and this here node
'				Local G:Int = 14
'				If xx = 0 Or yy = 0 Then G = 10
'				If G < node[x+xx, y+yy].G Then
'					node[x+xx, y+yy].parentX = x
'					node[x+xx, y+yy].parentY = y
'				EndIf
			EndIf
			If node[x+xx, y+yy].open = 0 Then					'0 = not been touched yet
				node[x+xx, y+yy].open = 1								'change it to 1, showing that we now consider it a possible path.
				node[x+xx, y+yy].parentX = x
				node[x+xx, y+yy].parentY = y
			EndIf
			Select heuristic
				Case 1
					node[x+xx, y+yy].H = (Abs(x+xx-ends.endX)+Abs(y+yy-ends.endY))*10
				Case 2
					node[x+xx, y+yy].H = (Abs(x+xx-ends.endX)+Abs(y+yy-ends.endY))
				Case 3
					Local ydist:Int = Abs(y+yy-ends.endY)
					Local xdist:Int = Abs(x+xx-ends.endX)
					If xDist> yDist Then
						node[x+xx, y+yy].H = 14*yDist +10*(xDist-yDist)
					Else
						node[x+xx, y+yy].H = 14*xDist +10*(yDist-xDist)
					EndIf
			EndSelect
			node[x+xx, y+yy].G = 14
			If xx = 0 Or yy = 0 node[x+xx, y+yy].G = 10
			node[x+xx, y+yy].F = node[x+xx, y+yy].G + node[x+xx, y+yy].H
		Next
	Next
EndFunction
Function findLowF:Int(lowFCoordinateX:Int Var, lowFCoordinateY:Int Var)
	Local lowestF:Int = 999999
	For Local y:Int = 0 To mapY
		For Local x:Int = 0 To mapX
			If node[x,y].open = 1 Then
				If node[x,y].F < lowestF Then
					lowestF = node[x,y].F
					lowFCoordinateX = x
					lowFCoordinateY = y
				EndIf
			EndIf
		Next
	Next
EndFunction




Const NORMAL:Int = 0
Const DOTTED:Int = 1
Function drawEllipse(x:Int,y:Int,xSize:Int,ySize:Int,StepSize:Int = 15, width:Int=1, style:Int = NORMAL)
	Local oldlinewidth:Int = GetLineWidth(), dot:Int = 1
	SetLineWidth width
	Local a:Int = stepSize
	Repeat
		If dot DrawLine x+xSize*Sin(a), y+ySize*Cos(a),x+xSize*Sin(a-stepSize), y+ySize*Cos(a-stepSize)
		a:+stepSize
		If style dot = 1-dot
	Until a> 360
	SetLineWidth oldlinewidth
EndFunction



Const FILL:Int = 3
Const LINE:Int = 2
Const CORNERS:Int = 1
Const BOX:Int = 0

Function drawl(x1:Int,y1:Int,x2:Int,y2:Int,width:Int=1,style:Int = BOX)
	Local oldlinewidth:Int = GetLineWidth()
	SetLineWidth width
	Select style
	Case 3
		DrawRect x1,y1,x2,y2
	Case 2
		x2:+x1
		y2:+y1
		DrawLine x1,y1,x2,y2
	Case 1
		x2:+x1
		y2:+y1
		DrawLine (x1,y1,x1+(x2-x1)*.1,y1)
		DrawLine (x1,y1,x1,y1+(y2-y1)*.1)
		DrawLine (x1,y2-(y2-y1)*.1,x1,y2)
		DrawLine (x1,y2,x1+(x2-x1)*.1,y2)
		
		DrawLine (x2,y1,x2-(x2-x1)*.1,y1)
		DrawLine (x2,y1,x2,y1+(y2-y1)*.1)
		DrawLine (x2,y2-(y2-y1)*.1,x2,y2)
		DrawLine (x2,y2,x2-(x2-x1)*.1,y2)
	Default
		x2:+x1
		y2:+y1
		DrawLine (x1,y1,x2,y1)
		DrawLine (x1,y1,x1,y2)
		DrawLine (x1,y2,x2,y2)
		DrawLine (x2,y1,x2,y2)
	EndSelect
	SetLineWidth oldlinewidth
End Function

As you can see, it doesn't find the most efficient route at
all. I'm not sure why. Not to mention the code is
horrendous (I'm using functions! Ah!)

But it works! And it works pretty fast, too! Now, I
rewrite and rewrite again until I have a usable module to
implement in my projects.

This is quite cool. I'm very excited.

A* isn't guaranteed to find the shortest route (that's Djikstra's algo). It's a trade off between speed and an 'acceptable' route. To get more accurate underestimate
your heuristic. A *very* quick check and your manhatten distance seems to be *10. Is that right? Try taking out the *10.

Also aStar is best used on a dense graph (where most nodes have connections to most other nodes). If you have a sparse graph, where most nodes only have connections to a few other nodes, Djikstras Shortest Path Tree Algorithm is probably better.

Thanks, tonyg. Although, taking out the *10 makes for a very...
"square-edged" path that ends up being a less-efficient path.
You can run it to see what I mean.

The Diagonal heuristic, however is very, very nice. It
consistently finds the more direct route compared to
Manhattan, AND it opens far less nodes in the process! This
AStar stuff is amazing.

FlameDuck: Yeah, I can see this working much better on a
dense bunch of nodes, BUT i've decided to trash the original
node-web system and use a grid.

It's a much better idea, because I can take the collision
mask of my level and create a grid on-the-fly for the A* to
use. Because my terrain is going to be generated at random,
and then heavily modified during gameplay, I can't really
see how my web system would work at all.

Well, if you are fighting in the wilderness of the continental US, how about wearing bright red. It worked for the British.
hahahahahahahaha

I'm thinking you should precalculate a list of shortest routes between each possible node pair.

Leadwerks: I'm trashing the web-node idea and I'm using a node
grid. My map will be randomly generated and then heavily
modified during gameplay.

I can't precalculate for that.



Can I?

I think you can.
When the map is randomly generated in the first place, as long as you build into that part of the program a precalculation for shortest route for small parts of the map, then it should still give good results.

The heavily modified bit is a bugger, I would say yes, but I dont tend to write RT games, more TB games. And in TB you can do this, but if it would be real time or not, Im not sure.

Well, there's a can of worms - the Half-Life (and many other) games don't let you do that.

Anything else that is going to significantly alter the final method?

EDIT:
In fact, define

Well actually puki, this game takes place in 2D space, like so:

And I can heavily modify my terrain (via intense battling,
shelter-building, etc) so that it eventually looks like so:


I will be creating a low-res solid/non-solid collision grid from the hi-res collision mask used
by entities. AStar will use this for pathfinding. That AStar grid might look something like this:


The above pictures were just whippped up in photoshop, if you really want
to see what I'm aiming for, take a gander at this: A link to my old, old map generator,
done in Qbasic about 8 years ago. Sadly the game that was built using this generator is
long gone. Despite how unfinished it was, friends say it was "pretty kick-ass" to battle
each other with it. (2-player, shared screen). This is the
reason I program, to hear remarks like that.

Back then, I only had indexed colours, I had no image loading code or even any video
layers(or "backbuffers", whatever), So all visuals were procedurally generated on the
screen. I have had many working (but very incomplete) versions of this project in
the past, and I feel I am ready to complete one.

This time, I can do it right. This time, I have knowledge of Finite State machines, AStar,
and some predictive-projectile code I've been honing. And of course, I also have BMax!

A star is ok for a 2d grid, but seems to be very slow in a 3d grid.

I'm not using a 3D Grid though.

wow drew I think I saw your generator years ago, thats awesome. And if you make it into tiles A* is very doable. I also made a game like this with AI, its on my website.