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)
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)
Thanks for the blend
Did you explain how to use it in the blend?
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
could this be used for small spherical planets?
yes it is possible, how to do it would be up to you.
i was thinking more along the lines of a maze on a sphere.