Pathfindingmodule

SiWi

27-05-2007 09:35:26

I know there is another thread about AI modules, but I only need pathfinding and not complete AI. Do you know any pathfinding modules for Python?

saladin

28-05-2007 16:23:19

I know there is another thread about AI modules, but I only need pathfinding and not complete AI. Do you know any pathfinding modules for Python?

Google 'A-Star python'. If the first 10 search result doesn't give u what u want, maybe we should look at python-wrapping 'OpenSteer'.

pocho

30-05-2007 20:05:41

ok saladin here a the code
a very simple pathfinder whith the A*
you can check a tutorial here
http://www.policyalmanac.org/games/aStarTutorial.htm

the code of scabootssca to PYTHON in blender game engine
the blend file
http://pochoblender.googlepages.com/AstarDemo.rar


#;===================================================================
#;A* Pathfinder Version:3.2
#;===================================================================
#:Made By scabootssca 6/12/06
#:Based Off Of The A* Tutorial From
#:http://www.policyalmanac.org/games/aStarTutorial.htm
#:Made For Use With Blender3D www.blender3d.com
#:Blender Forums www.blenderartists.org

# funcion para imprimir en la consola
# el contenido de la matriz array
# usa un for para las las filas
# y dentro de este uno para las columnas

def printArray(array):
for row in array:
for column in row:
if column.pathPart: print "***",
else: print column.draw,
print "\n"
print "\n"*3





class Node:


def __init__(self,Xpos,Ypos,type,draw="000",parentNode=0,G=0,H=0,F=0):
self.Xpos = Xpos
self.Ypos = Ypos
self.type = type
self.draw = draw
self.parentNode = parentNode
self.G = G
self.H = H
self.F = F

#debug
self.pathPart = 0

def makeClosed(self,draw="[|]",type=1):
self.draw = draw
self.type = type

def makeOpen(self,draw="000",type=0):
self.draw = draw
self.type = type

def getDirection(self,startNode):
if (startNode.Xpos==self.Xpos) or (startNode.Ypos==self.Ypos): return 0
else: return 1

def getGcost(self,startNode):
dir = self.getDirection(self.parentNode)
costsG = [10,14]
return startNode.G+costsG[dir]

def getFGH(self,startNode,endNode):
#\/---(Get The G-Cost)
self.G = self.getGcost(self.parentNode)
#\/---(Get The H-Cost)
self.H = 10*(abs(self.Xpos-endNode.Xpos)+abs(self.Ypos-endNode.Ypos))
#\/---(Get The F-Cost)
self.F = self.G+self.H
#debug
#self.draw = self.F

class createArray:
def __init__(self,width,height):
self.width = width
self.height = height
self.array = []
self.createEmptyArray(width,height)
self.openList = []
self.closedList = []
self.startNode = 0
self.endNode = 0

def createEmptyArray(self,width,height):
for row in range(height):
tmpAdd = []
for column in range(width):
newX,newY = self.convertCoords(column,row,height)
newNode = Node(newX,newY,0)
tmpAdd.append(newNode)
self.array.append(tmpAdd)

def convertCoords(self,x,y,preLength=0):
length = len(self.array)
if preLength: length = preLength
x = x
y = length-1-y
return x,y

def getNode(self,Xnode,Ynode):
"""Call This Anytime You Change A Node"""
x,y = self.convertCoords(Xnode,Ynode)
return self.array[y][x]

def makeOpen(self,Xnode=0,Ynode=0,draw="000",type=0,node=0):
if not node:
node = self.getNode(Xnode,Ynode)
node.makeOpen(draw,type)
self.openList.append(node)
if self.closedList.count(node):
self.closedList.remove(node)

def makeClosed(self,Xnode=0,Ynode=0,draw="[|]",type=1,node=0):
if not node:
node = self.getNode(Xnode,Ynode)
node.makeClosed(draw,type)
self.closedList.append(node)
if self.openList.count(node):
self.openList.remove(node)

def makeStart(self,Xnode,Ynode):
self.startNode = self.getNode(Xnode,Ynode)

def makeEnd(self,Xnode,Ynode):
self.endNode = self.getNode(Xnode,Ynode)

def checkIsValid(self,Xpos,Ypos):
if (Xpos<0 or Ypos<0) or (Xpos>=self.width or Ypos>=self.height):
return 0
return 1

def getCloseNodes(self,Xstart,Ystart,cutCorners=0):
closeNodes = []
goodCloseNodes = []
onNode = 0
# Check If Is A Valid Node
for Xpos in range(-1,2):
for Ypos in range(-1,2):
startNode = self.getNode(Xstart,Ystart)
onPos = [Xstart+Xpos,Ystart+Ypos]
closeNodes.append(onPos)

for node in closeNodes:
onNode += 1
if self.checkIsValid(node[0],node[1]): #if it is not walkable, ignore it
currentNode = self.getNode(node[0],node[1])
if currentNode.type != 1: #if it is on the closed list, ignore it
corner1 = 0
corner2 = 0
if not cutCorners: #If can't cut corners
# Check To See If Cutting Corners
cN2 = 0
cN4 = 0
cN6 = 0
cN8 = 0
if self.checkIsValid(closeNodes[1][0],closeNodes[1][1]):
cN2 = self.getNode(closeNodes[1][0],closeNodes[1][1]).type

if self.checkIsValid(closeNodes[3][0],closeNodes[3][1]):
cN4 = self.getNode(closeNodes[3][0],closeNodes[3][1]).type

if self.checkIsValid(closeNodes[5][0],closeNodes[5][1]):
cN6 = self.getNode(closeNodes[5][0],closeNodes[5][1]).type

if self.checkIsValid(closeNodes[7][0],closeNodes[7][1]):
cN8 = self.getNode(closeNodes[7][0],closeNodes[7][1]).type

if onNode == 1:
#print closeNodes[0]
corner1 = cN2
corner2 = cN4
#corner2 = 0
#print corner1,corner2,"= Corner1"
if onNode == 3:
corner1 = cN2
corner2 = cN6
#corner2 = 0
#print corner1,corner2,"3"
if onNode == 7:
corner1 = cN8
corner2 = cN4
#corner2 = 0
#print corner1,corner2,"7"
if onNode == 9:
corner1 = cN8
corner2 = cN6
#print corner1,corner2,"9"

if corner1 == 0 and corner2 == 0:
goodCloseNodes.append(currentNode)
return goodCloseNodes

def doCloseNodes(self,parentNode,nodeList):
for node in nodeList:
if not self.openList.count(node): #If it isnt on the open list, add it to the open list.
self.makeOpen(node=node)
node.parentNode = parentNode #Make the current square the parent of this square
node.getFGH(self.startNode,self.endNode) #Record the F, G, and H costs of the square.
else:
if node.G > parentNode.G+node.getGcost(parentNode) : #check to see if this path to that square is better, using G cost as the measure.
node.parentNode = parentNode #change the parent of the square to the current square
node.G = node.getGcost(parentNode) #recalculate the G and F scores of the square
node.F = node.G+node.H

def findLowestFcost(self,nodeList):
lowestNode = nodeList[0]
for node in nodeList:
if node.F < lowestNode.F:
lowestNode = node
return lowestNode

def traceBack(self):
node = self.endNode
traceback = []
while node != self.startNode:
node.pathPart = 1
traceback.append(node)
node = node.parentNode
return traceback

def findPath(self,cutCorners=0):
self.makeOpen(node=self.startNode)
while not self.closedList.count(self.endNode):
currentSquare = self.findLowestFcost(self.openList)
self.makeClosed(draw="000",node=currentSquare)
closeNodes = self.getCloseNodes(currentSquare.Xpos,currentSquare.Ypos,cutCorners)
self.doCloseNodes(currentSquare,closeNodes)
#--------------------probe the program module----------------------------------------
#Make The Array
array = createArray(20,20)
#array = createArray(7,5)

#Make Walls

array.makeClosed(3,1)
array.makeClosed(3,2)
array.makeClosed(3,3)

#Make Start And End
array.makeStart(1,4)
array.makeEnd(12,11)
#array.makeStart(1,2)
#array.makeEnd(5,2)

#[\/]---(Find The Path)

array.findPath(0)
array.traceBack()

#[/\]---(Find The Path)

#Print The Path
printArray(array.array)



you can check this another example used pygame
http://arainyday.se/projects/python/AStar/
good luck

saladin

31-05-2007 10:52:50

ok saladin here a the code
...


Although I've implemented my own a while ago, your help is definitely appreciated. I'm sure I can learn something here.