Maze Solver With Explore - 3 for 3!

Ok, newest maze solver simulator.  I added an exploring routing that does up to 256 cells of exploring before using lowest value routines to get to its current target.  If the mouse explores on the way to the target and back for maze2, it uncovers enough of the maze to solve it well on the speed run.  It is still possible for the mouse to get stuck in a sequence of cells that are adjacent to accessible, unexplored cells when it is not in explore mode.  I need to look into a "back track" routine that will handle this.  In the meantime, here is the updated simulator:
Maze Sim With Explore
Maze File 2

I need to develop a "speed run" routine that doesn't flood, explore, etc.  On press of a button, it would compute a single, shortest know cell path to the target and put that in a queue.  It would then pull off turns from the queue ( only straight, right, and left ) to direct it to the target.

Maze Solver - Not So Great...

    Ok, so I solved one maze from 1993.  It was a maze from a competition known to make hard mazes.  I created another maze from a 2004 competition.  It solved the maze.  It back solved by a different route.  It did its speed run on a totally new route and got stuck.  I'm just starting to work this out.  Here is the maze if you want to try it out:
Example Maze 2
  
    On the other hand, it does solve this maze from 2002 that I recreated.  It looks like I run into problems on two fronts.  First, if the first run and back solve don't reveal enough of the maze.  Second, if a run hits an unexplored region and the only open spaces available have cell values greater than the current cell.  I need to solve the "stuck" problem for sure.  I will also want to add more "exploration" to the back solve phase.

   Here is the other maze I was able to solve successfully ( if not optimally; I haven't checked ):
Example Maze 3

More Maze Simulation

    Okay, I made a slew of changes to the maze/mouse simulator.  The key to backsolving the maze from goal to start is to reflood the maze, using the start as the target.  I modified the flood method to take a target flag ( start or goal ) and a starting queue list ( either the start index or the goal indices ).  The program moves the mouse to the goal.  It then lets you back solve to the start.  It then lets you do a "speed run", solving the maze with all the wall data it collected in the initial solve and backsolve.  It was cool to see the mouse find a better back route than the initial solve route.  Along the way, it tried a few unexplored areas.  This led to the optimal 91 step route.
    I changed the display code, too.  The mouse is marked by the number 800.  I have code in there to make the mouse marker red, using ascii escape codes.  I commented these out, so everyone can run it ( and so it will display ok in the Eclipse console ).  Uncomment them if you like.  The maze file is unchanged.  I put it here, so no one has to go hunt for it.  Here is the new code:
Full Mouse Maze Simulator
Sample Maze File

    Oh, I didn't even think about this.  Windows users may have trouble seeing this maze file cleanly.  There are no carriage returns.  Don't let your editor add them.  It may cause problems when loading the maze.  I can't remember if I allowed for this or not.

New shots:

First Solve - Note the value at start cell

Back Solve Initial Flood Results

End Back Solve - Note New Values/Better Path

Speed Run - Note Better Path

More on the Maze

I redid the mouse/maze simulator.  It is much faster.  I also wrote it in a more procedural fashion.  I am getting a better idea of what the code will look like on the Pic this way.  I just swapped the files, so the old code is no longer available.  Instead, the new code is here:
maze and mouse simulator

This program parses a character based maze file.  Here is an example file:
Sample Maze File

It should be easy to create new mazes with this format.  Remember the IEEE rules.  The middle four tiles are the goal and must have at least one way to enter.  The start tile is in the lower left ( south west ) corner.  It must have only one open direction.  This simulator is only geared to the competition 16 x 16 mazes.

Screenshots:

The Maze in its Initial State

 The Maze After First "Flood" - no walls known

The Solved Maze - some unexplored cells

The next step for me is to figure out why gpsim isn't working with the I2C eeprom 256k bit module.  I can do everything but acknowledge polling.  It always times out.  This is odd since the code runs on a real Pic.

Some Code - Bootloader, I2C, Maze Solving (virtual)

    Ok, time for some code updates.

    First up is the bootloader.  I rewrote my bootloader to accomodate my 16F877 and 16F876a chips.  Unfortunately, this meant the USART speed went down to 2400.  I didn't really notice much difference.  One thing I did put in my bootloader, a true erase sequence.  I made sure I wrote patch space ( 0x3FFF ) to every block from address 0x004 to the start of the bootloader code.  Yes, I know that the '877 and '876a do an erase before write, but what about old code that might sit in between your new code?  I opted for the safe route and made sure the space was clean.  It adds about 30 seconds to the '877's program time.  It adds about 10 seconds to the '876a.  I can live with it.  If you can't, just don't call the erase sequence.

You can download the assembly code for the 16F876a here. 
The adjusted Python code is here.

Note that the command line looks something like this now:
icsp.py /dev/ttyS0 16f876a 2400 /path/to/hex/file.hex -d
for program name, serial port, device type, baud rate, path to hex file, and -d debug switch.

    Next up is the test code I used to get the 32k eeprom working over I2C.  This is pretty much taken whole cloth from application note AN976 from Microchip.

Assembly code for I2C master mode with 32k eeprom.

    Last up is some test code I wrote.  It started as just a quick way to generate a graphical maze like those used for micromouse competitions.  I then patched in some maze-solving simulation.  It needs a total rewrite, but I still think it's cool and useful.

 Here is the maze code.

    And here is a screenshot of maze after solving:

    That's it for now.

I2C Working

    Here's what we have so far.  I got my bootloader working on the 16F876a chips on the first try.  I took the sample code from application note AN976 and got the uCU working with the 32k eeprom.  The next step is to start writing the maze solving code on the Pic.  I'll have plenty of room now that the eeprom chip is working.  I think the cell values want to live on the Pic's built in eeprom.  That way, when it is time to run the maze, I won't need to access the eeprom chip.  I'll store the wall values and a flags ( visited before, destination cell, start cell ) for each cell on the first 256 bytes of the eeprom.  The rest of it can be stack space.  I'll still need a counter word to guard against stack overflow.  Most operations other than init will be single byte reads/writes.
  
    I'll be able to compute "neighbors" by +1 for East, -1 for West, +16 for North, and -16 for South.  If the boundaries cross, it won't be a problem because the walls will let me know not to bother with them.  The initial load of the arrays will pre-fill the outer walls of the maze.

    I'll need to stay aware of what operation I'm doing.  If I try to read or write from the USART, I'll need to make sure and disable the I2C operation first.  Otherwise, I run the risk of errors.

    Order of operations:
    1. take bearings ( walls )
    2. partial flood fill ( update values )
    3. determine next move
    4. virtual move
    5. repeat until destination.

    This will be a fun first exercise!

Detour...Again... MicroMouse!

    Well, here I go again.  Hexapods are expensive!! I took a detour and looked into these things called MicroMice.  At first, it didn't seem all that great.  The robot runs around a maze and tries to find the center.  Wee!  Blindly follow a wall and always go right, right?  Wrong!  These suckers actually solve the maze using an heuristic algorithm.  The Bellman algorithm is apparently the standard.  Then, they improved on it with the modified "flood-fill" approach.  Then, they got even smarter.  The mice continue exploring after finding the center.  They calculate the best route over several options.  Then, they improved more.  The mice calculate diagonal as well as strictly vertical/horizontal attacks.  The Japanese competitions average around 15 seconds for a solve.  Wow.  This is way out of my league.  But I do like the idea of having a little uMcu solve a maze.  I whipped up a prototype in Python.
    What I came up with is a bit daunting.  I will need two arrays and a stack.  The arrays need to be 256 bytes long.  The stack needs to be at least 200 bytes.  The maze I test solved ( from 1993 ) needed a stack of 148.  It's pretty memory intensive stuff with a lot of recursion.  I think I'll need to back-solve the recursion to just do straight loops.  Ugh!  It makes my head hurt to do that.  I worked hard in college to get recursion.  I never did get the hang of implementing the same solution in straight loops.  Once I figured out how to do it with recursion, it always looked so neat and simple.
    The short term plan is just to get the chips to solve the maze.  Steps:  First, I need some new chips.  I'm sticking with the Ram deficient Pics.  I ordered some 16F876 chips and some 32K I2C Ram chips.  These will help alleviate the memory issues.  I will get I2C working between two Pics.  Then, I'll get it working with the Ram chip.  Then, I think I will simulate movement in the maze from a PC over USART.  I'll let the mouse solve the maze.  It will stream it's arrays back to the PC ( walls located and the value of each tile ).. I'll need to write a program to crunch this stream and generate the maze.  My simulator will help with that.
    The actual robot to solve a maze is pretty complex.  The motors/drivers must be able to know exactly how far they have traveled.  They must be able to turn on a pin head.  They can't be thrown off by rough terrain or miss-alignment.  The two choices here are stepper motors ( slow and new programming ) or DC motors with encoders.  I don't like the idea of encoders.  Too many interrupts that can mess with other time-sensitive operations.  Steppers, on the other hand are slow, expensive, and I can't seem to find good, cheap drivers.
    For sensors, most seem to use line following type IR sensors.  I'm thinking that three Sharp IR sensors might do the trick.  I'll mount them fixed front, left, and right.  That will only tie up three pins.
    It looks like the mouse wants either 2 or 3 controllers.  One will definitely be assigned to maze solving.  Another will handle motor control/movement.  The sensors could be handled by either of these chips or a third chip.  We'll see.
   I honestly don't know if I'll ever actually build this 'bot.  I'm sure whatever I could cobble together on limited funds wouldn't be much.  It'd be cool if it could just solve the maze, whatever the time.

Hexapod

I saw that Pololu offers a board to control 16 servos.  It's just a Pic16f87x.  I thought: wow! I could do that.  I wrote a proof of concept on the 16f88 at 8MHz that can do it without "jitter."  Of course, the 16f88 can't handle 16 servos.  It only has 15 pins output max.  My code looks solid, though.  I can move 2 servos on any two pins without "jitter."  I wonder if it is better to bundle the control with the gaits in one 16f87x chip, or should I invest in a Texas Instruments TLC to control the PWM...

Right now, as I contemplate a hexapod,  I think I will use a 16f87x to handle the gaits and PWM in one.  That's one less chip.  The main controller should talk to it via SSP or I2C.  SSP looks simpler, but everyone seems to use I2C.  I haven't played with either yet, so I don't have an opinion.  I don't want to use serial, for I want to preserve that for programming/debugging/talking to the PC.

The rough idea now is to make the lightest hexapod possible.  I would like to use the cheap, $8.00 servos from Sparkfun.  I'm thinking about 4 lipo batteries in series for power.  I'll need a recharge solution for sure.  I think a PCB for the base and paperclips for the legs.  I'll need to work out how to hold it all together and how to attach the paperclips to the servos....  I really have to take the time to do the math on the strength of the servos.  How much weight is involved, and can the servos support it?

In short, Yay!  New problems to figure out!

BootLoader Update

I found an edge case tonight.  My checksum value came up as zero.  Here is the rough update to the code to deal with it.  The whole program needs an overhaul for optimization, but here is the working version:


#!/usr/bin/python2.6

from time import *
from uspp import uspp
import sys

class Programmer:
    tty = None
    prog = None
    file = None
    filename = None
    portname = None
    debug = False
    ok = 'k'
    failed = 'n'
    dataStart = 9
    rewriteAddrH = '0F'         # each must be 2 characters
    rewriteAddrL = 'FC'
    startSignal = chr(0xc1)
  
    def __init__(self, args ):
        self.prog = args[0]
        if self.prog.rfind( '/' ) >= 0:
            self.prog = self.prog[self.prog.rfind('/')+1:]
        if len(args) < 3:
            print self.prog + ': usage:', self.prog, '/path/to/serial/port /path/to/myHex.hex [-d]'
            exit(1)
        if len( args ) >3 and args[3] == '-d':
            self.debug = True
        self.portname = args[1]
        self.filename = args[2]
      
    #    
    def writeProgram(self):
        if self.debug == True:
            print '\nProgrammer.writeProgram: PROGRAM: ' + self.prog + '   PORT: "' + self.portname + '"   FILENAME: ' + self.filename + '\n'
        self.openFile( self.filename )
        if self.debug == True:
            print 'Programmer.writeProgram: File open. Reading packets. . .\n'
        packets = self.makePackets( self.file )
        self.file.close()
        if self.debug == True:
            print '\nProgrammer.writeProgram: Packet dump:\n'
            for packet in packets:
                for c in packet:
                    val = hex(ord(c))[2:]
                    if len(val) < 2:
                        val = '0' + val
                    print val,
                print ''
        print '\nProgrammer.writeProgram: File read complete. Ready to reset pic . . .\n'
        self.openPort(self.portname)
        if self.debug == True:
            print 'Programmer.writeProgram: port open. Awaiting start sequence. . .\n'
        self.startSequence()
        for packet in packets:
            self.sendPacket(packet)

        # how to end? The chip will time out waiting and reset itself.
        print 'Programmer.writeProgram: Programming complete.'
  
    # attempt to send a packet to the pic up to three times. Die on no response.
    def sendPacket(self, packet ):
        retries = 3
        while retries >0:
            if self.debug == True:
                print 'Programmer.sendPacket: Sending packet...',
                for c in packet:
                    print hex(ord(c)),
                print ''
  
            self.tty.write( packet )

            while True:
                status = self.endlessWait()
                if 'k' == status:
                    print 'Programmer.sendPacket: Packet send successful.'
                    return
                elif 'n' == status:
                    if self.debug == True:
                        print 'Programmer.sendPacket: Packet send unsuccessful.  Retrying...'
                    retries = retries - 1
                    break
                else:
                    print 'Programmer.sendPacket: An unexpected response from the microchip.  Received: ', ord(status), 'Aborting. . .'
                exit(1)

        # if we get down here, we've failed
        print 'Programmer.sendPacket: Failed to get the packet to the microchip successfully. Aborting. . . '
        exit(1)
  
    # opens the serial port.  sets in in class variable and returns handle too
    def openPort(self, portname ):
        try:
            self.tty = uspp.SerialPort( portname, 0, 38400)
            self.tty.flush() # discard unread bytes
        except Exception:
            print 'Programmer.openPort: Could not open the serial port: ' + portname
            exit(1)
  
    # opens the hex file, stores file handle in class var and returns the file handle
    def openFile(self, filename ):
        try:
            self.file = open( filename, 'r' )
        except Exception:
            print 'Programmer.openFile: Could not open file: ' + filename
            exit(1)
        return self.file
  
  
    def makePackets(self, file ):
        lines = file.readlines()
        packets = []
        for line in lines:
            ind = line.find( '\n' )
            if ind > 0:
                line = line[:ind]
            ni = line[1:3]
          
            intNumInstr = int(ni,16)/2
            # Need to put high and low together
            # as a single hex value, divide by two, then split them.
            addrValue = int(line[3:7],16) / 2
          
            recordType = int(line[7:9],16)
            packet = ''
          
            # Record Type 0: data
            # Record Type 1: end of file
            # Record Type 2 & 3: Extended segment addressing.  throw warning for us...
            # Record Type 4: signals true 32 bit addressing.  throw warning for us...
            # Record Type 5: another extended address thingy.  throw warning for us...
            if recordType == 0: # This is a data line
                # compute address high and low
                addrH = ''
                addrL = ''
                if addrValue < 256:
                    addrH = '0'
                    addrL = hex( int( bin( addrValue ),2 ) )[2:] # take value as binary int & convert to hex string
                else:
                    b = bin(addrValue)[2:]                  # get as binary string but trim off the '0b'
                    addrH = hex( int( b[:len(b)-8], 2 ) )[2:]      # turn binary into --> int --> hex string and trim off '0x'
                    addrL = hex( int( b[len(b)-8:], 2 ) )[2:]
                intAddrH = int( addrH, 16 )
                intAddrL = int( addrL, 16 )
                addrH = chr( intAddrH )
                addrL = chr( intAddrL )
              
                # Now deal with the address given
                if intAddrH > 32:
                    print 'Programmer.makePackets: Not sure how to deal with data memory writes yet.  Skipping. . .'
                    continue
                # config bits will have address high of 32
                elif intAddrH == 32:
                    if self.debug == True:
                        print 'Programmer.makePackets: Config bit instruction. skipping this line'
                        print '\t\t\tConfig bits can\'t be programmed by this bootloader.\n'
                    continue
                # the bootloader will have an address space of 0xfff - 192 = 0xf1f
                # this translates to an address high of 15 and address low of 31
                elif intAddrH >= 15 and intAddrL >= 31:
                    print 'Programmer.makePackets: Your program is trying to overwrite the bootloader.  Aborting...'
                    print '\tThis program will not allow you to overwrite the bootloader program.  You will need to reprogram the chip if you wish to overwrite.'
                    exit(1)
                # need to deal with the first 4 instructions
                elif intAddrH == 0 and intAddrL == 0:
                    self.createFirstInstructionLines( packets, line, intNumInstr )
                else:
                    packet = self.createRegularPacket( line, intNumInstr, addrH, addrL )  
                    packets.append( packet )
              
            elif recordType == 1:  # end of file
                if self.debug == True:
                    print '\nProgrammer.makePackets: Hex file read complete.'
            elif recordType == 4:   # print inhx32 warning
                if self.debug == True:
                    print  'Programmer.makePackets: Found an indicator line to use 32 bit addressing.  Compile with inhx8s or inhx8m. Ignoring this line.\n'
            else:
                if self.debug == True:
                    print 'Programmer.makePackets: Found lines with extended segment addressing. Skipping this line. . .\n'  
        return packets
  
    def computeNumberOfInstructions(self, intNumInstr ):
        computedNumInstr = 8
        if intNumInstr <= 4:
            computedNumInstr = 4
        elif intNumInstr > 8:
            print 'Programmer.makePackets: Number of instructions was greater than 8.  Unexpected. Aborting. . .'
            exit(1)
        return computedNumInstr

    def createFirstInstructionLines(self, packets, line, intNumInstr ):
        """ This is an abysmal function and set of algorithms.  Need to refactor to make use of redundant operations.
Eventually, the redundant operations in this and the createRegularPacket should be combined.  For now, I just want it work."""

        computedNumInstr = self.computeNumberOfInstructions( intNumInstr )
        numInstr = chr( computedNumInstr  )
        # If less than 4 instructions, create special rewrite packet with what we have then pad instructions to 4.
        # The crc will need to be computed to account for the special address.
        # else if 4 or more, create rewrite packet for first 4
        # calculate crc
        if intNumInstr < 4:
            #get the data for all the instructions
            lineOne = line[self.dataStart:self.dataStart+4*intNumInstr]
            numToPad = (4 - intNumInstr) * 2
            for i in range(0,numToPad,1):
                lineOne = lineOne + '00'
        else:
            # create the lineOne data for the first 4 instructions
            lineOne = line[self.dataStart:self.dataStart+16]
        # expect doubleAddress to return 1e82
        crcOne = self.calculateChecksum( '04' + self.rewriteAddrH + self.rewriteAddrL + lineOne )
        packetOne = self.makeChar( self.rewriteAddrH ) + self.makeChar( self.rewriteAddrL ) + self.makeChar( '04' )
        for i in range( 0, len(lineOne), 4 ):
            packetOne = packetOne + self.makeChar( lineOne[i:i+2] ) + self.makeChar( lineOne[i+2:i+4] )
        packetOne = packetOne + self.makeChar( crcOne )
      
        packets.append( packetOne )
            # if more than 4 instructions and less than 9, create second packet with what's left
            # calculate new crc.  Address will be 0x04 for low
        if computedNumInstr == 8:
            start = self.dataStart + 16   #start at 5th instruction
            end = len(line) - 2           # knock off old crc
            lineTwo = line[start:end]
            if intNumInstr < 8:
                pad = computedNumInstr - intNumInstr
                if pad > 0:
                    for i in range(0,pad,1):
                        lineTwo = lineTwo + '0000'
            crcTwo = self.calculateChecksum( '04' + '0004' + lineTwo )
            packetTwo = self.makeChar( '00' ) + self.makeChar( '04' ) + self.makeChar( '04' )
            for i in range( 0, len(lineTwo), 4 ):
                packetTwo = packetTwo + self.makeChar( lineTwo[i:i+2] ) + self.makeChar( lineTwo[i+2:i+4] )
            packetTwo = packetTwo + self.makeChar( crcTwo )
            packets.append( packetTwo )
  
    def calculateChecksum(self, data ):
        tot=0
        for i in range( 2, len(data)+2, 2 ):
            tot = tot + int( data[i-2:i], 16 )
        s = bin( tot )
        if len(s) <10:
            s = s[2:]
        else:
            s = s[-8:]
        hx = 0x100 - int(s,2)
        crc = ''
        if hx < 0x100:
            crc = hex( hx )[2:]
        else:
            crc = hex( hx )[-2:]
        return  crc
  
    def createRegularPacket(self, line, intNumInstr, addrH, addrL ):
        # compute the number of instructions
        computedNumInstr = self.computeNumberOfInstructions( intNumInstr )
          
        numInstr = chr( computedNumInstr )
        packet = '' + addrH + addrL + numInstr
      
        # now add the data packets
        for i in range( self.dataStart, len(line) - 4, 4 ):
            packet = packet + self.makeChar( line[i:i+2] ) + self.makeChar( line[i+2:i+4] )
          
        # need to add padding for short lines
        pad = computedNumInstr - intNumInstr
        if pad > 0:
            for i in range(0,pad,1):
                packet = packet + self.makeChar( '00' ) + self.makeChar( '00' )
              
        # now add in the checksum
        data = hex( computedNumInstr )[2:].zfill(2) + hex( ord(addrH) )[2:].zfill(2) + hex( ord(addrL) )[2:].zfill(2) + line[7:len(line)-2]
        checksum = self.calculateChecksum( data )
#        checksum = line[len(line)-2:]
        packet = packet + self.makeChar( checksum )
        return packet
  
    def makeChar( self, str ):
        return chr(int( '0x' + str, 16) )


    def startSequence(self):
        """Go into endless wait, listening on port for the startSignal.  When it receives the start signal, it
echoes it back to the pic.  It then waits endlessly for the pic to send ok ('k').  It then returns."""
#        self.waitForResponse( self.startSignal )
#        self.endlessWait()
        self.waitForStartDiscardJunk()
        sleep(.002)
        self.tty.write( self.startSignal )
        print 'Programmer.startSequence: Sent the start signal to the pic.'
        # for echo only, write ok back
#        self.tty.write( self.ok )
        self.waitForResponse( self.ok )

    def waitForStartDiscardJunk(self):
        c = ''
        while True:
            c = self.tty.read()
            if self.startSignal == c:
                return
            elif '' != c:
                print 'junk char received: ', c, 'ord:', ord(c)

    def waitForResponse( self, charWeExpect ):
        c = self.endlessWait()
        if charWeExpect != c:
            print 'Programmer.waitForResponse: We did not receive the character we were expecting.  Looking for:', hex(ord(charWeExpect)), '.  We received:', hex(ord(c)), '. Aborting.'
            exit(0)
        else:
            ch = ''
            try:
                ch = c.decode('ascii')
            except:
                ch = hex( ord(c) )
            print 'Programmer.waitForResponse: Got expected response:', ch
    def endlessWait( self ):
        c = ''
        while True:
            c = self.tty.read()
            if '' != c:
                return c
  
if __name__ == '__main__':
    programmer = Programmer( sys.argv )
    programmer.writeProgram()

Lots of Minor Work

I completed a lot of minor work today.  I adjusted my bootloader.  For the initial load of the bootloader, I found it was necessary to add a dummy program to the upper region to stop the code from flowing back to the start of the bootloader.  If I didn't, the icsp program on the PC might get noise and fail to receive the start signal.  I also added a new start method on the PC end.  It waits for the start signal from the Pic, and it ignores anything else ( like bogus 0x00 from an open output on the TX line.

I cut some scrap wood for a base and taped on a ball caster in place of the electrical taped LED I was using for the back balance.  I got the ball caster in the mail today along with a few other goodies from Sparkfun.  One of the other goodies was an RS232 shifter kit.  I soldered that together.  It not only freed up a load of space on my breadboard, it also allowed me to reprogram my 'bot in circuit.  Happiness!  It is much faster than I'd ever hoped.  It has been remarkably error free, too.

I've started playing around with the Sharp IR sensor and some basic IR transmitter/receiver stuff.  I want to rewrite CDR to use the Sharp instead of the Ping ultrasound sensor.  I also want to add line following capability.

I got a pair of really small ( and probably fragile ) servos, too.  They are just fodder for some routines I want to try.  I want to write a routine that will do interrupt driven servo control.  I'll start with two or three servos.  I want to see how many servos I can control with a single Pic 16f88 at 8MHz, using a single timer1 at 1 or .5 mSec interrupts without "jitter".

I see the button to add a video here, I'll try to link in a vid I did of CDR:

BootLoader - Faster

Just made the changes to up the speed to 8MHz at 19200 baud.  Still flawless performance and no rewrites.  Tried loading my robot code (317 words ) and it flew in about as fast or faster than my programmer.  And I didn't have to unplug anything!!!  I'll eventually add in support for programming data memory as well.  I don't have a need for it as of now, so no hurry.

I noticed that I left a small gaff in the python code.  The python code doesn't check the startSignal value to make sure it is what I was waiting for.  I was getting some off values once in awhile.  Once this happened, it kept happening until I had rebooted my laptop.  My guess is that it is either something to do with the startup of the USART on the pic or the buffer on my PC's USART.  Or it could be a bug in the Python uspp code...  I'm not too stressed about it.  The rest of the code is pretty bullet proof for version 0.0.1.

Now that it is finally working, I can't help tweaking it. ;}

EDIT:
Still pushing things.  I removed the gaff.  I now expect the pic to send the correct start signal.  It's working fine.  I upped the baud rate to 38.4k baud.  At 8MHz internal, the datasheet says the error rate is +0.16%.  So far: flawless.

BootLoader - Python Code for PC

Still rough looking.  Could use a lot of clean up, optimization, etc.

#/usr/bin/python2.6

from time import *
from uspp import uspp
import sys

class Programmer:
    tty = None
    prog = None
    file = None
    filename = None
    portname = None
    debug = False
    ok = 'k'
    failed = 'n'
    dataStart = 9
    rewriteAddrH = '0F'         # each must be 2 characters
    rewriteAddrL = 'FC'
    startSignal = chr(0xc1)
  
    def __init__(self, args ):
        self.prog = args[0]
        if self.prog.rfind( '/' ) >= 0:
            self.prog = self.prog[self.prog.rfind('/')+1:]
        if len(args) < 3:
            print self.prog + ': usage:', self.prog, '/path/to/serial/port /path/to/myHex.hex [-d]'
            exit(1)
        if len( args ) >3 and args[3] == '-d':
            self.debug = True
        self.portname = args[1]
        self.filename = args[2]
      
    #    
    def writeProgram(self):
        if self.debug == True:
            print '\nProgrammer.writeProgram: PROGRAM: ' + self.prog + '   PORT: "' + self.portname + '"   FILENAME: ' + self.filename + '\n'
        self.openFile( self.filename )
        if self.debug == True:
            print 'Programmer.writeProgram: File open. Reading packets. . .\n'
        packets = self.makePackets( self.file )
        self.file.close()
        if self.debug == True:
            print '\nProgrammer.writeProgram: Packet dump:\n'
            for packet in packets:
                for c in packet:
                    val = hex(ord(c))[2:]
                    if len(val) < 2:
                        val = '0' + val
                    print val,
                print ''
        print '\nProgrammer.writeProgram: File read complete. Ready to reset pic . . .\n'
        self.openPort(self.portname)
        if self.debug == True:
            print 'Programmer.writeProgram: port open. Awaiting start sequence. . .\n'
        self.startSequence()
        for packet in packets:
            self.sendPacket(packet)

        # how to end? The chip will time out waiting and reset itself.
        print 'Programmer.writeProgram: Programming complete.'
  
    # attempt to send a packet to the pic up to three times. Die on no response.
    def sendPacket(self, packet ):
        retries = 3
        while retries >0:
            if self.debug == True:
                print 'Programmer.sendPacket: Sending packet...',
                for c in packet:
                    print hex(ord(c)),
                print ''
  
            self.tty.write( packet )

            while True:
                status = self.endlessWait()
                if 'k' == status:
                    print 'Programmer.sendPacket: Packet send successful.'
                    return
                elif 'n' == status:
                    if self.debug == True:
                        print 'Programmer.sendPacket: Packet send unsuccessful.  Retrying...'
                    retries = retries - 1
                    break
                else:
                    print 'Programmer.sendPacket: An unexpected response from the microchip.  Received: ', ord(status), 'Aborting. . .'
                exit(1)

        # if we get down here, we've failed
        print 'Programmer.sendPacket: Failed to get the packet to the microchip successfully. Aborting. . . '
        exit(1)
  
    # opens the serial port.  sets in in class variable and returns handle too
    def openPort(self, portname ):
        try:
            self.tty = uspp.SerialPort( portname, 0, 9600)
            self.tty.flush() # discard unread bytes
        except Exception:
            print 'Programmer.openPort: Could not open the serial port: ' + portname
            exit(1)
  
    # opens the hex file, stores file handle in class var and returns the file handle
    def openFile(self, filename ):
        try:
            self.file = open( filename, 'r' )
        except Exception:
            print 'Programmer.openFile: Could not open file: ' + filename
            exit(1)
        return self.file
  
  
    def makePackets(self, file ):
        lines = file.readlines()
        packets = []
        for line in lines:
            ind = line.find( '\n' )
            if ind > 0:
                line = line[:ind]
            ni = line[1:3]
          
            intNumInstr = int(ni,16)/2
            # Need to put high and low together
            # as a single hex value, divide by two, then split them.
            addrValue = int(line[3:7],16) / 2
          
            recordType = int(line[7:9],16)
            packet = ''
          
            # Record Type 0: data
            # Record Type 1: end of file
            # Record Type 2 & 3: Extended segment addressing.  throw warning for us...
            # Record Type 4: signals true 32 bit addressing.  throw warning for us...
            # Record Type 5: another extended address thingy.  throw warning for us...
            if recordType == 0: # This is a data line
                # compute address high and low
                addrH = ''
                addrL = ''
                if addrValue < 256:
                    addrH = '0'
                    addrL = hex( int( bin( addrValue ),2 ) )[2:] # take value as binary int & convert to hex string
                else:
                    b = bin(addrValue)[2:]                  # get as binary string but trim off the '0b'
                    addrH = hex( int( b[:len(b)-8], 2 ) )[2:]      # turn binary into --> int --> hex string and trim off '0x'
                    addrL = hex( int( b[len(b)-8:], 2 ) )[2:]
                intAddrH = int( addrH, 16 )
                intAddrL = int( addrL, 16 )
                addrH = chr( intAddrH )
                addrL = chr( intAddrL )
              
                # Now deal with the address given
                if intAddrH > 32:
                    print 'Programmer.makePackets: Not sure how to deal with data memory writes yet.  Skipping. . .'
                    continue
                # config bits will have address high of 32
                elif intAddrH == 32:
                    if self.debug == True:
                        print 'Programmer.makePackets: Config bit instruction. skipping this line'
                        print '\t\t\tConfig bits can\'t be programmed by this bootloader.\n'
                    continue
                # the bootloader will have an address space of 0xfff - 192 = 0xf1f
                # this translates to an address high of 15 and address low of 31
                elif intAddrH >= 15 and intAddrL >= 31:
                    print 'Programmer.makePackets: Your program is trying to overwrite the bootloader.  Aborting...'
                    print '\tThis program will not allow you to overwrite the bootloader program.  You will need to reprogram the chip if you wish to overwrite.'
                    exit(1)
                # need to deal with the first 4 instructions
                elif intAddrH == 0 and intAddrL == 0:
                    self.createFirstInstructionLines( packets, line, intNumInstr )
                else:
                    packet = self.createRegularPacket( line, intNumInstr, addrH, addrL )  
                    packets.append( packet )
              
            elif recordType == 1:  # end of file
                if self.debug == True:
                    print '\nProgrammer.makePackets: Hex file read complete.'
            elif recordType == 4:   # print inhx32 warning
                if self.debug == True:
                    print  'Programmer.makePackets: Found an indicator line to use 32 bit addressing.  Compile with inhx8s or inhx8m. Ignoring this line.\n'
            else:
                if self.debug == True:
                    print 'Programmer.makePackets: Found lines with extended segment addressing. Skipping this line. . .\n'  
        return packets
  
    def computeNumberOfInstructions(self, intNumInstr ):
        computedNumInstr = 8
        if intNumInstr <= 4:
            computedNumInstr = 4
        elif intNumInstr > 8:
            print 'Programmer.makePackets: Number of instructions was greater than 8.  Unexpected. Aborting. . .'
            exit(1)
        return computedNumInstr

    def createFirstInstructionLines(self, packets, line, intNumInstr ):
        """ This is an abysmal function and set of algorithms.  Need to refactor to make use of redundant operations.
Eventually, the redundant operations in this and the createRegularPacket should be combined.  For now, I just want it work."""

        computedNumInstr = self.computeNumberOfInstructions( intNumInstr )
        numInstr = chr( computedNumInstr  )
        # If less than 4 instructions, create special rewrite packet with what we have then pad instructions to 4.
        # The crc will need to be computed to account for the special address.
        # else if 4 or more, create rewrite packet for first 4
        # calculate crc
        if intNumInstr < 4:
            #get the data for all the instructions
            lineOne = line[self.dataStart:self.dataStart+4*intNumInstr]
            numToPad = (4 - intNumInstr) * 2
            for i in range(0,numToPad,1):
                lineOne = lineOne + '00'
        else:
            # create the lineOne data for the first 4 instructions
            lineOne = line[self.dataStart:self.dataStart+16]
        # expect doubleAddress to return 1e82
        crcOne = self.calculateChecksum( '04' + self.rewriteAddrH + self.rewriteAddrL + lineOne )
        packetOne = self.makeChar( self.rewriteAddrH ) + self.makeChar( self.rewriteAddrL ) + self.makeChar( '04' )
        for i in range( 0, len(lineOne), 4 ):
            packetOne = packetOne + self.makeChar( lineOne[i:i+2] ) + self.makeChar( lineOne[i+2:i+4] )
        packetOne = packetOne + self.makeChar( crcOne )
      
        packets.append( packetOne )
            # if more than 4 instructions and less than 9, create second packet with what's left
            # calculate new crc.  Address will be 0x04 for low
        if computedNumInstr == 8:
            start = self.dataStart + 16   #start at 5th instruction
            end = len(line) - 2           # knock off old crc
            lineTwo = line[start:end]
            if intNumInstr < 8:
                pad = computedNumInstr - intNumInstr
                if pad > 0:
                    for i in range(0,pad,1):
                        lineTwo = lineTwo + '0000'
            crcTwo = self.calculateChecksum( '04' + '0004' + lineTwo )
            packetTwo = self.makeChar( '00' ) + self.makeChar( '04' ) + self.makeChar( '04' )
            for i in range( 0, len(lineTwo), 4 ):
                packetTwo = packetTwo + self.makeChar( lineTwo[i:i+2] ) + self.makeChar( lineTwo[i+2:i+4] )
            packetTwo = packetTwo + self.makeChar( crcTwo )
            packets.append( packetTwo )
  
    def calculateChecksum(self, data ):
        tot=0
        for i in range( 2, len(data)+2, 2 ):
            tot = tot + int( data[i-2:i], 16 )
        s = bin( tot )
        if len(s) <10:
            s = s[2:]
        else:
            s = s[len(s)-8:]
        return  hex( 0x100 - int(s,2) )[2:]
  
    def createRegularPacket(self, line, intNumInstr, addrH, addrL ):
        # compute the number of instructions
        computedNumInstr = self.computeNumberOfInstructions( intNumInstr )
          
        numInstr = chr( computedNumInstr )
        packet = '' + addrH + addrL + numInstr
      
        # now add the data packets
        for i in range( self.dataStart, len(line) - 4, 4 ):
            packet = packet + self.makeChar( line[i:i+2] ) + self.makeChar( line[i+2:i+4] )
          
        # need to add padding for short lines
        pad = computedNumInstr - intNumInstr
        if pad > 0:
            for i in range(0,pad,1):
                packet = packet + self.makeChar( '00' ) + self.makeChar( '00' )
              
        # now add in the checksum
        data = hex( computedNumInstr )[2:].zfill(2) + hex( ord(addrH) )[2:].zfill(2) + hex( ord(addrL) )[2:].zfill(2) + line[7:len(line)-2]
        checksum = self.calculateChecksum( data )
#        checksum = line[len(line)-2:]
        packet = packet + self.makeChar( checksum )
        return packet
  
    def makeChar( self, str ):
        return chr(int( '0x' + str, 16) )


    def startSequence(self):
        """Go into endless wait, listening on port for the startSignal.  When it receives the start signal, it
echoes it back to the pic.  It then waits endlessly for the pic to send ok ('k').  It then returns."""
#        self.waitForResponse( self.startSignal )
        self.endlessWait()
        sleep(.002)
        self.tty.write( self.startSignal )
        print 'Programmer.startSequence: Sent the start signal to the pic.'
        # for echo only, write ok back
#        self.tty.write( self.ok )
        self.waitForResponse( self.ok )

    def waitForResponse( self, charWeExpect ):
        c = self.endlessWait()
        if charWeExpect != c:
            print 'Programmer.waitForResponse: We did not receive the character we were expecting.  Looking for:', hex(ord(charWeExpect)), '.  We received:', hex(ord(c)), '. Aborting.'
            exit(0)
        else:
            ch = ''
            try:
                ch = c.decode('ascii')
            except:
                ch = hex( ord(c) )
            print 'Programmer.waitForResponse: Got expected response:', ch
    def endlessWait( self ):
        c = ''
        while True:
            c = self.tty.read()
            if '' != c:
                return c
  
if __name__ == '__main__':
    programmer = Programmer( sys.argv )
    programmer.writeProgram()

BootLoader - Pic Code

Here is the Pic code for the bootloader.  Hope it copies ok.

;******************************************************************************
;                                                                            
;       Filename:   bootloader.asm                                                                          
;       Date:   2010.11.21                                                
;   File Version:   1.0.0                                                      
;                                                                            
;       Author:   Tom Hunt                                                  
;                                                                            
;******************************************************************************
;  NOTES: A bootloader for 16f88.  Runs at 9600 baud at 4 MHz currently.
;  Relies on Python code icsp.py to run.  Reserves the last 224 bytes
;         For the bootloader.
;
;         PC_flash: 0xC1  nr  AddrH  AddrL  ...(DataLo DataHi)...  crc
;  PIC: 0xC1   k k                                                        
;******************************************************************************
;  CHANGE LOG:                                                      
;                                                                    
;                                                                    
;******************************************************************************

list      R=DEC, p=16f88           ; list directive to define processor

#include "p16f88.inc"

__CONFIG    _CONFIG1, _CP_OFF & _CCP1_RB0 & _DEBUG_OFF & _WRT_PROTECT_OFF & _CPD_OFF & _LVP_OFF & _BODEN_OFF & _MCLR_ON & _PWRTE_ON & _WDT_OFF & _INTRC_IO
__CONFIG    _CONFIG2, _IESO_OFF & _FCMEN_OFF

;******************************************************************************
;  CONSTANT DEFINITIONS                                                      
;******************************************************************************

#define maxFlash 0x1000
#define bootLoader (maxFlash - 224) ;
#define userFirstFour (maxFlash - 32)
#define oneBefore (userFirstFour - 1 )
#define rewriteAddrH 0x00F
#define rewriteAddrL 0x0E0
#define startSignal 0xc1
;errorlevel 1, -302

;******************************************************************************
;  VARIABLE DEFINITIONS                                                      
;******************************************************************************

cblock 0x20
buffer:80
endc

cblock 0x70
crc
counter
i
cnt1
cnt2
cnt3
flag
endc

;******************************************************************************
;  MACRO DEFINITIONS                                                      
;******************************************************************************

bank0_no_status MACRO
clrf STATUS
ENDM

bank0 MACRO
bcf STATUS, RP1
bcf STATUS, RP0
ENDM

bank1 MACRO
bcf STATUS, RP1
bsf STATUS, RP0
ENDM

bank2 MACRO
bsf STATUS, RP1
bcf STATUS, RP0
ENDM

bank3 MACRO
bsf STATUS, RP1
bsf STATUS, RP0
ENDM

;******************************************************************************
;  PROGRAM RESET                                                      
;******************************************************************************

ORG     0x0000
PAGESEL TomBootloader
GOTO    TomBootloader

;******************************************************************************
;  BOOTLOADER CODE                                                    
;******************************************************************************

ORG bootLoader

Initb
bank2
movwf counter ; # of loops
clrf flag
movlw 0x000
movwf EEADR^0x100 ; prepare flash adress
movwf EEADRH^0x100
movlw buffer ; prepare FSR at index 0
movwf FSR
return

writeloop ; write 2 bytes = 1 instruction
movf INDF,W
movwf EEDATA^0x100
incf FSR,F
movf INDF,W
movwf EEDATH^0x100
incf FSR,F
bank3
bsf EECON1^0x180,EEPGD ; FOR NOW, NO DATA. ALWAYS PROGRAM SPACE
bsf EECON1^0x180,WREN
clrf INTCON ; shouldn't need to, but disable all interrupts
movlw 0x55
movwf EECON2^0x180
movlw 0xaa
movwf EECON2^0x180
bsf EECON1^0x180,WR
nop
nop
waitwre
btfsc EECON1^0x180,WR ;for eeprom writes (wait to finish write)
goto waitwre
bcf EECON1^0x180,WREN
bank2
incf EEADR^0x100,F ;does not cross zones
btfsc STATUS,Z ; if we overflow, increment addr high
incf EEADRH^0x100,F
decfsz counter,F
goto writeloop
return

;******************************************************************************
;  USART ROUTINES                                                      
;******************************************************************************

sendByte
movwf TXREG
bank1
btfss TXSTA^0x080,TRMT ; when TRMT is set, transmission is completed
goto $ - 1
bank0_no_status
return

; This is the same as my usual delay code. cnt gets loaded with 3 for 4MHz ~1.5 sec delay
Receive
bank0   ;_no_status ; puts us in bank0
movlw 0x03
movwf cnt1
rpt2
clrf cnt2
rpt3
clrf cnt3
rptc
btfss PIR1,RCIF ;test RX
goto $ + 8 ; endless wait for byte
btfss RCSTA,OERR
goto $ + 2
bcf RCSTA,CREN
bsf RCSTA,CREN
movf RCREG,W ;return in W
addwf crc,f ;compute crc
return

decfsz cnt3,F
goto rptc
decfsz cnt2,F
goto rpt3
decfsz cnt1,F
goto rpt2
;timeout:

way_to_exit ;exit in all other cases; must be BANK0/1
bank1
bcf RCSTA,SPEN ; deactivate USART
bank0_no_status
goto programMain

;******************************************************************************
;  MAINLINE CODE                                                      
;******************************************************************************

TomBootloader
;init serial port
bank0_no_status
clrf INTCON ; disable all interupts
bank1
movlw 0x00 ^ ( 1 << 2 ) ; Port B all output except RX on B2
movwf TRISB ^ 0x080
movlw b'01100010' ; bits for OSCCON internal clock at 4MHz
movwf OSCCON^0x080
; set up bank 1 part of AUSART
movlw 0x19 ; decimal 25 at 4 MHz for 9600 baud
movwf SPBRG^0x080
; txsta gets b'00100100' enables asynch transmit and fast(brgh)
movlw 0x00 ^ ( ( 1 << TXEN ) + ( 1 << BRGH ) )
movwf TXSTA ^ 0x080
bank0_no_status ; puts us in bank0
; rcsta gets b'10010000' enables serial port and continuous receive
movlw 0x00 ^ ( ( 1 << SPEN ) + ( 1 << CREN ) )
movwf RCSTA
movlw startSignal ; send startSignal to begin process
call sendByte
;wait for computer
call Receive
sublw startSignal ;Expect C1
skpz
goto way_to_exit

;******************************************************************************
;  ERASE ROUTINES                                                      
;******************************************************************************

; for the 16F87/88, flash memory must be erased before writing
; erasing can only be done by blocks of 32 words, with address = integer x 32
; so : 1. save the 4 first words in buffer
;      2. erase all the user memory (0x000 to 0F40)
;      3. erase the block containing the final jump (block at 0xF80)
;      4. rewrite the 4 first words from buffer
;      5. write the user program & data in flash or eeprom

; first read the 4 first words of program
movlw 4 ; and copy them back after bulkerase
call Initb

loopread ; (or direct fill of 8 bytes in buffer)
bank3
bsf EECON1^0x180,EEPGD ; select flash program memory
bsf EECON1^0x180,RD ; select read
nop
nop
bank2 ; now in bank 2
movf EEDATA^0x100,W ; store bytes in buffer
movwf INDF
incf FSR,F
movf EEDATH^0x100,W
movwf INDF
incf FSR,F
incf EEADR^0x100,F
decfsz counter,F
goto loopread
bulkErase ; erase 120 blocks of 32 words
movlw bootLoader/32
call Initb ;
loopErase
call eraseBlock
decfsz counter,F
goto loopErase
movlw rewriteAddrH
movwf EEADRH^0x100
movlw rewriteAddrL
movwf EEADR^0x100
call eraseBlock ; and erase block where user's first 4 go
goto writeJump

eraseBlock
bank3 ; now in bank 3
bcf EECON1^0x180,RD
bsf EECON1^0x180,EEPGD ; select flash program memory
bsf EECON1^0x180,WREN
bsf EECON1^0x180,FREE
clrf INTCON ; shouldn't need to, but disable all interrupts
movlw 0x55
movwf EECON2^0x180
movlw 0xAA
movwf EECON2^0x180
bsf EECON1^0x180,WR ; erase 1 block
nop
nop
bcf EECON1^0x180,WREN
bcf EECON1^0x180,FREE
bank2 ; now in bank 2
movlw 32 ; add 32 to flash memory pointer
addwf EEADR^0x100,F
btfsc STATUS,C ; if we overflow, increment addr high
incf EEADRH^0x100,F
return

writeJump ; rewrite the 4 first words of bootloader program
movlw 4
call Initb
call writeloop

;******************************************************************************
;  RECEIVE PACKETS ROUTINES                                                      
;******************************************************************************

MainLoop ; back to original program
bank0_no_status ; puts us in bank0
movlw 'k'
call sendByte
mainl
clrf crc
call Receive ;H
bank2
movwf EEADRH^0x100
;movwf flag ;used to detect if is eeprom  NOT USED FOR NOW...
call Receive ;L
bank2 ;bank2
movwf EEADR^0x100
call Receive ;counter = numInstr
movwf counter
movwf i
;incf i,F
movlw buffer ;reset FSR to index 0
movwf FSR

receivePacket ; put the data packet and crc into buffer
call Receive
movwf INDF
incf FSR,F
call Receive
movwf INDF
incf FSR,F
decfsz i,F
goto receivePacket
call Receive ; get the crc
movwf INDF
movf crc,f ;check crc
skpz
goto checksumError ;write
bank2
movlw buffer ; reset FSR to index 0
movwf FSR

call writeloop

goto MainLoop

checksumError
movlw 'n'
call sendByte
goto mainl


;******************************************************************************
;  SPACE FOR USER'S FIRST FOUR INSTRUCTIONS CODE                                                    
;******************************************************************************

ORG oneBefore

programMain
;  This is where the program's first 4 instructions will go.
;  The 4 nops will be overwritten with the first 4 instructions of the
;  user's program
;  The next 28 instructions are wasted space, needed for the 32 byte erase
clrf PCLATH ; reset to first page, so loaded program's

ORG userFirstFour
; first 4 instructions can execute
nop
nop
nop
nop

;*************************************************************
; After reset
; Do not expect the memory to be zero,
; Do not expect registers to be initialised like in catalog.

            END