summaryrefslogtreecommitdiff
path: root/pathfinding.py
diff options
context:
space:
mode:
Diffstat (limited to 'pathfinding.py')
-rw-r--r--pathfinding.py80
1 files changed, 47 insertions, 33 deletions
diff --git a/pathfinding.py b/pathfinding.py
index c126559..61f32a8 100644
--- a/pathfinding.py
+++ b/pathfinding.py
@@ -42,16 +42,37 @@ class Graph:
self.blobs = blobs
+class Grid:
+ def __init__(self, origin, radius, density, default=None):
+ self.radius = radius
+ self.density = density
+ self.origin = origin
+ self.data = [[default for x in range(int(2*radius//density+1))] for x in range(int(2*radius//density+1))]
+ def getpos(self, x, y = None):
+ if y == None:
+ x,y=x[0],x[1]
+ return ( int(x-self.origin.x+self.radius)//self.density, int(y-self.origin.y+self.radius)//self.density )
+
+ def at(self, x, y = None):
+ xx,yy = self.getpos(x,y)
+ return self.data[xx][yy]
+
+ def set(self, val, x, y = None):
+ xx,yy = self.getpos(x,y)
+ self.data[xx][yy] = val
+
+ def is_border(self, x, y):
+ xx,yy = self.getpos(x,y)
+ return (xx in [0,len(self.data)-1] or yy in [0, len(self.data[xx])-1])
# A* code taken and adapted from https://gist.github.com/jamiees2/5531924
class Node:
- def __init__(self,value,point,point_in_grid, is_in_wormhole_plane, graph, cell):
+ def __init__(self,value,point, is_in_wormhole_plane, graph, cell):
self.value = value
self.point = point
- self.point_in_grid = point_in_grid
self.parent = None
self.H = 0
self.G = 0
@@ -60,7 +81,7 @@ class Node:
self.find_near_wormholes(50)
def find_near_wormholes(self, radius):
- self.near_wormholes = list(filter(lambda blob : (self.point - blob.point).len() < radius, self.graph.blobs))
+ self.near_wormholes = [] # list(filter(lambda blob : (self.point - blob.point).len() < radius, self.graph.blobs))
def move_cost(self,other):
dist = distance(self, other)
@@ -72,15 +93,14 @@ class Node:
return max(dist, 5*dist - 500)
def siblings(self):
- x,y = self.point_in_grid
- links = [self.graph.grid[d[0]][d[1]] for d in [(x-1, y),(x-1,y-1),(x,y - 1),(x+1,y-1),(x+1,y),(x+1,y+1),(x,y + 1),(x-1,y+1)]]
+ x,y = self.graph.grid.getpos(self.point)
+ links = [self.graph.grid.data[d[0]][d[1]] for d in [(x-1, y),(x-1,y-1),(x,y - 1),(x+1,y-1),(x+1,y),(x+1,y+1),(x,y + 1),(x-1,y+1)]]
return [link for link in links if link.value != None] + self.near_wormholes
def distance(point,point2):
return math.sqrt((point.point[0] - point2.point[0])**2 + (point.point[1]-point2.point[1])**2)
-def aStar(start, goal, grid):
- print("aStar("+str(start.point)+"="+str(start.point_in_grid)+", "+str(goal.point)+"="+str(goal.point_in_grid)+")")
+def aStar(start, goal):
openset = set()
closedset = set()
@@ -133,52 +153,46 @@ class PathfindingTesterStrategy:
self.path = None
self.gui = gui
- def build_grid(self):
+ def build_graph(self):
graph = Graph(None, [])
- graph.blobs = [ Node(0, c.pos, Vec( int((c.pos.x - self.c.player.center.x + grid_radius) // grid_density), int((c.pos.y - self.c.player.center.y + grid_radius) // grid_density) ), True, graph, c) for c in self.c.world.cells.values() if c.is_food ]
+ graph.blobs = [ Node(0, c.pos, True, graph, c) for c in self.c.world.cells.values() if c.is_food ]
- graph.grid = [[0 for x in range(int(2*grid_radius//grid_density+1))] for x in range(int(2*grid_radius//grid_density+1))]
+ graph.grid = Grid(self.c.player.center, grid_radius, grid_density, 0)
interesting_cells = list(filter(lambda c : not (c.is_food or c in self.c.player.own_cells), self.c.player.world.cells.values()))
+
+ x_range = range( int(self.c.player.center.x-grid_radius), int(self.c.player.center.x+grid_radius+1), grid_density)
+ y_range = range( int(self.c.player.center.y-grid_radius), int(self.c.player.center.y+grid_radius+1), grid_density)
for cell in interesting_cells:
- for x in range(-grid_radius,grid_radius+1,grid_density):
- gridx = (x+grid_radius) // grid_density
- for y in range(-grid_radius,grid_radius+1,grid_density):
- gridy = (y+grid_radius) // grid_density
-
- relpos = (cell.pos.x - (x+self.c.player.center.x), cell.pos.y - (y+self.c.player.center.y))
+ for x in x_range:
+ for y in y_range:
+ relpos = (cell.pos.x - x, cell.pos.y - y)
dist_sq = relpos[0]**2 + relpos[1]**2
if dist_sq < cell.size**2 *3:
- graph.grid[gridx][gridy] += 100000000
-
- for x in range(-grid_radius,grid_radius+1,grid_density):
- gridx = (x+grid_radius) // grid_density
- for y in range(-grid_radius,grid_radius+1,grid_density):
- gridy = (y+grid_radius) // grid_density
+ graph.grid.set(100000000, x,y)
- if (gridx in [0,len(graph.grid)-1] or gridy in [0, len(graph.grid[gridx])-1]):
+ for x in x_range:
+ for y in y_range:
+ if graph.grid.is_border(x,y):
val = None
else:
- val = graph.grid[gridx][gridy]
+ val = graph.grid.at(x,y)
- graph.grid[gridx][gridy] = Node(val, self.c.player.center+Vec(x,y), Vec(gridx, gridy), False, graph, None)
+ graph.grid.set(Node(val, Vec(x,y), False, graph, None), x,y)
for blob in graph.blobs:
- blob.find_near_wormholes(200)
+ blob.find_near_wormholes(50)
- return graph.grid
+ return graph
def plan_path(self):
- goalx = int((self.gui.marker[0][0] - self.c.player.center[0] + grid_radius)/grid_density)
- goaly = int((self.gui.marker[0][1] - self.c.player.center[1] + grid_radius)/grid_density)
-
- grid = self.build_grid()
+ graph = self.build_graph()
- path = aStar(grid[int(grid_radius/grid_density)][int(grid_radius/grid_density)], grid[goalx][goaly], grid)
+ path = aStar(graph.grid.at(self.c.player.center), graph.grid.at(self.gui.marker[0]))
return path
def path_is_valid(self, path):
@@ -198,7 +212,7 @@ class PathfindingTesterStrategy:
self.path = self.plan_path()
for node in self.path:
- print (node.point_in_grid)
+ print (node.point)
print("="*10)