# 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)

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

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

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.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

olist = list(self.openlist)
olist.sort(key=lambda x: x.f, reverse=False)

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.