A* search algorithm ( Node based )


(edderkop) #1

here is a “A* search algorithm” not the fastest around but it gets the job done.

i created it to generate roads on my random maps.


http://15b.dk/blendfiles/astar.blend

(press spacebar to generate new map)


(guramarx) #2

Thanks for the blend


(Lostscience) #3

Did you explain how to use it in the blend?


(edderkop) #4

I have made a few optimizations and did a little cleanup of the code

import numpy as np

def Dist(v1, v2):
    a = np.array([v1.x,v1.y,v1.z])
    b = np.array([v2.x,v2.y,v2.z])
    x = a - b
    return np.sqrt(x.dot(x))


class Node:
    def __init__(self,**kw):
        self.key = 0
        self.x = 0
        self.y = 0
        self.z = 0
        self.parent = None
        self.h = 0
        self.f = 0
        self.g = 0
        self.neighbour = {}
        self.active = True # for doors and other moving obstacles
        #self.set = None
        
        for arg in kw:
            if arg in vars(self):
                if type(self[arg]) == dict:
                    self[arg].update(kw[arg])
                else:
                    self[arg] = kw[arg] 
            
    def __getitem__(self, key):
        return getattr(self, key)
    
    def __setitem__(self, key, value):
        setattr(self, key, value)
        
    def add_neighbour(self,key,value=10):
        self.neighbour[key] = value

class NodeTree:
    def __init__(self):
        self.tree = {}
        
    def __len__(self):
        return len(self.tree)
    
    def __iter__(self):
        for n in self.tree:
            yield self.tree[n]
        return self
    
    def keys(self):
        for n in self.tree:
            yield n
        return self
    
    def __next__(self):
        return self
    
    def add(self,key,data):
        self.tree[key] = data
        
    def remove(self,key):
        if key in self.tree:
            del self.tree[key]
    
    def get(self,key):
        if key in self.tree:
            return self.tree[key]
        return None
            
    def exist(self,key):
        if key in self.tree:
            return True
        return False
    
    
    
class astar:
    def __init__(self):
        self.start = None
        self.target = None
        
    def search(self,start,target,grid):
        self.openlist = NodeTree()
        self.closedlist = NodeTree()
        self.start = grid.get(start)
        self.target = grid.get(target)
        path = []
        
        if start in grid.keys() and target in grid.keys():
            s = self.start
            t = self.target
            node = Node(x=s.x,y=s.y,z=s.z,key=start)
            node.h = Dist(s,t)
            node.f = node.h + node.g
            
            self.openlist.add(start,node)      
           
            dist = 0
            current = grid.get(start)

            while len(self.openlist)>0:
                for neighbour in current.neighbour:
                    neigh = grid.get(neighbour)
                    gcost = current.neighbour[neighbour]
                    if neigh.active:
                        if not self.closedlist.exist(neighbour):    
                            if neigh:
                                if neighbour == target:
                                    ne = grid.get(neighbour)
                                    ne.parent = current
                                    path = [ne]
                                    self.closedlist.add(current.key,current)
                                    self.closedlist.add(ne.key,ne)
                                    self.openlist.remove(current.key)
                                    self.openlist.remove(ne.key)
                                    break
                                
                                if neighbour in self.openlist.keys():
                                    tmp = grid.get(neighbour)
                                    if tmp.parent:
                                        if tmp.parent.g > current.g:
                                            tmp.parent = current
                                else:
                                    ne = grid.get(neighbour)
                                    node = Node(x=ne.x,y=ne.y,z=ne.z,key=neighbour)
                                    node.neighbour = ne.neighbour
                                    node.parent = current
                                    node.h = Dist(ne,t)
                                    node.g = gcost + current.g
                                    node.f = node.h + node.g
                                    self.openlist.add(neighbour,node)  
                
                olist = list(self.openlist)
                olist.sort(key=lambda x: x.f, reverse=False)
                
                self.closedlist.add(current.key,current)
                self.openlist.remove(current.key)
                
                if len(olist)>0:
                    current = olist[0]
            
            if self.target.key in self.closedlist.tree:
                key = self.closedlist.tree[self.target.key ].key       

                while True:
                    parent = self.closedlist.tree[key].parent
                    
                    if parent:
                        key = parent.key
                        path.append(parent)
                        if key == self.start.key:
                            break
                    else:
                        break
        return path            

here is a working demo.
(a entity roaming a dungeon )

filesize: 11.5 mb
http://15b.dk/blendfiles/astar-kdtree.blend


(Lostscience) #5

could this be used for small spherical planets?


(edderkop) #6

yes it is possible, how to do it would be up to you.


(Lostscience) #7

i was thinking more along the lines of a maze on a sphere.