Pathfinding AI

Well, after coding my first AI idea, I realize that it doesn't work as well as I thought it would... So I was thinking about finding a path to the player when the enemy is created, and then just follow it:


Here for example, it gets an initial straight path to the player and checks if it collides with something. If not, great, follow it. If it does, in this case, that gray thingy, then it checks for alternatives.


Here it went up a bit, and then straight to the player. But it's still not perfect.


Now it can reach the player without colliding with anything. But that's a damn ugly path. Until now, I can do it on my own, saving the path in a list of points and following it.


So, it takes the point that deviates from the original path the most, and makes it the half point of a curve between the player and the enemy. But I have no idea how to do that. I have two ideas, one using sin and cos, the other just taking the axis with the smallest difference, in the image above it would be Y, and add successive values, lowering every time.

Did anyone ever have to do this? Will this be resource-consuming?

here is a easy "realtime" algoritm for such pathifinding... i don't know the name of it... but i think you can write your own routine...

the basic-idea...

source is the top point and dest is the bottom point... so that your object can "roll" from top to down... if you have a object in the moddle - this generate a small hill - so that your object automaticaly do not collide with this...

you need this:
-dest coord
-current coord
-all collide coords + collide factor

from all this coords you can calculate delta coords to move your object... you should normalize delta to 1 and multiply this with speed factor...

i have no formulas... but i think this is smilar to this:

http://en.wikipedia.org/wiki/Metaballs
http://de.wikipedia.org/wiki/Metaball


but this algo is not perfect - it have problems with complex scenes (labyrinths) - i do not know - do you have labyrinths?

Toward More Realistic Pathfinding . on Gamasutra. You might need to register (unless you can search and find the article somewhere else) but well worth it.

Well actually I don't plan to create any labyrinths, but in later stages there will be a lot of rocks, meaning the enemies will have to dodge several times, maybe make several turns to reach the player. So I think I don't need something very complex. I have to leave now, I'll read the links you gave me as soon as I'm back. Thanks tonyg :)

Your last comments suggest you might want to look at Steering Behaviours for which Scott Shaver created a module
Here's some more info.

Sorry McCredo I thought your post was also by tonyg, so I forgot to say thanks... So thanks :) Your idea would work too but I think the steering behaviours are more appropriate in this case.

tonyg: I think that will do just great, will try it as soon as I get home. Thanks.

Hello.

The "standar" pathfindig algoritm A* es useful for you. One system for make your movement is increment the cost of nodes proportionally to the distance to grey player.
Low distance -> high cost
high distance -> low cost
The A* make your curve automatically

I write a pathfinding function really fast.
it take in my machine 4.5 seg in traverse a map of 100000 nodes and only 384 millisec for a map with 10000 nodes. All nodes are traversables in 8 directions with a random cost. If not all nodes are traversables the time is reduced.
The algoritm is useful with any number of directions.

If you need it talk with me. It is free :-)

Bye,
Paposo

Isn't the needed code not already in the forum ?
Click here!

Hello.

Yes xMicky.
This is only another point of view of same algorithm.
The indiepath es very very fast. My routine more slow.

Diferences:
Indie algorithm:
- Use rectagular cells in a matrix
- two dimensional paths
- Fixed heuristic
- Directions fixeds
- Dependance algorithm - map
- Construct the nodes automatically
- All the nodes are identically
- Very especific

Paposo algorithm:
- Not use cells in any matrix
- N dimensional paths
- Customizable heuristic
- Directions variables for each cell
- Independance algorithm - map
- The user construct the nodes
- Allowed diferent node, costs and heuristic implementations in same map
- Very generic

The objectives of routines are distincts.

I have in developement more optimized routine. I are regarding the fast-fast indie code for make optimizations in my code. ;-)

Bye,
Paposo

hm... if i have time, i write this routine, i decribed above... it is good for not complex scenes - with many moving objects - and you need only few simple calculations
and if something changes - you get the result at "realtime"...

You do not need cells and you do not need predefined paths/grids. You do not get a path to destination, but you get only a moving direction. And in theory you sohuld have smooth movement.

Paposo I would like to take a look at your code, if you don't mind. My e-mail and MSN is mothmanbr@...

Thanks.

Hello M07hM4n.

This version are more optimized . It take 24 millisec in 1 million nodes in my machine.
For fast algorithm the cost fixed + modifier equilibrated with heuristic. For optimal path heuristic low than (costfixed+modifier)

The user adjust factorPA, fixed cost, modifiers for penality certains directions, and heuristic for your pourpose. It make de algorithm more fast or slow.

Sorry. All coments are in spanish
This is the code:

SuperStrict

Public

'*************************************************************************************************
'	TIPO ABSTRACTO PARA MODELAR EL FUNCIONAMIENTO
'*************************************************************************************************

Type TAStarMapa Abstract
	Method getNumNodos:Int() Abstract								'	Devuelve el numero de nodos de la rejilla
	Method getSucesores:Int[](nodo:Int) Abstract					'	Devuelve un array con las indices de los nodos sucesores
	Method getModificadores:Int[](nodo:Int) Abstract				'	Devuelve un array con los modificadores para cada sucesor
	Method getCosteFijo:Int(nodo:Int) Abstract						'	Devuelve un array con los costes fijos de cada nodo
	Method getCosteH:Float(nodo:Int, nodoMeta:Int) Abstract			'	Devuelve el coste estimado desde un nodo hasta la meta
	Method esTransitable:Byte(nodo:Int) Abstract					'	Devuelve true si el nodo es transitable o false en caso contrario
EndType

'*************************************************************************************************
'	FUNCION DE BUSQUEDA DE CAMINO
'*************************************************************************************************	

'	nodoOrigen: Nodo de partida
'	nodoMeta:	Destino
'	mapa:		Implementacion de TAStarMapa
'	factorPA:	Altera la importancia de busqueda en amplitud o profundidad
'				Si factorPA < 0.5:	Busca mas en profundidad. Heuristica mas importante que coste calculado. Apto para caminos muy largos
'				Si factorPA > 0.5:	Busca mas en amplitud. Coste calculado mas importante que heuristica. Apto para caminos cortos
'				Si factorPA = 0.5:	Busqueda balanceada. Identica importancia. Ponderado
Function PathFinder:Int[](nodoOrigen:Int, nodoMeta:Int, mapa:TAStarMapa, factorpa:Float=0.5)

	Assert (factorPa>=0 And factorPa<=1), "1 >= factorPA >= 0"
	
	'	Origen y destino deben ser transitables
	If Not (mapa.esTransitable(nodoOrigen) And mapa.esTransitable(nodoMeta))
		Return New Int[0]
	EndIf
	
	'	Inicializar
	Local numNodos:Int=mapa.getNumNodos()
	Local costeG:Int[]=New Int[numNodos]
	Local padres:Int[]=New Int[numNodos]
	Local cerrada:Int[]=New Int[numNodos]

	Global costeF:Float[]=New Float[numNodos]				'	Coste actualmente calculado
	Global abierta:Int[]=New Int[numNodos]					'	Contiene los indices de los nodos
	Global locAbierta:Int[]=New Int[numNodos]				'	Contiene el indice en abierta de cada id de nodo
	Global sizeAbierta:Int=0								'	Tamaño logico de la lista abierta
	
	Local nodoAct:Int
	Local finalizar:Byte=False
	
	costeG[nodoOrigen]=mapa.getCosteFijo(nodoOrigen)
	costeF[nodoOrigen]=costeG[nodoOrigen]+mapa.getCosteH(nodoOrigen,nodoMeta)
	
	'	Inserta el nodo origen en abierta
	sizeAbierta:+1
	'If(sizeAbierta>=abierta.length)
	'	_grow(sizeAbierta)
	'EndIf
	abierta[sizeAbierta]=nodoOrigen
	locAbierta[nodoOrigen]=sizeAbierta+1					'	Se añade 1 para que 0 sea indicador de que no existe
	_fixup(sizeAbierta)
	'	Fin insercion
	
	Repeat


		If(sizeAbierta=0)									'	Si no hay nodos en abierta termina el proceso
			nodoAct=-1
			finalizar=True
		Else

			'	Extrae el siguiente nodo de abierta		
			nodoAct=abierta[1]
			locAbierta[nodoAct]=0

			abierta[1]=abierta[sizeAbierta]
			locAbierta[abierta[1]]=1+1

			abierta[sizeAbierta]=-1
			sizeAbierta:-1
		
			If(sizeAbierta>1)
				_fixdown(1)
			EndIf
			'	Fin extraccion
			
			cerrada[nodoAct]=1
			Local sucesores:Int[]=mapa.getSucesores(nodoAct)
			Local modificadores:Int[]=mapa.getModificadores(nodoAct)
			For Local mm:Int=0 To sucesores.length-1
				Local suc:Int=sucesores[mm]
				If(suc=nodoMeta)
					padres[suc]=nodoAct
					nodoAct=suc
					finalizar=True
					Exit
				EndIf
				If(cerrada[suc]=0 And mapa.esTransitable(suc) )						
					'	Controla la actualizacion de abierta
					Local cG:Int=factorPA*(mapa.getCosteFijo(suc)+modificadores[mm])+costeG[nodoAct]
					If(locAbierta[suc]>0)								'	¿Esta ya en abierta?
						If(costeG[suc]>cG)
							costeF[suc]=costeF[suc]-costeG[suc]+cG
							costeG[suc]=cG
							padres[suc]=nodoAct
							_fixup(locAbierta[suc]-1)		'	Reordena abierta
						EndIf
					Else
						costeF[suc]=cG+(1-factorPA)*mapa.getCosteH(suc,nodoMeta)
						costeG[suc]=cG
						padres[suc]=nodoAct
						'	Inserta el nuevo sucesor en abierta
						sizeAbierta:+1
				'		If(sizeAbierta>=abierta.length)
				'			_grow(sizeAbierta)
				'		EndIf
						abierta[sizeAbierta]=suc
						locAbierta[suc]=sizeAbierta+1		'	Se añade 1 para que 0 sea indicador de que no existe
						_fixup(sizeAbierta)
						'	Fin insercion

					EndIf
				EndIf
			Next
		EndIf
	Until (finalizar)
	
	If(nodoAct<0)
		Return New Int[0]
	EndIf
	

	Local act:Int=0
	Local cta:Int=1
	act=nodoAct
	While(act<>nodoOrigen)
		cta:+1
		act=padres[act]
	Wend
	act=nodoAct
	Local resultado:Int[]=New Int[cta]
	While(cta>0)
		cta:-1
		resultado[cta]=act
		act=padres[act]
	Wend

	
	Return resultado

'-------------------------------------------------------------------------------------------------------	
'	funcion interna hacer crecer la lista abierta cuando es necesario

	Function _grow(index:Int)
		Local sizeAbiertaAct:Int=abierta.length
		If(index<sizeAbiertaAct)
			Return
		Else
			sizeAbiertaAct=sizeAbiertaAct Shl 2
		EndIf
		abierta=abierta[..sizeAbiertaAct]
	EndFunction
'-------------------------------------------------------------------------------------------------------	
'	funcion interna que balancea el arbol desde el la posicion hacia inicio (como si se hubiera incrementado la prioridad)

	Function _fixup(k:Int)
		Local j:Int
		Local tmp:Int
		
		While(k>1)
			j=k Shr 1
			If(costeF[abierta[j]]<=costeF[abierta[k]])
				Exit
			EndIf
			tmp=abierta[j]
			abierta[j]=abierta[k]
			abierta[k]=tmp
			
			locAbierta[abierta[j]]=j+1
			locAbierta[abierta[k]]=k+1
			k=j
		Wend
	EndFunction	
'-------------------------------------------------------------------------------------------------------	
'	funcion interna que balancea el arbol desde posicion hasta final (como si se hubiera decrementado la prioridad)

	Function _fixdown(k:Int)
		Local j:Int
		Local tmp:Int
		
		Repeat
			j=k Shl 1
			If(Not ( (j<=sizeAbierta) And (j>0)))
				Exit
			EndIf
			If( (j<sizeAbierta) And (costeF[abierta[j]] > costeF[abierta[j+1]] ))
				j:+1
			EndIf
			If(costeF[abierta[k]] <= costeF[abierta[j]])
				Exit
			EndIf
			tmp=abierta[j]
			abierta[j]=abierta[k]
			abierta[k]=tmp

			locAbierta[abierta[j]]=j+1
			locAbierta[abierta[k]]=k+1
			k=j			
		Forever
	EndFunction

EndFunction

This is a example with 1000000 nodes and 8 directions

'*************************************************************************************************
'	EJEMPLO DE USO
'*************************************************************************************************


 
Type TMapa Extends TAStarMapa
	Field mapa:Int[,]
	Field coste:Int[]
	Field numNodos:Int
	Field sucesores:Object[]
	Field modificadores:Int[][]=[ 	[14, 10, 14, 10, 10, 14, 10, 14], ..
									[10,10,14], ..
									[10,14,10], ..
									[10,14,10], ..
									[14,10,10], ..
									[10,10,14,10,14], ..
									[14,10,14,10,10], ..
									[10,14,10,10,14], ..
									[14,10,10,14,10] ..
								]
	
	
	Function create:TMapa(mapa:Int[,], coste:Int[])
		Local m:TMapa=New TMapa
		m.mapa=mapa
		m.coste=coste
		m.numNodos=mapa.dimensions()[0]
		m.preCalcularSucesores()
		Return m
	EndFunction
	
	Method getNumNodos:Int() 							'	Devuelve el numero total de nodos
		Return numNodos
	EndMethod	
		
	Method getCosteFijo:Int(nodo:Int)					'	Coste fijo de un nodo
		Return coste[nodo]
	EndMethod
	
	Method getCosteH:Float(nodo:Int, nodoMeta:Int)		'	Heuristica
		Local dx:Int=Abs(mapa[nodo,0]-mapa[nodometa,0])
		Local dy:Int=Abs(mapa[nodo,1]-mapa[nodometa,1])
		'	heuristica optima
		Return Sqr((dx*dx)+(dy*dy))*10

		Rem
		'	Heuristica aceptable
		If(dx>dy)
			Return (14*dy+10*(dx-dy))
		Else
			Return (14*dx+10*(dy-dx))
		EndIf
		EndRem

		'	heuristica manhathan. No proporciona caminos optimos
		Rem
		Return 10*(dx+dy)
		EndRem
	EndMethod
	
	Method esTransitable:Byte(nodo:Int)					'	Devuelve true si el nodo es transitable
		Return True
	EndMethod
	
	Method getSucesores:Int[](nodo:Int)					'	Devuelve un array con todos los vecinos de un nodo
		Return Int[](sucesores[nodo])
	EndMethod
			
	Method getModificadores:Int[](nodo:Int)				'	Devuelve un array con los modificadores de coste para cada uno de los vecinos desde nodo
		Return modificadores[getTipoPosicion(nodo)]
	EndMethod



	Method preCalcularSucesores()						'	Uso interno. Para optimizar
		sucesores=New Object[numNodos]
		For Local nn:Int=0 To numNodos-1
			sucesores[nn]=getSucesoresInt(nn)
		Next
	EndMethod
	

	Method getTipoPosicion:Int(nodo:Int)				'	Uso interno
		Local retorno:Int
		Local nf:Int=Int(nodo / 1000)
		Local nc:Int=nodo Mod 1000
		If(nf<>0 And nf<>999 And nc<>0 And nc<>999)
			retorno=0
		ElseIf(nF=0 And nc=0)
			retorno=1
		ElseIf( nf=0 And nc=999)
			retorno=2
		ElseIf( nf=999 And nc=0)
			retorno=3
		ElseIf(nf=999 And nc=999)
			retorno=4
		ElseIf (nf=0)
			retorno=5
		ElseIf( nf=999)
			retorno=6
		ElseIf(nc=0)
			retorno=7
		ElseIf(nc=999)
			retorno=8
		EndIf
		Return retorno
	EndMethod
		
	Method getIncrementos:Int[](nodo:Int)				'	Uso interno. Incremento a añadir para obtener sucesores
		Local retorno:Int[]
		Local tp:Int=getTipoPosicion(nodo)
		
		Select tp
			Case 0
				retorno=[-1001,-1000,-999,-1,1,999,1000,1001]
			Case 1
				retorno=[1,1000,1001]
			Case 2
				retorno=[-1,999,1000]
			Case 3
				retorno=[-1000,-999,1]
			Case 4
				retorno=[-1001,-1000,-1]
			Case 5
				retorno=[-1,1,999,1000,1001]
			Case 6
				retorno=[-1001,-1000,-999,-1,1]
			Case 7
				retorno=[-1000,-999,1,1000,1001]
			Case 8
				retorno=[-1001,-1000,-1,999,1000]
		EndSelect
		
		Return retorno
	EndMethod

	Method getSucesoresInt:Int[](nodo:Int)				'	Uso interno
		Local incr:Int[]=getIncrementos(nodo)
		Local retorno:Int[]=New Int[incr.length]
		For Local nn:Int=0 To incr.length-1
			retorno[nn]=nodo+incr[nn]
		Next
		
		Return retorno
	EndMethod

EndType



Local rejilla:Int[,]=New Int[1000000,2]
Local costes:Int[]=New Int[1000000]
Local cta:Int=0

'SeedRnd(MilliSecs())

For Local yy:Int=0 To 999
	For Local xx:Int=0 To 999
		rejilla[cta,0]=xx
		rejilla[cta,1]=yy
		costes[cta]=Rand(1,20)
		cta:+1
	Next
Next


Local map:TMapa=TMapa.create(rejilla, costes)

Local t1:Int=MilliSecs()
Local resultado:Int[]=PathFinder(0,999999,map, 0.3)
Local t2:Int=MilliSecs()

Print resultado.length

Print (t2-t1)

For Local nn:Int=0 To resultado.length-1
	Local mm:Int=resultado[nn]
	Print "Nodo: "+String(mm)+String"  ( "+String(rejilla[mm,0])+" , "+String(rejilla[mm,1])+ " )"
Next

if you need explain answer me

Bye,
Paposo

Thanks Paposo, do you expect a mention in the special thanks section of the credits? :P

And don't worry about the spanish, I speak portuguese and can handle myself with it.