Автор работы: Пользователь скрыл имя, 26 Февраля 2013 в 06:52, курсовая работа
Данная курсовая работа посвящена разработке алгоритма интеллектуального управления танком для участия в конкурсе «Российский кубок по программированию искусственного интеллекта CodeTanks 2012 (Russian AI Cup)». В работе рассмотрены принципы наиболее эффективного поведения танка, позволяющие ему эффективно передвигаться по полю, минимизировать повреждения от танков оппонентов и набирать как можно большее количество очков за счет уничтожения танков оппонентов. Алгоритм реализован на языке программирования Python 2.7.3 в среде разработки JetBrains PyCharm 2.6.3.
Введение 3
1 О мире CodeTanks 2012 4
1.1Общие положения и правила 4
1.2 Описание игрового мира 5
1.3 Описание танков 7
1.4 Описание снарядов и механики попаданий 9
1.5 Описание бонусов 10
1.6 Начисление баллов 11
2 Стратегия управления танком 12
2.1 Выбор танка 12
2.2 Принципы поведения танка 14
2.2.1 Движение танка 15
2.2.1.1 Уворот 19
2.2.1.2 Рикошет 20
2.2.2 Стрельба 22
Заключение 24
Список использованной литературы 25
Приложение А 26
в рассчитанном положении, то доверительный угол для попадания по цели уменьшен так, как будто диагональ цели вдвое меньше.
Доверительный угол – это угол, на который необходимо повернуть башню, чтобы с достаточной степенью уверенности попасть в цель.
Подробнее поворот башни продемонстрирован на рисунке 9.
Рисунок 9. Определение угла, до которого необходимо повернуть башню
а) до статичной цели; б) до движущейся цели
α – доверительный угол для статичной цели
β – доверительный угол для движущейся цели
Штриховой линией обозначено предсказанное положение танка через время полета снаряда.
Изм.
Лист
№ докум.
Подпись
Дата
Лист
24
1304.123074.000 ПЗ
Заключение
В результате проведенной работы реализован алгоритм управления танком для конкурса «Российский кубок по программированию искусственного интеллекта CodeTanks 2012 (Russian AI Cup)». Рассмотрены различные варианты поведения танка в зависимости от событий на поле.
Реализованный алгоритм занял
восьмидесятое место среди
Изм.
Лист
№ докум.
Подпись
Дата
Лист
25
1304.123074.000 ПЗ
Список использованной литературы
Исходный код алгоритма
Модуль MyStrategy.py
from math import *
from model.FireType import FireType
from model.TankType import TankType
from model.Unit import Unit
from Head import Head
from Dodge import Dodge
from Calculation import Calculation
from TankMedium import TankMedium
from TankDestroyer import TankDestroyer
from TankHeavy import TankHeavy
class MyStrategy:
def __init__(self):
self.my_tanks = {}
def move(self, me, world, move):
if not me.id in self.my_tanks:
if me.type == TankType.TANK_DESTROYER:
self.my_tanks[me.id] = TankDestroyer()
elif me.type == TankType.MEDIUM:
self.my_tanks[me.id] = TankMedium()
elif me.type == TankType.HEAVY:
self.my_tanks[me.id] = TankHeavy()
self.my_tanks[me.id].move(me, world, move)
def select_tank(self, tank_index, team_size):
if team_size == 1:
return TankType.MEDIUM
elif team_size == 2:
if tank_index == 0:
return TankType.HEAVY
else:
return TankType.MEDIUM
Модуль Calculation.py
# -*- coding: utf-8 -*-
from __future__ import division
from bisect import bisect
import copy
from Factor import Factor
from model.ShellType import ShellType
__author__ = 'yokre_000'
from math import *
class Calculation:
@staticmethod
def choose_shell_type(me, unit):
if me.premium_shell_count > 0 and me.get_distance_to_unit(unit) < 700:
return ShellType.PREMIUM
return ShellType.REGULAR
@staticmethod
def get_new_pos(tank, time, power = 1):
# оттестирован, работает
if time > Factor.MAX_TIME - 1: time = Factor.MAX_TIME - 1
F = Factor.F_POWER[tank.type] * power
if power < 0:
F *= tank.engine_rear_power_factor
F *= (tank.crew_health + tank.crew_max_health) / tank.crew_max_health / 2
s = sqrt(tank.speedX ** 2 + tank.speedY ** 2) * Factor.K_V[tank.type][time] + F * Factor.K_F[tank.type][time]
x = tank.x + s * cos(tank.angle)
y = tank.y + s * sin(tank.angle)
if x > 1280 - tank.width/2:
x = 1280 - tank.width/2
elif x < tank.width/2:
x = tank.width/2
if y < tank.width/2:
y = tank.width/2
elif y > 800 - tank.width/2:
y = 800 - tank.width/2
return x, y
@staticmethod
def can_hit_unmoving_unit(me, unit):
cos_angle = cos(unit.angle)
sin_angle = sin(unit.angle)
width = unit.width + 4
height = unit.height + 4
x1 = unit.x + cos_angle*width / 2 + sin_angle*height / 2
x2 = unit.x - cos_angle*width / 2 + sin_angle*height / 2
x3 = unit.x - cos_angle*width / 2 - sin_angle*height / 2
x4 = unit.x + cos_angle*width / 2 - sin_angle*height / 2
y1 = unit.y + sin_angle*width / 2 - cos_angle*height / 2
y2 = unit.y - sin_angle*width / 2 - cos_angle*height / 2
y3 = unit.y - sin_angle*width / 2 + cos_angle*height / 2
y4 = unit.y + sin_angle*width / 2 + cos_angle*height / 2
angles = [
me.get_turret_angle_to(x1, y1),
me.get_turret_angle_to(x2, y2),
me.get_turret_angle_to(x3, y3),
me.get_turret_angle_to(x4, y4),
]
return pi/2 > max(angles) > 0 > min(angles) > pi/-2
@staticmethod
def aimed_to_unit(me, unit):
cos_angle = cos(unit.angle)
sin_angle = sin(unit.angle)
x1 = unit.x + cos_angle*unit.width / 4 + sin_angle*unit.height / 4
x2 = unit.x - cos_angle*unit.width / 4 + sin_angle*unit.height / 4
x3 = unit.x - cos_angle*unit.width / 4 - sin_angle*unit.height / 4
x4 = unit.x + cos_angle*unit.width / 4 - sin_angle*unit.height / 4
y1 = unit.y + sin_angle*unit.width / 4 - cos_angle*unit.height / 4
y2 = unit.y - sin_angle*unit.width / 4 - cos_angle*unit.height / 4
y3 = unit.y - sin_angle*unit.width / 4 + cos_angle*unit.height / 4
y4 = unit.y + sin_angle*unit.width / 4 + cos_angle*unit.height / 4
angles = [
me.get_turret_angle_to(x1, y1),
me.get_turret_angle_to(x2, y2),
me.get_turret_angle_to(x3, y3),
me.get_turret_angle_to(x4, y4),
]
aimed = pi/2 > max(angles) > 0 > min(angles) > pi/-2
# for debug
if aimed:
return True
else:
return False
@staticmethod
def aimed_to_moving_unit(me, unit):
u = copy.deepcopy(unit)
distance = me.get_distance_to_unit(u) - me.virtual_gun_length
if distance < 0:
distance = 0
if Calculation.choose_shell_type(
time = bisect(Factor.SHELL_REGULAR_
else:
time = bisect(Factor.SHELL_PREMIUM_
if time < 0:
time = 0
u.x += u.speedX * time
u.y += u.speedY * time
return Calculation.aimed_to_unit(me, u)
@staticmethod
def turret_angle_to_moving_unit(
u = copy.deepcopy(unit)
me = copy.deepcopy(me)
distance = me.get_distance_to_unit(u) - me.virtual_gun_length
if distance < 0:
distance = 0
if Calculation.choose_shell_type(
time = bisect(Factor.SHELL_REGULAR_
else:
time = bisect(Factor.SHELL_PREMIUM_
if time < 0:
time = 0
u.x += u.speedX * time
u.y += u.speedY * time
u.angle += u.angular_speed * time
me.x += me.speedX
me.y += me.speedY
me.angle += me.angular_speed
return me.get_turret_angle_to_unit(u)
@staticmethod
def get_targets(world):
"""
Возвращает список возможных целей
"""
good_targets = []
for tank in world.tanks:
if not tank.teammate and tank.hull_durability > 0 and tank.crew_health > 0:
good_targets.append(tank)
return good_targets
@staticmethod
def get_obstacles(world, me):
"""
Возвращает список препятствий
"""
obstacles = []
if len(world.tanks) > 0:
for tank in world.tanks:
if tank.hull_durability <= 0 or tank.crew_health <= 0 or (tank.teammate and tank.id != me.id):
obstacles.append(tank)
[obstacles.append(b) for b in world.bonuses]
[obstacles.append(o) for o in world.obstacles]
return obstacles
Модуль Dodge.py
__author__ = 'Drell'
from math import *
from bisect import bisect
from model.Tank import Tank
from model.FireType import FireType
from model.Unit import Unit
from Head import Head
from Calculation import Calculation
from Factor import Factor
# Maths 7th grade, Geometry - 8th grade, Hemorrhoids - 1st grade
class point:
x = 0
y = 0
class Dodge:
#TODO
A = 0.6
def getPoints(self, unit):
# p2p1 - left track
# p2p3 - rear
# p3p4 - right track
# p4p1 - front
p1, p2, p3, p4 = point(), point(), point(), point()
p1.x = unit.x + cos(unit.angle)*unit.width/2 + sin(unit.angle)*unit.height/2
p1.y = unit.y + sin(unit.angle)*unit.width/2 - cos(unit.angle)*unit.height/2
p2.x = unit.x - cos(unit.angle)*unit.width/2 + sin(unit.angle)*unit.height/2
p2.y = unit.y - sin(unit.angle)*unit.width/2 - cos(unit.angle)*unit.height/2
p3.x = unit.x - cos(unit.angle)*unit.width/2 - sin(unit.angle)*unit.height/2
p3.y = unit.y - sin(unit.angle)*unit.width/2 + cos(unit.angle)*unit.height/2
p4.x = unit.x + cos(unit.angle)*unit.width/2 - sin(unit.angle)*unit.height/2
p4.y = unit.y + sin(unit.angle)*unit.width/2 + cos(unit.angle)*unit.height/2
return p1, p2, p3, p4
def rayIntersectsSegment(self, rX1, rY1, rX2, rY2, sX1, sY1, sX2, sY2):
# rX, rY - ray coordinates; sX, sY - line segment
# rX1, rY1 - ray start; else doesn't matter
rX1 = float(rX1)
rY1 = float(rY1)
rX2 = float(rX2)
rY2 = float(rY2)
sX1 = float(sX1)
sY1 = float(sY1)
sX2 = float(sX2)
sY2 = float(sY2)
p = point()
if (rX2*sY2 - rX1*sY2 - rX2*sY1 + rX1*sY1 - sX2*rY2 + sX1*rY2 + sX2*rY1 - sX1*rY1) == 0 or (sX2 == sX1):
if rX1 == rX2:
p.x = -1
p.y = -1
rT = -1
return p, rT
else:
rT = (sX1 - rX1) / (rX2 - rX1)
p.x = rX1 + rT*(rX2 - rX1)
p.y = rY1 + rT*(rY2 - rY1)
return p, rT
rT = (sX2*rY1 - sX1*rY1 - sX2*sY1 - rX1*sY2 + sX1*sY2 + rX1*sY1)/(rX2*sY2 - rX1*sY2 - rX2*sY1 + rX1*sY1 - sX2*rY2 + sX1*rY2 + sX2*rY1 - sX1*rY1)
sT = (rX1 + rT*(rX2 - rX1) - sX1) / (sX2 - sX1)
if (rT < 0) or (sT < 0) or (sT > 1):
p.x = -1
p.y = -1
else:
p.x = rX1 + rT*(rX2 - rX1)
p.y = rY1 + rT*(rY2 - rY1)
return p, rT
def angleBetweenLines(self, rX1, rY1, rX2, rY2, sX1, sY1, sX2, sY2):
# ax + by + c = 0
rX1 = float(rX1)
rY1 = float(rY1)
rX2 = float(rX2)
rY2 = float(rY2)
sX1 = float(sX1)
sY1 = float(sY1)
sX2 = float(sX2)
sY2 = float(sY2)
a1 = rY1 - rY2
b1 = rX2 - rX1
c1 = rX1*rY2 - rX2*rY1
a2 = sY1 - sY2
b2 = sX2 - sX1
c2 = sX1*sY2 - sX2*sY1
alpha = asin( (a1*b2 - a2*b1) / (sqrt(a1*a1 + b1*b1) * sqrt(a2*a2 + b2*b2)))
return alpha
#checks if shell first hits the unit. Range to unit in shell speed vectors and hit point. If doesn't hit range = 6666, pt = -1;-1
def hits(self, shell, unit):
p = self.getPoints(unit)
pt = point()
pt.x, pt.y = -1, -1
minD = 6666
inter,
dist = self.rayIntersectsSegment(
if inter.x > -1 and inter.y > -1:
if dist < minD:
minD = dist
pt.x, pt.y = inter.x, inter.y
inter,
dist = self.rayIntersectsSegment(
if inter.x > -1 and inter.y > -1:
if dist < minD:
minD = dist
pt.x, pt.y = inter.x, inter.y
inter,
dist = self.rayIntersectsSegment(
if inter.x > -1 and inter.y > -1:
if dist < minD:
minD = dist
pt.x, pt.y = inter.x, inter.y
inter,
dist = self.rayIntersectsSegment(
if inter.x > -1 and inter.y > -1:
if dist < minD:
minD = dist
pt.x, pt.y = inter.x, inter.y
return minD, pt
#checks if shell last hits unit. Range to unit in shell speed vectors and hit point. If doesn't hit range = -1, pt = -1;-1
def hitsThrough(self, shell, unit):
p = self.getPoints(unit)
pt = point()
pt.x, pt.y = -1, -1
maxD = -1
inter,
dist = self.rayIntersectsSegment(
if inter.x > -1 and inter.y > -1:
if dist > maxD:
maxD = dist
pt.x, pt.y = inter.x, inter.y
inter,
dist = self.rayIntersectsSegment(
if inter.x > -1 and inter.y > -1:
if dist > maxD:
maxD = dist
pt.x, pt.y = inter.x, inter.y
inter,
dist = self.rayIntersectsSegment(
if inter.x > -1 and inter.y > -1:
if dist > maxD:
maxD = dist
pt.x, pt.y = inter.x, inter.y
inter,
dist = self.rayIntersectsSegment(
if inter.x > -1 and inter.y > -1:
if dist > maxD:
maxD = dist
pt.x, pt.y = inter.x, inter.y
return maxD, pt
def rotateToDodge(self, me, shell, move):
p = self.getPoints(me)
#left side
ls, lsT
= self.rayIntersectsSegment(
#right side
rs, rsT
= self.rayIntersectsSegment(
#front side
fs, fsT
= self.rayIntersectsSegment(
frontSideAttacked = False
leftSideAttacked = False
rightSideAttacked = False
if fs.x > -1 and fs.y > -1:
frontSideAttacked = True
if ls.x > -1 and ls.y > -1:
leftSideAttacked = True
if rs.x > -1 and rs.y > -1:
rightSideAttacked = True
if frontSideAttacked:
if fsT < rsT:
rightSideAttacked = False
if fsT < lsT:
leftSideAttacked = False
if leftSideAttacked and rightSideAttacked:
if lsT < rsT:
rightSideAttacked = False
else:
leftSideAttacked = False
if leftSideAttacked:
# print 'left'
alpha = self.angleBetweenLines(p[1].x, p[1].y, p[0].x, p[0].y, shell.x, shell.y, shell.x + shell.speedX, shell.y + shell.speedY)
if alpha < 0:
if abs(alpha) > pi/9:
move.left_track_power = me.engine_rear_power_factor
move.right_track_power = -1
if abs(alpha) < pi/18:
move.left_track_power = -1
move.right_track_power = me.engine_rear_power_factor
else:
if abs(alpha) > pi/9:
move.left_track_power = -1
move.right_track_power = me.engine_rear_power_factor
if abs(alpha) < pi/18:
move.left_track_power = me.engine_rear_power_factor
move.right_track_power = -1
if rightSideAttacked:
# print 'right'
alpha = self.angleBetweenLines(p[3].x, p[3].y, p[2].x, p[2].y, shell.x, shell.y, shell.x + shell.speedX, shell.y + shell.speedY)