Monday 7 November 2011

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?)


Saturday 29 October 2011

AI Challenge

Attribution asobi tsuchiya
The University of Waterloo Computer Science Club has been running an AI competition for a short while which involves training ants to battle rival ant gangs for ant supremacy!

All a bit of fun, no prizes up for grabs but its been a while since I've touched anything AI-esque so will try a few ideas out and see how well my ants perform.

The platform supports most common used languages, prolog being a notable omission from an AI competition.

I downloaded the python version of the tools and examples for the following reasons;
  1. The demos given are in python or java
  2. I have PyDev installed
  3. I am lazy
The site advises "get your name on the global leaderboard in less than five minutes", owing to point 3 above I decided to take that challenge and it is true that you can have submitted code waiting to battle against other ant controlling bots in that sort of time… However your ants will probably just end up crashing into each other and if they do happen to stumble upon some food (a mechanism for gaining more ant troops) your new ant will sit on top of your anthill preventing any other ants from joining your front lines.

Fortunately there are tutorials to help you build upon the starter code and to build some basic behaviors, its a start but certainly nowhere near the end of what is possible!

Next up for my ants… learning that they can't swim!

edit :: And also how to guard their base it seems :(

Tuesday 25 October 2011

MSP430 running without power!

Well, not quite :D

I had plugged the Launchpad into USB for convenience but didn't have need for it yet, the code that was on the MSP430G2231 in the socket didn't do much besides blink the LEDs on P1.0 and P1.6

This was slightly annoying but instead of removing the USB cable (which tends to run away and hide) I decided to remove the VCC jumper from J3. My thinking was…
"This will cut power to the device and cease that annoying blinking!"
Turns out I was wrong! Have a look at the video :D

 

With the VCC jumper the LEDs blink bright, taking the VCC jumper off they still blink but not quite as bright.

Not shown in the video disconnecting the TXD or RXD line will reduce the brightness further, removing both will not allow the LEDs to light.

The above doesn't always seem to be true suggesting we are right on the limit of what the MSP430 can run on sourcing power through random pins.

In the code all pins are left at their default state except for P1.0 and P1.6 which are set to outputs.

Any ideas?

Wednesday 12 October 2011

Notes on the MSP430 header files

Browsing MSP430 header files I came across a syntax I wasn't familiar with and searching online failed to give me a good explanation (or rather, I was missing the obvious) here is the section from the header file so hopefully you can find this via google :D

#define INCH_0 (0*0x1000u) /* Selects Channel 0 */
#define INCH_1 (1*0x1000u) /* Selects Channel 1 */
#define INCH_2 (2*0x1000u) /* Selects Channel 2 */
#define INCH_3 (3*0x1000u) /* Selects Channel 3 */
#define INCH_4 (4*0x1000u) /* Selects Channel 4 */
#define INCH_5 (5*0x1000u) /* Selects Channel 5 */
#define INCH_6 (6*0x1000u) /* Selects Channel 6 */
#define INCH_7 (7*0x1000u) /* Selects Channel 7 */
#define INCH_8 (8*0x1000u) /* Selects Channel 8 */
#define INCH_9 (9*0x1000u) /* Selects Channel 9 */
#define INCH_10 (10*0x1000u) /* Selects Channel 10 */
#define INCH_11 (11*0x1000u) /* Selects Channel 11 */
#define INCH_12 (12*0x1000u) /* Selects Channel 12 */
#define INCH_13 (13*0x1000u) /* Selects Channel 13 */
#define INCH_14 (14*0x1000u) /* Selects Channel 14 */
#define INCH_15 (15*0x1000u) /* Selects Channel 15 */


These definitions are used to set the input channel for the ADC, reading the family guide (slau144) Section 22.3.2 the above numbers should map to bits 15-12, notably INCH_10 should map to 1010 on those bits which is the internal temperature sensor where available.

But how does 10*0x1000u produce 1010?

Looking at the u threw me first, all that symbolises is that the number is unsigned. If it was signed the 15th bit would be to denote positive or negative but in this case its just a part of the number, for our purposes here we can ignore it.

The next problem I had was the multiplication. I opened up a programming calculator set to hex and typed in

10*1000 = 10000 and converted to binary 1 0000 0000 0000 0000

In a case of missing the obvious… The first set of digits isn't hex! Its decimal!

Decimal 10 = Hex A, A*1000 = A000 = 1010 0000 0000 0000