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?
SiWi
27-05-2007 09:35:26
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?
pocho
30-05-2007 20:05:41
#;===================================================================
#;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)
saladin
31-05-2007 10:52:50
ok saladin here a the code
...