How can we refine this path search method to make group movement more elegant? I'm trying to make a RTS-style game, using a 2d tiled gameworld. I have implemented an A* pathfinding algorithm which works well enough for single units. I've also make some functionality to make agents walk around other agents they stumble across on their way.
Here is some of my code:
def move(self, agent, clickbox, nogolist):
impassable = []
impassable.extend(nogolist)
mapinfo1 = MapInfo(self.map_layout.finalsize,self.map_layout.finalsize,impassable)
graph, self.nodes = self.make_graph(mapinfo1)
paths = AStarGrid(graph)
for c in self.map_layout.all_map_objects:
if clickbox.box.collidepoint(c.checkpoint):
path = []
if len(agent.travel_list) > 1:
v = agent.travel_list[1]
start = self.nodes[v[0]][v[1]]
elif len(agent.travel_list) == 1:
start = self.nodes[agent.grid_pos[0]][agent.grid_pos[1]]
end = self.nodes[c.gridnumber[0]][c.gridnumber[1]]
path = paths.search(start, end)
try:
agent.target = self.convert_path(path)
agent.travel_list = self.waypoints((agent.grid_pos[0],agent.grid_pos[1]), path)
except:
print 'road error'
When one or more agents are selected and the player right-clicks somewhere, self.move gets called on each agent individually, they are at this point still ignorant of other agents positions. The next part is where I try to have agents not walk over each other, or just stop if 'travel_list' only contains one more step, and another agent occupies it.
if not len(self.traveling_agents) == 0:
for a, b in combinations(self.agent_list, 2):
self.resolve(a, b, self.nogolist)
self.resolve(b, a, self.nogolist)
def resolve(self, a, b, nogolist):
try:
if len(a.travel_list) > 1 and b.travel_list[0] == a.travel_list[-1]:
a.travel_list = a.travel_list[:-1]
a.target = a.target[:-1]
if a.travel_list[1] == b.travel_list[0]:
self.traveling_agents.remove(a)
elif len(a.travel_list) > 1 and b.travel_list[0] == a.travel_list[1]:
path = []
go = a.travel_list[0]
goal = a.travel_list[-1]
impassable = []
impassable.append(b.travel_list[0])
impassable.extend(nogolist)
mapinfo1 = MapInfo(self.map_layout.finalsize,self.map_layout.finalsize,impassable)
graph, self.nodes = self.make_graph(mapinfo1)
paths = AStarGrid(graph)
start = self.nodes[go[0]][go[1]]
end = self.nodes[goal[0]][goal[1]]
path = paths.search(start, end)
a.target = self.convert_path(path)
a.travel_list = self.waypoints((go[0],go[1]), path)
del impassable
except: a.stop()
This works reasonably well for solo agents encountering other stationary solo agents. But when moving in a group towards a common target, this method falls way short of what would be desired. What can we do to achieve smoother group movement like what is seen in some of those old school RTS games?
For some additional insight on my code, check my previous entry on implementing the A-star search algorithm: https://stackoverflow.com/questions/14390458/how-to-structure-an-adjacency-list-for-this-a-program/