AI Challenge: Pathfinding

Attribution Asterclix

As I wrote in the last AI challenge post, the basic starter bot is rather stupid and even the tutorial bots leave much to be desired. Coming from the tutorial your ants will be okay (ish) on the more open maps, but on the tighter maze maps will have real problems with the walls.

Our first requirement is some kind of way to figure out how to get the shortest route from A to B while avoiding water, and having a nod to speed as we have only 1000ms per turn (usually). The simplest solution here is to use the A* algorithm for finding those paths.

The wikipedia page on A* is fairly heavy reading but i found http://www.policyalmanac.org/games/aStarTutorial.htm to provide an excellent primer to what is going on with the open lists, closed lists, heuristics and so on.

So, lets apply this to our ants, fortunately the starter package provides some useful functions;

• ants.distance(start, target) provides a distance assuming no obstacles, we can use this for a heuristic
• ants.destination(start, direction) takes a co-ordinate and direction {n, e, s, w} and returns the co-ordinate of where that direction would take you
• AIM is a dictionary that compares {n, e, s, w} to the change in co-ordinates
• ants.passable(location) will test for water

The best thing about these functions is they take wrapping into account so if you are at (0,0) and travel west you could end up at (255, 0) and then north and end up at (255,255). They also handle different map sizes for you.

The pseudocode in the wikipedia article is fairly pythonic so lets use that, after a bit of tweaking we end up with…

def aStar(start, target):  
    closedList = set()  
    openList = set()  
    came_from = {}  
    g_score = {}  
    h_score = {}  
    f_score = {}  
    directions = list(AIM.keys())  
         
    openList.add(start)        
    g_score[start] = 0  
    h_score[start] = ants.distance(start, target)  
    f_score[start] = g_score[start] + h_score[start]  
        
    while openList:  
        current = min(f_score, key=f_score.get)  
        if (current == target):  
            self.PATH.append(start)  
            trace_path(came_from, came_from[target])  
            self.PATH.append(target)  
            return self.PATH  
           
        f_score.pop(current)  
        openList.remove(current)  
        closedList.add(current)  
          
        for direction in directions:  
            new_loc = ants.destination(current, direction)  
            if (new_loc in closedList or not ants.passable(new_loc)):  
                continue  
            new_g = g_score[current] + 1  
            
            if new_loc not in openList:  
                openList.add(new_loc)  
                closer = True  
            elif new_g < g_score[new_loc]:  
                closer = True  
            else:  
                closer = False  
               
            if closer == True:  
                came_from[new_loc] = current  
                g_score[new_loc] = new_g  
                h_score[new_loc] = ants.distance(new_loc, target)  
                f_score[new_loc] = g_score[new_loc] + h_score[new_loc]  
               
            return None  


def trace_path(came_from, current_node):  
    if current_node in came_from:  
        trace_path(came_from, came_from[current_node])  
        self.PATH.append(current_node)  
        return  

Add this to the do_turn section and the only other change you will need is the add self.path = [] to the do_setup section for this to work.

This will return a list of tuples for each step on the path your ant needs to take to reach a target, this could be food, an enemy hill or even just a random point where you want to move an ant to. It will be of the format [(0,0),(0,9),(9,9),(9,8),(8,8)]

To Do:

• Maintain a list of paths
• Provide a method to move ants along the path and check that paths are correct
• Watch the time left (this is important, although this algorithm is fairly fast it will eat up your 1000ms if you use it a lot)

Potential improvements:

• Speed - I think most major speed boosts have been implemented (use of dicts and sets) but there is space for some small gains
• Mapping - ants.passable only includes what we can currently see, maintaining our own map should let us remember all seen obstacles (also potentially faster?)