 |
| Attribution Asterclix |
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 heuristicants.destination(start, direction)takes a co-ordinate and direction{n, e, s, w}and returns the co-ordinate of where that direction would take youAIMis a dictionary that compares{n, e, s, w}to the change in co-ordinatesants.passable(location)will test for water
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?)
