#g.nodes is a DICTIONARY#g.node.values() are CLASSES called 'node'print ""print ""print "_________________________________"import Blenderimport GameLogic as g##Generate the Node TreepathTree = Blender.Mesh.Get("Path") #'Path' is the meshdef dist(a,b): return ((a[0]-b[0])**2+(a[1]-b[1])**2+(a[2]-b[2])**2)**.5class node: #each node is a class! def __init__(self,coord): #containing: self.neighbors = {} #empty dictionary self.distance = 0 self.coord = coord self.parent = 0def generateTree(pathTree): nodes = {} # a dictionary, not to be confused with class 'node' for v in pathTree.verts: nodes[v.index] = node(v.co) #adds a _class_ 'node' to the dictionary 'nodes' for edge in pathTree.edges: distance = dist(edge.v1.co , edge.v2.co) nodes[edge.v1.index].neighbors[edge.v2.index] = distance #appends a new key:value pair in the dictionary 'neighbors' nodes[edge.v2.index].neighbors[edge.v1.index] = distance return nodes#############if not hasattr(GameLogic,"nodes"): g.nodes = generateTree(pathTree)####################################################################################################### all of the above needs to be separated into a text module. (Cannot import blener in realtime) #######################################################################################################con = g.getCurrentController()own = con.getOwner()destination = g.getCurrentScene().getObjectList()["OBtrackme"].getPosition()def getClosestTo(pos): #get the closest node to pos closestNode = 0 closestPos = dist(pos,g.nodes[closestNode].coord) for TestNode in g.nodes: if dist(pos , g.nodes[TestNode].coord) < closestPos: closestNode = TestNode closestPos = dist(pos , g.nodes[TestNode].coord) return g.nodes[closestNode] #returns the closest nodeg.startnode = getClosestTo(own.getPosition()) #get the closest node to botg.endnode = getClosestTo(destination) #get closest node to destinationg.cuttestnode = 0class finder: #just in case the variables need to be global def __init__(self): self.open = [] self.closed = [] self.current = g.startnode #startnode is determined by closest to AI self.current_backtrack = g.endnode self.path = []f = finder()def calc_pathcost(end,start): #determines the cost of the pre-determined path between two points pathcost = 0.0 g.cuttestnode = end while 1: n = dist(g.cuttestnode.coord , g.cuttestnode.parent.coord) pathcost += n #adds all the distances following the path so far cur_node = g.cuttestnode.parent if g.cuttestnode == end: break return pathcostdef shortcut_to(node): #see if there is a better path to the current node from a node aleady in the closed list for testneighbor in node.neighbors: if g.nodes[testneighbor] in f.closed: pathcost = calc_pathcost(node , g.nodes[testneighbor]) if dist(node.coord , g.nodes[testneighbor].coord) < pathcost: print " \t \t shortcut taken" node.parent = g.nodes[testneighbor] else: passdef find_Nextnode(cur_node,openlist): Nextnode = 0 F = 999999 for neighbor in cur_node.neighbors:#neighbor is an int if g.nodes[neighbor] in openlist: G = cur_node.neighbors[neighbor] #returns the VALUE of the key:value(m_index:dist) pair of the dictionary "neighbors" H = dist(destination , g.nodes[neighbor].coord) if (G+H) < F: Nextnode = neighbor F = G + H return g.nodes[Nextnode]##### SOLVEwhile f.current != g.endnode: ############## NEIGHBORS IS A DICTIONARY!!! {mesh vertex index: distance from current node} print "current: ", f.current.coord if f.current not in f.closed: f.closed.append(f.current) #Add the current node to the CLOSED LIST! if f.current in f.open: f.open.remove(f.current) deadend = 1 for neighbor in f.current.neighbors: if(g.nodes[neighbor]) not in f.closed: deadend = 0 if (g.nodes[neighbor]) not in f.open: f.open.append(g.nodes[neighbor]) #ADD NEIGHBORS TO THE OPEN LIST if deadend: f.current = f.current.parent continue Nextnode = find_Nextnode(f.current,f.open) #returns class instance Nextnode.parent = f.current #assign the current node as the next node's parent f.current = Nextnode #move on to the next node as the current node shortcut_to(f.current)###############################add the nodes to the pathif f.current == g.endnode: print " -----HIT THE END!------ " iterb = 1 while f.current_backtrack != g.startnode: #f.current_backtrack starts at end iterb += 1 if iterb > 20: print "break" break f.path.append(f.current_backtrack) print "appened ",f.current_backtrack.coord,"to the path." f.current_backtrack = f.current_backtrack.parent #go to the next node