Pathfinding AI

BlitzMax Forums/BlitzMax Beginners Area/Pathfinding AI

mothmanbr (Posted 2007) [#1]

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?

MrCredo (Posted 2007) [#2]

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?

tonyg (Posted 2007) [#3]

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.

mothmanbr (Posted 2007) [#4]

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

tonyg (Posted 2007) [#5]

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

mothmanbr (Posted 2007) [#6]

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.

Paposo (Posted 2007) [#7]

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

xMicky (Posted 2007) [#8]

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

Paposo (Posted 2007) [#9]

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

MrCredo (Posted 2007) [#10]

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.

mothmanbr (Posted 2007) [#11]

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

Paposo (Posted 2007) [#12]

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

mothmanbr (Posted 2007) [#13]

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.