Pathfiding for groups of agents

Question

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/

Answer 1

I suggest you implement some flocking behavior principles on the movement method. If you don't know about flocking algorithms, here are some useful links and tutorials:

http://harry.me/blog/2011/02/17/neat-algorithms-flocking/

http://www.lalena.com/AI/Flock/

The trick would be the following:

1- The movement and its direction each frame will be controlled by a movement vector.

2- The A* pathfinder will return an array of waypoints the entity needs to go thru so it will end up at the desired location without running into walls and whatnot.

3- This vector is the resulting sum of other vectors generated by the flocking algorithm. The some common vectors are cohesion, separation and alignment along with a vector pointing to the current waypoint (heading).

This is not a silver bullet, though. The original flocking theory doesn't account for walls or obstacles. Neither implementing pathfinding nor combining it with flocking is as trivial as it might seem.