Adventure Island 2 [NES] Map movement in python

adv_island_2_algo.py

MAX_INDEX = 0x20

eggWay1 = [-8, -7, -9,  1, -1,  9,  7,  8]
eggWay2 = [-9, -8, -1, -7,  7,  1,  8,  9]
eggWay3 = [-1, -9,  7, -8,  8, -7,  9,  1]
eggWay4 = [7, -1,  8, -9,  9, -8,  1, -7]
eggWay5 = [8,  7,  9, -1,  1, -9, -7, -8]
eggWay6 = [9,  8,  1,  7, -7, -1, -8, -9]
eggWay7 = [1,  9, -7,  8, -8,  7, -9, -1]
eggWay8 = [-7,  1, -8,  9, -9,  8, -1,  7]
eggWays = eggWay1, eggWay2, eggWay3, eggWay4, eggWay5, eggWay6, eggWay7, eggWay8

worldState1 = [0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x36, 0x41, 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x20, 0xF0, 0x40, 0xFF, 0xFF, 0xFF, 0x15, 0x37, 0xF0, 0x18, 0x2A, 0xFF, 0xFF, 0xFF]
worldState2 = [0xFF, 0x4E, 0x1A, 0x2C, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x01, 0x23, 0x31, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x19, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x14, 0x30, 0xFF, 0xFF, 0xFF, 0xFF]
worldState3 = [0xFF, 0xFF, 0xFF, 0x4A, 0x4B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x33, 0xFF, 0xFF, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0x10, 0x13, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x21, 0x3D, 0xFF, 0xFF, 0xFF]
worldState4 = [0xFF, 0xFF, 0x48, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x1E, 0x43, 0x17, 0xFF, 0xFF, 0xFF, 0xFF, 0x27, 0xFF, 0xFF, 0xFF, 0x3F, 0xFF, 0xFF, 0xFF, 0xFF, 0x3E, 0x08, 0x09, 0xFF, 0xFF, 0xFF, 0xFF]
worldState5 = [0x2E, 0x46, 0x45, 0x2B, 0xFF, 0xFF, 0xFF, 0xFF, 0x22, 0x07, 0x06, 0x11, 0xFF, 0xFF, 0xFF, 0xFF, 0x32, 0xFF, 0xFF, 0x1C, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x24, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF]
worldState6 = [0x4D, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x2D, 0xFF, 0xFF, 0xFF, 0x35, 0xFF, 0xFF, 0xFF, 0x3A, 0x05, 0xFF, 0xFF, 0x1D, 0xFF, 0xFF, 0xFF, 0x25, 0x16, 0x4C, 0x04, 0xFF, 0xFF, 0xFF, 0xFF]
worldState7 = [0x4F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0E, 0x0A, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x29, 0x34, 0x26, 0xFF, 0x0B, 0xFF, 0xFF, 0xFF, 0x12, 0xFF, 0xFF, 0x3C, 0xFF, 0xFF, 0xFF, 0xFF]
worldState8 = [0xFF, 0x0C, 0x0D, 0x44, 0xFF, 0xFF, 0xFF, 0xFF, 0x2F, 0x3B, 0x1F, 0x39, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0F, 0x47, 0x38, 0x1B, 0x49, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x28, 0xFF, 0x42, 0xFF, 0xFF]

worldStates = worldState1, worldState2, worldState3, worldState4, worldState5, worldState6, worldState7, worldState8
beginIndexes = 0x15, 0x14, 0x3D, 0x08, 0x24, 0x35, 0x0B, 0x42
endIndexes   = 0x41, 0x4E, 0x4A, 0x48, 0x46, 0x4D, 0x4F, 0x3B

def extractUnique(pairs):
  levels = set()
  ansPairs = []
  for pair in pairs:
    level, eggoNo = pair
    if level not in levels:
      levels.add(level)
      ansPairs.append(pair)
  return ansPairs

def getNextWay(curIndex, egg, worldState):
  nextIndex = curIndex
  for tries in xrange(4):
    checkIndNext = []
    for ind in egg:
      checkIndNext = []
      newInd = nextIndex + ind
      if newInd < 0 or newInd >= MAX_INDEX:
        continue
      newLevel = worldState[newInd]
      if newLevel == 0xF0 and checkIndNext == -1:
        checkIndNext.append(newInd)
      if newLevel < 0x50:
        return newLevel
    if len(checkIndNext)>0:
      for indNext in checkIndNext:
        if indNext != curIndex:
          nextIndex = indNext
          break
    else:
      break
  for nextIndex in xrange(0x1F,-1,-1):
    defLevel = worldState[nextIndex]
    if defLevel < 0x50 and curIndex != nextIndex:
      return defLevel
  return -1
  
  
def buildWay(curLevel, endLevel, curWay, worldState, answer):
  offset = -1
  try:
    offset = worldState.index(curLevel)
  except ValueError:
    print "Invalid index:", curLevel
  indexes = map(lambda w : getNextWay(offset, w, worldState), eggWays)
  newWorldState = worldState[:]
  newWorldState[offset] = 0xF0
  indexesPairs = [(x,y) for (y,x) in enumerate(indexes)]
  indexesPairs = extractUnique(indexesPairs)
  for pair in indexesPairs:
    nextIndex, eggNo = pair
    if nextIndex == -1:
      answer.append(curWay)
    elif nextIndex == endLevel:
      result = curWay[:] + [pair]
      answer.append(result)
    else:
      newCurWay = curWay[:] + [pair]
      #print newCurWay
      buildWay(nextIndex, endLevel, newCurWay, newWorldState, answer)
    
    
def getPathes(levelNo):
  answer = []
  buildWay(beginIndexes[levelNo], endIndexes[levelNo], [(beginIndexes[levelNo],-1)], worldStates[levelNo], answer)
  return answer
###

def findShortest(ways):
  ans = []
  minLen = 32
  for way in ways:
    if len(way)<minLen:
      minLen = len(way)
  ans = filter(lambda x: len(x) == minLen, ways)
  return ans
  
def findLongest(ways):
  ans = []
  maxLen = 0
  for way in ways:
    if len(way)>maxLen:
      maxLen = len(way)
  ans = filter(lambda x: len(x) == maxLen, ways)
  return ans
  
def getLevelCounts(worldState):
  return len(filter(lambda x:x < 0x50, worldState))
  
def printWay(way):
  for x in xrange(len(way)):
    print hex(way[x][0]),
    if x < len(way)-1:
      print "->(%d)->"%way[x+1][1],
  print ""

def analyzeLevels():
  for x in xrange(8):
    ans = getPathes(x)
    shortest = findShortest(ans)
    longest = findLongest(ans)
    levelCount = getLevelCounts(worldStates[x])
    print "World ", x
    print "Levels count:", levelCount
    print "Shortest way:"
    for x in shortest:
      print "   ",
      printWay(x)
    print "  (length:%d)"%len(x)
    print "Longest way:",  
    printWay(longest[0]),
    print "  (length:%d)"%len(longest[0])