CodeCombat map scanner

#util.py

Pi = 3.1415926535

def utilHeartbeat():
    self.moveXY(self.pos.x, self.pos.y)

#pos.py

def pos(x, y):
    return {"x": x, "y": y}

def posDistSqr(_from, to):
    return (to.x - _from.x)**2 + (to.y - _from.y)**2

def posDist(_from, to):
    return Math.sqrt(distanceSquared(_from, to))

def posDir(_from, to):
    dx = to.x - _from.x
    dy = to.y - _from.y
    mag = Math.sqrt(dx**2 + dy**2)
    if mag < 0.001:
        return pos(0, 0)
    return pos(dx/mag, dy/mag)

def posSortByDist(_from, _items):
    items = []
    items.extend(_items)
    def selectSecond(pair):
        return pair[1]
    pairs = []
    for item in items:
        pairs.append([item, distanceSquared(_from, item.pos)])
    pairs = sorted(pairs, selectSecond)
    items = []
    for pair in pairs:
        items.append(pair[0])
    return items

def posFindNearest(_from, items):
    cur = items[0]
    curDistSqr = posDistSqr(_from, cur.pos)
    for item in items:
        itemDistSqr = posDistSqr(_from, item.pos)
        if itemDistSqr < curDistSqr:
            cur = item
            curDistSqr = itemDistSqr
    return cur

#map.py
#needs pos.py
#needs util.py

_mapGrid = []
_mapSize = {"width": 0, "height": 0}

_mapUnknown = -2
_mapInaccessible = 0
_mapReachable = 1
_mapScanStack = []
#Sample the map at a two meter resolution
_mapResFactor = 2

#initialize the map
def _mapInit():
    #begin the bucket fill from the current player location
    intPos=pos(int((self.pos.x) / _mapResFactor + 0.5), int((self.pos.y) / _mapResFactor + 0.5))
    _mapGrow(intPos.x + 1, intPos.y + 1)
    _mapGrid[intPos.y][intPos.x] = _mapReachable
    _mapScanStack.append(intPos)
    while len(_mapScanStack) > 0:
        _mapScan()
        utilHeartbeat()

    #optimized kernel application
    #to relax the reachable boundary
    repeatCount = Math.ceil(2.0 / _mapResFactor)
    for repeat in range(repeatCount):
        for x in range(_mapSize.width - 1, 0, -1):
            for y in range(_mapSize.height):
                _mapGrid[y][x] &= _mapGrid[y][x - 1]
    utilHeartbeat()

    for repeat in range(repeatCount):
        for x in range(_mapSize.width - 1):
            for y in range(_mapSize.height):
                _mapGrid[y][x] &= _mapGrid[y][x + 1]
    utilHeartbeat()

    for repeat in range(repeatCount):
        for y in range(_mapSize.height - 1, 0, -1):
            for x in range(_mapSize.width):
                _mapGrid[y][x] &= _mapGrid[y - 1][x]
    utilHeartbeat()

    for repeat in range(repeatCount):
        for y in range(_mapSize.height - 1):
            for x in range(_mapSize.width):
                _mapGrid[y][x] &= _mapGrid[y + 1][x]
    utilHeartbeat()

#ensure that _mapGrid is large enough
def _mapGrow(width, height):
    if width > _mapSize.width:
        for y in range(_mapSize.height):
            _mapGrid[y].extend([_mapUnknown]*(width - _mapSize.width))
    for y in range(_mapSize.height, height):
        _mapGrid.append([_mapUnknown]*width)
    _mapSize.width = width
    _mapSize.height = height

def _mapScan():
    #limit to 300 iterations, so heartbeats can happen
    allowedStepCount = 300
    while len(_mapScanStack) > 0 and allowedStepCount > 0:
        allowedStepCount -= 1
        #perform an iteration of the bucket fill
        current = _mapScanStack.pop()
        _mapGrow(current.x + 2, current.y + 2)
        directions = [pos(-1, 0), pos(0, -1), pos(1, 0), pos(0, 1)]
        for direction in directions:
            xOffset = direction.x
            yOffset = direction.y
            next = pos(current.x + xOffset, current.y + yOffset)
            if _mapGrid[next.y][next.x] != _mapUnknown:
                continue
            actualCurrent = pos(current.x * _mapResFactor, current.y * _mapResFactor)
            actualNext = pos(next.x * _mapResFactor, next.y * _mapResFactor)
            #use a ray trace to detect reachable grids
            passable = self.isPathClear(actualCurrent, actualNext)
            if passable:
                _mapGrid[next.y][next.x] = _mapReachable
                _mapScanStack.append(next)
            else:
                _mapGrid[next.y][next.x] = _mapInaccessible

_mapInit()