I am currently trying to fix my pathfinding system in my game. The A pathfinding python code is super slow, considering it has to calculate thousands of nodes each time for my grid. My grid is stored in a dictionary that has the positions of all of the walls and obstacles. Are there any ways I could speed this up signifigantly? Here is my algorithm:
def findpath_subgrid(self, start, end):
self.subgrid_cache.clear()
start_subgrid = (start[0] // self.subgrid_size, start[1] // self.subgrid_size)
end_subgrid = (end[0] // self.subgrid_size, end[1] // self.subgrid_size)
if start_subgrid == end_subgrid:
return self.find_path(start, end)
else:
with self.lock:
if start_subgrid in self.subgrid_cache:
return self.subgrid_cache[start_subgrid]
else:
path = self.find_path(start, end)
self.subgrid_cache[start_subgrid] = path
return path
def heuristic(self, a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def find_path(self, start, end):
queue = []
heapq.heappush(queue, (0, start))
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0
while queue:
current = heapq.heappop(queue)[1]
if current == end:
break
for next in self.adjacent_cells(current):
new_cost = cost_so_far[current] + self.cost(current, next)
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost + self.heuristic(end, next)
heapq.heappush(queue, (priority, next))
came_from[next] = current
return self.reconstruct_path(came_from, start, end)
def adjacent_cells(self, pos):
x, y = pos
results = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
results = filter(self.in_bounds, results)
results = filter(self.passable, results)
return results
def in_bounds(self, pos):
x, y = pos
return 0 <= x < 2000 and 0 <= y < 2000
def passable(self, pos):
return self.grid.get(pos) != 1 # check if the cell is not an obstacle using the new grid dictionary
def cost(self, current, next):
if self.grid.get(next) == 2:
return 1000 # high cost for cells with enemies
else:
return 1 # otherwise, the cost is 1
def heuristic(self, a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def reconstruct_path(self, came_from, start, goal):
current = goal
path = []
while current != start:
path.append(current)
current = came_from[current]
path.append(start)
path.reverse()
return path
I've tried subgrids, cache's but its still very very slow.
If a position is extracted from the queue, you do not need to consider them again in your search (this statement is true because you are working on a grid and using manhattan distance as heuristic function). I added a variable expanded_list to function find_path and adjacent_cells (my Python writing is not the best so you can write them better later). Also it would be better if you use a 2D array for holding your grid instead of a dictionary.
def find_path(self, start, end):
queue = []
heapq.heappush(queue, (0, start))
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0
expanded_list = {}
expanded_list[current] = False
while queue:
current = heapq.heappop(queue)[1]
expanded_list[current] = True
if current == end:
break
for next in self.adjacent_cells(current):
expanded_list[next] = False
new_cost = cost_so_far[current] + self.cost(current, next)
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost + self.heuristic(end, next)
heapq.heappush(queue, (priority, next))
came_from[next] = current
return self.reconstruct_path(came_from, start, end)
def adjacent_cells(self, pos, expanded_list):
x, y = pos
results = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
results = filter(self.in_bounds, results)
results = filter(self.passable, results)
results = filter(lambda pos:not(pos in expanded_list and expanded_list[pos]==True), results)
return results