I'm working on a step-time strategy game (not sure if that's the proper term, but it moves in discrete time steps, about 4 frames, before pausing for input) with positively monstrous pathfinding calculations. I've solved the biggest of my problems already, but there is one algorithm that causes significant slowdown, and I'm sure it could be optimized, but I'm not sure how best to do that because my case has a unique property that isn't covered in any A* optimizations I've researched. (Or perhaps I'm just not thinking about it the right way.)
My game allows the creation of formations, which are defined as positional groupings of units relative to a leader. It's extremely important to the gameplay that these formations keep their shape as best as possible while balancing the need to move smoothly through any narrow spaces that constrict their shape. The algorithm I'm asking about now is responsible for choosing a path for the leader of the formation that (1) avoids unnecessarily traveling into narrow spaces and (2) always allows a certain amount of clearance between itself and obstacles, whenever those things are possible. Where I have found typical clearance-based approaches to A* fall short in addressing my problem is, ultimately, the leader will choose a path that goes through areas even just 1 space wide if there is no other option. In other words, I can't have the algorithm disregard those, but I can't have it explore those nodes either until it has explored the entirety of the rest of the map.
Here is my basic test map for this. The 5 green symbols at the top-left represent a formation led by the V in the center. The yellow circle at the center of the map is the goal.
Here is the solution that a regular A* would give, finding the shortest path:
Here is the solution I want (and the algorithm already does this, just slowly)
Here is the Python code that achieves this -- I know there are going to be some questions about what the vectors are and all of that, but basically, this is just a typical A* setup with the addition of a "c_cost," which is 0 if the given node has all the space that it wants (as defined by optimal_area), or 2 ^ the number of spaces missing from the amount of space we want.
def leader_pathfind(leader, going_to, treat_passable = [], treat_impassable = []):
""" Seek the shorest path that attempts to avoid obstacles at a distance equal to that of the furthest member in the formation """
global game_width
global game_height
global diagonal_movement_cost
global formation_dict
at_now = leader['position']
treat_passable.append(going_to) # Prevents indefinite hanging while rerouting if an obstacle has moved to the destination
if at_now == going_to:
return []
formation_obj = formation_dict[leader['id']]
vectors = formation_obj.get_formation_vectors()
max_dimension = 0
for vector in vectors:
for axis in vector:
if abs(axis) > max_dimension:
max_dimension = abs(axis)
optimal_area = basic_pow(max_dimension * 2 + 1, 2)
def clear_area(position):
""" Check in square rings around the position for obstacles/edges of map, then return the total area that is passable
within the square that first hits an obstacle/edge of map """
if not position_is_passable(position, treat_passable = treat_passable, treat_impassable = treat_impassable):
return sys.maxint
distance = 0
hit_obstacle = False
while not hit_obstacle:
distance += 1
corner_a = (position[0] - distance, position[1] - distance)
corner_b = (position[0] + distance, position[1] + distance)
outline = rectline(corner_a, corner_b)
for point in outline:
if not within_game_bounds(point):
hit_obstacle = True
break
elif not position_is_passable(point, treat_passable = treat_passable, treat_impassable = treat_impassable):
hit_obstacle = True
break
elif distance == max_dimension: # We have all the space we want, no need to compute further
hit_obstacle = True
break
tent_area = rectfill(corner_a, corner_b)
area = 0
for point in tent_area:
if within_game_bounds(point):
if position_is_passable(point, treat_passable = treat_passable, treat_impassable = treat_impassable):
# Some stray diagonals may get counted here occasionally, but that should be acceptable for this purpose
area += 1
return area
def c(position): # c_cost is in terms of clear area relative to the optimal clearance
area = clear_area(position)
c_cost = 0 if area >= optimal_area else basic_pow(2, abs(area - optimal_area)) # Cost grows exponentially by powers of 2 for each point less than the optimal area
return c_cost
# Traditional A* #
def h(position):
return basic_distance(position, going_to) / 100.0
f_dict = {at_now: h(at_now)}
g_dict = {at_now: 0}
open_set = [at_now]
closed_set = []
get_last = {}
found_path = False
current = at_now
while len(open_set) > 0:
current = open_set[0]
for op in open_set:
if op in f_dict.keys():
if f_dict[op] < f_dict[current]:
current = op
open_set.remove(current)
closed_set.append(current)
if current == going_to:
found_path = True
break
for neighbor in neighbors(current, treat_passable = treat_passable, treat_impassable = treat_impassable):
if neighbor in closed_set:
continue
if not neighbor in open_set:
open_set.append(neighbor)
movement_cost = diagonal_movement_cost if diagonally_adjacent(current, neighbor) else 1
tent_g = g_dict[current] + movement_cost
tent_f = tent_g + c(neighbor) + h(neighbor)
if not neighbor in f_dict.keys():
g_dict[neighbor] = tent_g
f_dict[neighbor] = tent_f
get_last[neighbor] = current
else:
if tent_f < f_dict[neighbor]:
g_dict[neighbor] = tent_g
f_dict[neighbor] = tent_f
get_last[neighbor] = current
if found_path:
path = [going_to]
current = going_to
while current != at_now:
current = get_last[current]
path.append(current)
path.reverse()
path.pop(0)
return path
else:
write_log('leader_pathfind: could not find a path from ' + str(at_now) + ' to ' + str(going_to))
return FalseJump Point Search, which I've used elsewhere, relies on the assumption of a uniform-cost grid, so I believe I need to rely on abstracting my map down to a smaller number of abstract nodes, and I'm at a loss for how I would do that for this case. What I've read on using abstract nodes rely on things like identifying entrances/exits from abstract nodes, but that won't be useful if the algorithm chooses a node with acceptable entrance/exit points but lots of obstacles in the middle. Here is an arbitrarily chosen slice of the map with the correct path:
Broken up into abstract 5x5 nodes, I am failing to see a pattern I could rely on to give the algorithm the information it needs, especially since a crucial part of the path rests right on the right edge of the two leftmost abstract nodes. To know that this is the correct path, i.e. has sufficient clearance, it would need to calculate the clearance from that edge, dipping into the nodes in the middle. So I can't choose nodes that will be helpful without already having the information that I need the nodes to speed up the calculation of.
That's as far as I've gotten with my thought process. Can anyone make any suggestions, general or specific? Thanks in advance
So maybe I can at least help start the discussion. 
