summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--main.py4
-rw-r--r--pathfinding.py155
2 files changed, 157 insertions, 2 deletions
diff --git a/main.py b/main.py
index ab92ce3..e980fb3 100644
--- a/main.py
+++ b/main.py
@@ -11,7 +11,7 @@ import nogui as gui # might be overridden later.
import stats
from subscriber import EnhancingSubscriber
from interval_utils import *
-from strategy import *
+from pathfinding import PathfindingTesterStrategy
import time
class Clock:
@@ -110,7 +110,7 @@ c.player.nick=nick
gui.set_client(c)
# initialize strategy
-strategy = Strategy(c, gui)
+strategy = PathfindingTesterStrategy(c, gui)
autorespawn_counter = 60
diff --git a/pathfinding.py b/pathfinding.py
new file mode 100644
index 0000000..9386275
--- /dev/null
+++ b/pathfinding.py
@@ -0,0 +1,155 @@
+import math
+
+
+# A* code taken and adapted from https://gist.github.com/jamiees2/5531924
+
+class Node:
+ def __init__(self,value,point,point_in_grid):
+ self.value = value
+ self.point = point
+ self.point_in_grid = point_in_grid
+ self.parent = None
+ self.H = 0
+ self.G = 0
+
+ def move_cost(self,other):
+ # assert other in siblings(self,grid). otherwise this makes no sense
+ return distance(self, other) + (self.value + other.value)/2
+
+def siblings(point,grid):
+ x,y = point.point_in_grid
+ links = [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)]]
+ return [link for link in links if link.value != None]
+
+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)+")")
+ openset = set()
+ closedset = set()
+
+ current = start
+ openset.add(current)
+
+ while openset:
+ #Find the item in the open set with the lowest G + H score
+ current = min(openset, key=lambda o:o.G + o.H)
+
+ #If it is the item we want, retrace the path and return it
+ if current == goal:
+ path = []
+ while current.parent:
+ path.append(current)
+ current = current.parent
+ path.append(current)
+ return path[::-1]
+
+ openset.remove(current)
+ closedset.add(current)
+
+ for node in siblings(current,grid):
+ if node in closedset:
+ continue
+
+ if node in openset:
+ #Check if we beat the G score
+ new_g = current.G + current.move_cost(node)
+ if node.G > new_g:
+ #If so, update the node to have a new parent
+ node.G = new_g
+ node.parent = current
+ else:
+ #If it isn't in the open set, calculate the G and H score for the node
+ node.G = current.G + current.move_cost(node)
+ node.H = distance(node, goal)
+
+ node.parent = current
+ openset.add(node)
+
+ raise ValueError('No Path Found')
+
+grid_radius=int(1100/30)*30
+grid_density=30
+
+class PathfindingTesterStrategy:
+ def __init__(self, c, gui):
+ self.c = c
+ self.path = None
+ self.gui = gui
+
+ def build_grid(self):
+ grid = [[0 for x in range(int(2*grid_radius//grid_density+1))] for x in range(int(2*grid_radius//grid_density+1))]
+
+ interesting_cells = list(filter(lambda c : not (c.is_food or c in self.c.player.own_cells), self.c.player.world.cells.values()))
+
+ 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))
+ dist_sq = relpos[0]**2 + relpos[1]**2
+ if dist_sq < cell.size**2 *3:
+ 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
+
+ if (gridx in [0,len(grid)-1] or gridy in [0, len(grid[gridx])-1]):
+ val = None
+ else:
+ val = grid[gridx][gridy]
+
+ grid[gridx][gridy] = Node(val, (self.c.player.center[0]+x,self.c.player.center[1]+y), (gridx, gridy))
+
+ return grid
+
+ 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()
+
+ path = aStar(grid[int(grid_radius/grid_density)][int(grid_radius/grid_density)], grid[goalx][goaly], grid)
+ return path
+
+ def path_is_valid(self, path):
+ interesting_cells = list(filter(lambda c : not (c.is_food or c in self.c.player.own_cells), self.c.player.world.cells.values()))
+ for node in path:
+ for cell in interesting_cells:
+ relpos = (cell.pos.x - node.point[0], cell.pos.y - node.point[1])
+ dist_sq = relpos[0]**2 + relpos[1]**2
+ if dist_sq < cell.size**2 *2:
+ return False
+
+ return True
+
+ def process_frame(self):
+ if self.gui.marker_updated[0]:
+ self.gui.marker_updated[0]=False
+
+ self.path = self.plan_path()
+ for node in self.path:
+ print (node.point_in_grid)
+ print("="*10)
+
+
+ for (node1,node2) in zip(self.path,self.path[1:]):
+ self.gui.draw_line(node1.point, node2.point, (0,0,0))
+
+ if self.path:
+ relx, rely = self.path[0].point[0]-self.c.player.center.x, self.path[0].point[1]-self.c.player.center.y
+ if relx*relx + rely*rely < (2*grid_density)**2:
+ self.path=self.path[1:]
+
+ if self.path and not self.path_is_valid(self.path):
+ print("recalculating!")
+ self.path = self.plan_path()
+
+ if self.path:
+ return self.path[0].point
+ return self.gui.marker[0]