Okay, I am finally not rushed right now! Nice and calm, and able to give explanations! 
Anyway, I reduced the amount of scripts from 5 to 3. I merged 3 of the scripts into 1, which is the main AI script, then there is the pathfinding.py and the slab.py. I am also looking into implementing binary heaps, as that will increase the speed. The speed right now is manageable, it takes 3-4 fps to update, and it updates every few seconds, so its not bad, except the freeze problem…
On the freeze problem, I figured out what is causing it! It happens when it looks for a path and cannot find one. The problem is under the pathfinding.py script. The fps drops about 100 for around 1 second, which if you’re running it on a game that runs at a normal 30 fps…
Anyone have any ideas on how to fix it? I am at a standstill from this problem. Any experienced python coders feel nice?
I started learning python about 1 month ago, so I enjoyed trying to figure this out, but it reached the end of its excitement.
oh, and btw thanks for the tip andrew-101!
I attached the problem code, and the blend. I removed the AI functions from the AI script, so its just pathfinding.
EDIT: I might have attached the wrong blend… :o
EDIT: I think the problem lay in line 157 - 170. I also posted the code in PasteAll.org for easier viewing.
#################################
### ------ Pathfinding ------ ###
#################################
### Copyright 2009 Chase Moskal!
# This contains the PATHFINDER class,
# which contains classes for NODE and PATH.
# It's for A* pathfinding.
###
INIT = 0
class PATHFINDER:
import math
class NODE:
def __init__(self, PATHFINDER, position, adjacentpos):
self.PATHFINDER = PATHFINDER
self.position = position
self.adjacentpos = adjacentpos
self.parent = None
self.adjacent = []
self.G = 0
self.H = 0
self.F = 0
def fastEvaluate(self, startNode, targetNode):
PATHFINDER = self.PATHFINDER
G = PATHFINDER.getManhattanDistance(startNode.position, self.position)
H = PATHFINDER.getManhattanDistance(self.position, targetNode.position)
F = G+H
self.G = G
self.H = H
self.F = F
return F, G, H
class PATH:
def __init__(self, startpos, targetpos, startNode, targetNode, OPEN, CLOSED):
self.OPEN = OPEN
self.CLOSED = CLOSED
self.startpos = startpos
self.targetpos = targetpos
self.nodes = []
self.nodes.append(targetNode)
node = targetNode
run = 1
while run == 1:
if node.parent:
node = node.parent
self.nodes.append(node)
else:
run = 0
self.nodes.reverse()
self.path = self.getPath()
def getPath(self):
path = []
path.append(self.startpos)
for node in self.nodes:
path.append(node.position)
path.append(self.targetpos)
return path
# Compiles the adjacents for each node in a list.
def compileAdjacents(self, nodes):
for node in nodes:
adjacent = []
for targetnode in nodes:
if targetnode.position in node.adjacentpos:
adjacent.append(targetnode)
node.adjacent = adjacent
# Evaluates vertinfolist from string form.
def stringToNodemesh(self, string):
# Converting to unix flavor...
string = string.replace("
", "
")
nodemesh = []
lines = string.split("
")
for line in lines:
if line:
try:
vertinfo = eval(line)
nodemesh.append(vertinfo)
except:
pass
return nodemesh
# Takes in a vertinfolist and converts it into a list of node objects
def NodemeshToNodes(self, nodemesh):
nodes = []
for vertinfo in nodemesh:
position = vertinfo[0]
adjacentpos = vertinfo[1]
node = self.NODE(self, position, adjacentpos)
nodes.append(node)
self.compileAdjacents(nodes)
return nodes
def makeNodes(self, string):
nodemesh = self.stringToNodemesh(string)
nodes = self.NodemeshToNodes(nodemesh)
return nodes
def cleanNodes(self, nodes):
for node in nodes:
node.parent = None
node.G = 0
node.H = 0
node.F = 0
def getManhattanDistance(self, A, B):
math = self.math
X = abs(A[0] - B[0])
Y = abs(A[1] - B[1])
Z = abs(A[2] - B[2])
D = X+Y+Z
return D
# Returns the nearest node, given a position and a list of nodes.
def getNearestNode(self, position, nodes):
best = []
for node in nodes:
if best:
bestnode = best[0]
bestdistance = best[1]
distance = self.getManhattanDistance(position, node.position)
if distance < bestdistance:
best = [node, distance]
else:
distance = self.getManhattanDistance(position, node.position)
best = [node, distance]
return best[0]
# Returns the node with the best F score: doesn't evaluate F.
def getBestF(self, nodes):
best = []
for node in nodes:
if best:
bestnode = best[0]
bestF = best[1]
if node.F < bestF:
best = [node, node.F]
else:
best = [node, node.F]
return best[0]
########################################
###### ------ fastFindPath ------ ######
########################################
# Given a list of nodes, start position, target position, and
# max number of steps, this method will return a path object.
# This will usually find a path faster, but at the expense of accuracy.
def fastFindPath(self, nodes, start, target, steps=200):
self.cleanNodes(nodes)
PATHFOUND = 0
startNode = self.getNearestNode(start, nodes)
targetNode = self.getNearestNode(target, nodes)
OPEN = [startNode]
CLOSED = []
for i in range(steps):
# Get node in OPEN with lowest F
currentNode = self.getBestF(OPEN)
# Switch it to CLOSED
OPEN.remove(currentNode)
CLOSED.append(currentNode)
# For each adjacent node
adjacentNodes = currentNode.adjacent
for node in adjacentNodes:
# If it's not in CLOSED
if not (node in CLOSED):
# Get F Score
F, G, H = node.fastEvaluate(startNode, targetNode)
if not (node in OPEN):
node.parent = currentNode
OPEN.append(node)
else:
if node.G < currentNode.G:
# No change to parent, and already in the OPEN list.
pass
else:
node.parent = currentNode
# Stop when we found the target node or if there are no more open nodes.
if targetNode in OPEN:
targetNode.parent = currentNode
PATHFOUND = 1
break
if not OPEN:
break
if PATHFOUND:
path = self.PATH(start, target, startNode, targetNode, OPEN, CLOSED)
return path
else:
return 0
Pathfinder = PATHFINDER
Attachments
AStar Pathfinding.blend (273 KB)
