diff options
| -rw-r--r-- | main.py | 4 | ||||
| -rw-r--r-- | pathfinding.py | 155 |
2 files changed, 157 insertions, 2 deletions
@@ -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] |