CodeTanks

*** m3d.py ***
---
import math as math

class Vector:
    def __init__(self,x,y):
        self.x = x
        self.y = y

def VectorAdd(v1, v2):
    return Vector( v1.x + v2.x, v1.y + v2.y )

def VectorSub(v1, v2):
    return Vector( v1.x - v2.x, v1.y - v2.y )

def VectorNeg(v):
    return Vector( -v.x, -v.y )

def VectorLength(v):
    return math.hypot(v.x,v.y)

def VectorNormalize(v):
    len = VectorLength(v)
    return Vector( v.x / len, v.y / len ) if len != 0 else Vector(0,0)

def VectorSetLength(v, len):
    norm = VectorNormalize(v)
    return Vector( norm.x*len, norm.y*len)

def VectorRotate(v,angle,origin):
    vec = VectorSub(v,origin)
    rotated = Vector( vec.x * math.cos(angle) - vec.y * math.sin(angle),  vec.y * math.cos(angle) + vec.x * math.sin(angle) )
    return VectorAdd( rotated, origin )

class BBox:
    def __init__(self,mid,ext):
        self.mid = mid
        self.ext = Vector(math.fabs(ext.x),math.fabs(ext.y))

    def Lines(self):
        v1 = Vector( self.mid.x - self.ext.x, self.mid.y - self.ext.y)
        v2 = Vector( self.mid.x + self.ext.x, self.mid.y - self.ext.y)
        v3 = Vector( self.mid.x - self.ext.x, self.mid.y + self.ext.y)
        v4 = Vector( self.mid.x + self.ext.x, self.mid.y + self.ext.y)
        return ( Line(v1,v2), Line(v2,v3), Line(v3,v4), Line(v4,v1) )

    def Mid(self):
        return self.mid

class OBBox:
    def __init__(self,box,angle):
        self.box = box
        self.angle = angle

    def Lines(self):
        v1 = Vector( self.box.mid.x - self.box.ext.x, self.box.mid.y - self.box.ext.y)
        v2 = Vector( self.box.mid.x + self.box.ext.x, self.box.mid.y - self.box.ext.y)
        v3 = Vector( self.box.mid.x - self.box.ext.x, self.box.mid.y + self.box.ext.y)
        v4 = Vector( self.box.mid.x + self.box.ext.x, self.box.mid.y + self.box.ext.y)
        v1 = VectorRotate( v1, self.angle, self.box.mid )
        v2 = VectorRotate( v2, self.angle, self.box.mid )
        v3 = VectorRotate( v3, self.angle, self.box.mid )
        v4 = VectorRotate( v4, self.angle, self.box.mid )
        return ( Line(v1,v2), Line(v2,v3), Line(v3,v4), Line(v4,v1) )

    def Mid(self):
        return self.box.Mid()

class Ray:
    def __init__(self,pos,dir):
        self.pos = pos
        self.dir = dir

def makeRay( pos, angle):
    dir = Vector( math.cos(angle), math.sin(angle))
    return Ray(pos,dir)

def makeLineFromRay( ray, len ):
    end = VectorAdd( VectorSetLength( ray.dir, len ), ray.pos )
    return Line( ray.pos, end )

class Line:
    def __init__(self,beg,end):
        self.beg = beg
        self.end = end

def intersectsLineRay(ray,line):
    x1_,y1_ = ray.pos.x, ray.pos.y
    x2_,y2_ = ray.pos.x + ray.dir.x, ray.pos.y + ray.dir.y
    x3_,y3_ = line.beg.x, line.beg.y
    x4_,y4_ = line.end.x, line.end.y
    ##Make sure the lines aren't parallel
    if ((y2_ - y1_) / (x2_ - x1_) != (y4_ - y3_) / (x4_ - x3_)):
        d = (((x2_ - x1_) * (y4_ - y3_)) - (y2_ - y1_) * (x4_ - x3_))
        if (d != 0):
            r = (((y1_ - y3_) * (x4_ - x3_)) - (x1_ - x3_) * (y4_ - y3_)) / d
            s = (((y1_ - y3_) * (x2_ - x1_)) - (x1_ - x3_) * (y2_ - y1_)) / d
            if (r >= 0):
                if (s >= 0 and s <= 1):
                    return True
    return False

def intersectsLineLine(l1,l2):
    x1, y1 = l1.beg.x, l1.beg.y
    x2, y2 = l1.end.x, l1.end.y
    x3, y3 = l2.beg.x, l2.beg.y
    x4, y4 = l2.end.x, l2.end.y

    bx = x2 - x1;
    by = y2 - y1;
    dx = x4 - x3;
    dy = y4 - y3;
    b_dot_d_perp = bx * dy - by * dx;
    if b_dot_d_perp == 0:
        return None
    cx = x3 - x1
    cy = y3 - y1
    t = (cx * dy - cy * dx) / b_dot_d_perp
    if t < 0 or t > 1:
        return None

    u = (cx * by - cy * bx) / b_dot_d_perp;
    if(u < 0 or u > 1):
        return None
    return Vector(x1+t*bx, y1+t*by)

def intersectsBoxRay(ray,box):
    lines = box.Lines()
    for l in lines:
        if intersectsLineRay(ray,l):
            return True
    return False

def intersectsBoxLine(line,box):
    lines = box.Lines()
    for l in lines:
        if intersectsLineLine(line,l):
            return True
    return False
---

*** const.py ***
---
from model.TankType import TankType

class K:
    RegularShellSpeed = 16
    PremiumShellSpeed = 13
    ShellSize = 8
    CellSize = 80

    RotationAcceleration = { #angular acceleration coefficient
                        TankType.MEDIUM         : 0.000837,
                        TankType.HEAVY          : 0.000296,
                        TankType.TANK_DESTROYER : 0.000254
                      }
    #maxRotAccOnSpot = self.rotAcc * me.engine_rear_power_factor
    RotationResistance = { #tank rotation resistance coefficient
                        TankType.MEDIUM         : 0.0205,
                        TankType.HEAVY          : 0.0144,
                        TankType.TANK_DESTROYER : 0.0141
                      }
    #self.rotMomentum = 1 - self.rotRes
---

*** Grid.py ***
---
import math as math
from m3d import *
from const import K

class Grid:
    def __init__(self,width,height):
        self.width = math.ceil(width/K.CellSize)
        self.height = math.ceil(height/K.CellSize)
        self.busy = bytearray([0 for i in range(0, self.width*self.height)])
        self.danger = bytearray([0 for i in range(0, self.width*self.height)])

    def FillObtacles(self,list,width):
        def distanceFactor(item,pos):
            distance = item.get_distance_to(pos.x, pos.y)
            return 1 if distance < item.width/2 + width/2 else 0

        for i in range(0,self.height*self.width):
            pos = self.CellToVector(i)
            val = 0
            for item in list:
                val = max( val, distanceFactor(item,pos) )
            self.busy[i] = val

    def CalculateDanger(self,cell,tanks,shels):
        width = 300
        def distanceFactor(item,pos):
            distance = item.get_distance_to(pos.x, pos.y)
            val = 100 if distance < item.width/2 else (  50 + 50 * (item.width/2 + width/2 - distance) / (item.width/2 + width/2) if distance < (item.width/2 + width/2) else 0 )
            #box = BBox(pos, Vector(K.CellSize/2,K.CellSize/2))
            #ray = makeRay(item,item.angle + item.turret_relative_angle)
            #val = val + (100 if intersectsBoxRay(ray,box) else 0)
            return val

        def shellFactor(item,pos):
            box = BBox(pos, Vector(K.CellSize/2,K.CellSize/2))
            ray = makeRay(item,item.angle)
            return 255 if intersectsBoxRay(ray,box) else 0

        pos = self.CellToVector(i)
        val = 0 if i > self.width and i < (self.height-1)*self.width and i % self.width not in [0, self.width-1] else 100
        for item in tanks:
            val = val + distanceFactor(item,pos)
        for item in shells:
            val = val + shellFactor(item,pos)
        return val


    def FillDanger(self,tanks,shells):
        for i in range(0,self.height*self.width):
            val = self.CalculateDanger(i,tanks,shell)
            self.danger[i] = int(val) if val < 255 else 255

    def GetDanger(self,pos):
        start = self.VectorToCell(pos)
        return self.danger[start]

    def VectorToCell(self,v):
        return math.floor(v.y/K.CellSize)*self.width + math.floor(v.x/K.CellSize)

    def CellToVector(self,c):
        return Vector( (c%self.width)*K.CellSize + K.CellSize/2, math.floor(c/self.width)*K.CellSize + K.CellSize/2 )

    def naighbors(self,e,full):
        def check(e,width,height,busy):
            if e >= 0 and e < width*height:
                if busy[e] == 0:
                    return e
            return None

        ret = []
        c = e - self.width
        if check(c,self.width,self.height,self.busy) != None:
            ret.append(c)
        c = e - 1
        if check(c,self.width,self.height,self.busy) != None:
            if e % self.width > 0:
                ret.append(c)
        c = e + 1
        if check(c,self.width,self.height,self.busy) != None:
            if e % self.width < self.width - 1:
                ret.append(c)
        c = e + self.width
        if check(c,self.width,self.height,self.busy) != None:
            ret.append(c)

        if full == True:
            if e % self.width > 0:
                c = e - self.width - 1
                if check(c,self.width,self.height,self.busy) != None:
                    ret.append(c)
                c = e + self.width - 1
                if check(c,self.width,self.height,self.busy) != None:
                    ret.append(c)

            if e % self.width < self.width - 1:
                c = e - self.width + 1
                if check(c,self.width,self.height,self.busy) != None:
                    ret.append(c)
                c = e + self.width + 1
                if check(c,self.width,self.height,self.busy) != None:
                    ret.append(c)

        return ret

    def NewWave(self,waveGrid,num,oldList):
        newList = []
        for e in oldList:
            n = self.naighbors(e,False)
            for c in n:
                if waveGrid[c] > num:
                    newList.append(c)
                    waveGrid[c] = num

        return newList

    def MakePath(self,waveGrid,targetCell):
        pos = self.CellToVector(targetCell)
        num = waveGrid[targetCell]
        movingScenario = []

        while num > 1:
            prevWave = self.naighbors(targetCell,True)
            bestDistance = math.pow(K.CellSize*2,2) ## bigger value
            bestPos = None
            bestCell = None
            bestNum = num
            for c in prevWave:
                if waveGrid[c] < num:
                    newPos = self.CellToVector(c)
                    newLen = math.hypot(newPos.x - pos.x,newPos.y - pos.y)
                    if (newLen < bestDistance and waveGrid[c] == bestNum) or waveGrid[c] < bestNum:
                        bestNum = waveGrid[c]
                        bestDistance = newLen
                        bestPos = newPos
                        bestCell = c

            num = bestNum
            targetCell = bestCell
            pos = self.CellToVector(targetCell)
            movingScenario.append(pos)

        return movingScenario

    def FindPath(self, pos, items, maxPath):
        if len(items) == 0:
            return None,None

        itemsCells = [ self.VectorToCell(item) for item in items ]

        waveGrid = bytearray([255 for j in range(0, self.width*self.height)])
        start = self.VectorToCell(pos)
        waveGrid[start] = 0
        num = 0
        itemsInWave = []
        cellOfItems = []
        wave = [start]
        while num < maxPath/K.CellSize and len(itemsInWave) == 0 and len(wave) > 0:
            num = num + 1
            wave = self.NewWave(waveGrid, num, wave)

            for cell in wave:
                if cell in itemsCells:
                    item = items[itemsCells.index(cell)]
                    itemsInWave.append(item)
                    cellOfItems.append(cell)
                    break

        if len(itemsInWave) != 0:
            targetItem = itemsInWave[0]
            targetCell = cellOfItems[0]
            return [Vector(targetItem.x,targetItem.y)] + self.MakePath(waveGrid,targetCell), targetItem

        return None,None

    def FindCover(self, pos):
        waveGrid = bytearray([255 for j in range(0, self.width*self.height)])
        start = self.VectorToCell(pos)
        waveGrid[start] = 0
        num = 0
        coverVal = self.danger[start]
        coverCell = start
        wave = [start]
        while num < self.width/4 and len(wave) > 0:
            num = num + 1
            wave = self.NewWave(waveGrid, num, wave)

            for cell in wave:
                if self.danger[cell] < coverVal:
                    coverVal = self.danger[cell]
                    coverCell = cell

        return [self.CellToVector(coverCell)] + self.MakePath(waveGrid,coverCell)
---

*** MyStrategy.py ***
---
import math as math
from m3d import *
from Grid import *
from const import K
from model.FireType import FireType
from model.TankType import TankType
from model.BonusType import BonusType
from model.Tank import Tank
import time

class BonusMission:
    def __init__(self, unit):
        self.unit = unit

    def check(self, world):
        id = self.unit.id
        for unit in world.bonuses:
            if unit.id == id:
                return True
        return False

def removeUnitFromList(list,units):
    ret = []
    for item in list:
        for unit in units:
            if item.id == unit.id:
                break
        else:
            ret.append(item)
    return ret

class MyStrategy:
    def __init__(self):
        self.prediction = {}
        self.mission = None
        self.target = None
        self.busyGrid = None
        self.dangerGrid = None
        self.scenario = None
        self.bonusesFrom = []
        self.targetId = None

    def select_tank(self, tank_index, team_size):
        return TankType.MEDIUM

    def move(self, me, world, move):
        if self.busyGrid == None:
            self.busyGrid = Grid(world.width,world.height)
            self.dangerGrid = Grid(world.width,world.height)

        self.prediction = self.calculatePrediction(me,world.tanks)

        #move
        if world.tick%2 == 0:
            self.busyGrid.FillObtacles(removeUnitFromList(world.tanks,[me]), me.height)
            self.busyGrid.FillDanger(self.selectEnemies(world.tanks),world.shells)

            if self.mission == None and self.scenario != None:
                if self.busyGrid.GetDanger(me) < 50:
                    self.scenario = None

            if self.busyGrid.GetDanger(me) > 150:
                self.scenario = self.busyGrid.FindCover(me)
                self.mission = None

            if self.mission != None:
                if self.mission.check(world) == False:
                    self.mission = None

            if self.scenario == None:
                needList = self.selectNeedList(me)
                if self.mission == None:
                    needBonuses = self.selectNeedBonuses(world.bonuses,needList)
                else:
                    needBonuses = [self.mission.unit] + self.selectNeedBonuses(self.selectNewBonuses(world.bonuses),needList)
                if len(needBonuses) > 0:
                    self.scenario,bonusItem = self.busyGrid.FindPath(me, needBonuses, world.width)
                    if self.scenario != None:
                        self.mission = BonusMission(bonusItem)

            if self.scenario == None:
                if self.busyGrid.GetDanger(me) > 50:
                    self.scenario = self.busyGrid.FindCover(me)

            if self.scenario == None and world.tick % 50 == 0:
                nearestBonuses = self.selectNearestBonuses(me,world.bonuses,300)
                if len(nearestBonuses) > 0:
                    self.scenario,bonusItem = self.busyGrid.FindPath(me, nearestBonuses,300)
                    if self.scenario != None:
                        self.mission = BonusMission(bonusItem)

        if self.scenario != None:
            if len(self.scenario) > 0:
                i = 0
                while i < len(self.scenario) and self.checkObtacles( Line( me, self.scenario[i]), me.height, removeUnitFromList(world.tanks,[me]) ) == True:
                    i = i + 1

                self.scenario[i+1:] = []
                bonus = self.scenario[-1]
                if me.get_distance_to_unit(bonus) > me.height:
                    self.moveTo(me, bonus, move)
                else:
                    self.scenario.pop()
            else:
                self.scenario = None

        # save bonuses
        self.bonusesFrom = world.bonuses
        # fire
        if self.targetId != None:
            target = self.findItemWithId(world.tanks,self.targetId)
            if target != None and (target.crew_health <= 0 or target.hull_durability <= 0):
                self.targetId = None
                target = None

        if self.targetId == None or world.tick % 50 == 0:
            enemies = self.selectEnemies(world.tanks)
            target = self.selectBestTarget(me, enemies,world)
            if target != None:
                self.targetId = target.id

        if target != None:
            leftTracPower = (move.left_track_power if move.left_track_power>=0 else move.left_track_power * me.engine_rear_power_factor)
            rightTracPower =(move.right_track_power if move.right_track_power>=0 else move.right_track_power * me.engine_rear_power_factor)
            rotationSpeed = me.angular_speed * (1 - K.RotationResistance[me.type]) + K.RotationAcceleration[me.type] *  (me.crew_health/me.crew_max_health) * (leftTracPower - rightTracPower) / 2

            predictedCoord = self.prediction[self.targetId]
            angle = me.get_turret_angle_to(predictedCoord.x, predictedCoord.y)
            angle = angle - rotationSpeed
            if angle > 0:
                move.turret_turn = me.turret_turn_speed
            elif angle < 0:
                move.turret_turn = -me.turret_turn_speed

            if me.remaining_reloading_time == 0 and world.tick != 0:
                predicted = self.prediction[target.id]
                if  intersectsBoxRay(makeRay(me, me.angle+me.turret_relative_angle), OBBox( BBox(predicted, Vector(target.width/4,target.height/4)), target.angle)):
                    obtacles = removeUnitFromList(world.tanks,[me,target]) + world.bonuses
                    if self.checkObtacles(Line(me,predicted),K.ShellSize, obtacles) == False:
                        if me.get_distance_to_unit(predicted) / K.PremiumShellSpeed < 20 or me.premium_shell_count > 2:
                            move.fire_type = FireType.PREMIUM_PREFERRED
                        else:
                            move.fire_type = FireType.REGULAR

            if world.tick == 0:
                move.fire_type = 0

###########################################################################3
    def selectNeedList(self,me):
        ret = []
        if me.crew_health/me.crew_max_health < 0.6:
            ret.append(BonusType.MEDIKIT)
        if me.hull_durability / me.hull_max_durability < 0.6:
            ret.append(BonusType.REPAIR_KIT)
        return ret

    def selectNeedBonuses(self,bonuses,needList):
        ret = []
        for bonus in bonuses:
            if bonus.type in needList:
                ret.append(bonus)
        return ret

    def selectEnemies(self, tanks):
        result = [tank for tank in tanks if (tank.crew_health > 0 and tank.hull_durability > 0 and tank.teammate == False)]
        return result

    def selectTanksWhoCanShootMe(self, me, tanks):
        result = []
        for tank in tanks:
            angle = tank.get_turret_angle_to_unit(me)
            if math.fabs(angle) < math.pi/18:
                result.append(tank)
        return result

    def selectBestTarget(self, me, targets,world):
        bestTarget = None
        maxRating = 0
        for tank in targets:
            angle = me.get_turret_angle_to(self.prediction[tank.id].x, self.prediction[tank.id].y)
            obtacles = removeUnitFromList(world.tanks,[me,tank]) + world.bonuses
            if self.checkObtacles(Line(me,self.prediction[tank.id]),K.ShellSize, obtacles) == False:
                angle = angle if math.fabs(angle) > 0.1 else 0.1
                distance = me.get_distance_to_unit( tank )
                rating = 100 / ( math.fabs(angle)/math.pi * distance)
                if rating > maxRating:
                    maxRating = rating
                    bestTarget = tank
        return bestTarget

    def sheckShells(self,me,shells,obtacles):
        pass

    def checkObtacles(self,line,width,units):
        for unit in units:
            if intersectsBoxLine(line,BBox( unit, Vector( unit.width/2 + width/2, unit.width/2 + width/2 ) ) ):
                return True
        return False

    def selectNearestBonuses(self, me, bonuses, maxDistance):
        ret = []
        for bonus in bonuses:
            distance = me.get_distance_to_unit(bonus)
            if distance < maxDistance:
                ret.append(bonus)
        return ret

    def selectNewBonuses(self,bonuses):
        ret = []
        for bonus in bonuses:
            if self.findItemWithId(self.bonusesFrom, bonus.id) == None:
                ret.append(bonus)
        return ret

    def findItemWithId(self,list,id):
        for item in list:
            if item.id == id:
                return item
        return None

    def calculatePrediction(self, me, list):
        predicted = {}
        for tank in list:
            distance = me.get_distance_to_unit(tank)
            timeToImpact = distance / (K.PremiumShellSpeed if me.premium_shell_count > 0 else K.RegularShellSpeed)
            predicted[tank.id] = VectorAdd( tank, VectorSetLength( Vector(tank.speedX, tank.speedY), timeToImpact ) )
        return predicted

    def moveTo(self, me, pos, move):
        angle = me.get_angle_to(pos.x, pos.y)

        if math.fabs(angle) < 3*math.pi/4:
            if angle > 0:
                move.left_track_power = 1.0
                move.right_track_power = 2.0*math.pow(math.cos(math.fabs(angle)),2) - 1.0
            elif angle < 0:
                move.left_track_power = 2.0*math.pow(math.cos(math.fabs(angle)),2) - 1.0
                move.right_track_power = 1.0
            else:
                move.left_track_power = 1.0
                move.right_track_power =1.0
        else:
            if angle < math.pi:
                move.left_track_power = -1.0
                move.right_track_power = 1.0 - 2.0 * math.pow(math.cos(math.fabs(math.pi-angle)),2)
            elif angle > -pi:
                move.left_track_power = 1.0 - 2.0 * math.pow(math.cos(math.fabs(math.pi-angle)),2)
                move.right_track_power = -1.0
            else:
                move.left_track_power = -1.0
                move.right_track_power = -1.0
---