}:+()___ [Smile], ты хоть в этом году и не занял призовое в финале, но хотелось бы услышать, как у тебя всё работает. По опыту предыдущих лет, твоя стратегия обычно всё же отличается от других. Как минимум, в ней больше математики.
Если лень писать статью, то хотя-бы пост в топике на форуме хотелось бы
ud1, ну и ждём твоё описание/сорцы, в дополнение к видео
В общем, моя стратегия. В одном файле, ибо я ленивый, как ud1.
Общая схема у меня такая же, как и у всех топов, пройдусь по отдельным подсистемам.
Поиск пути у меня похожий на таковой у sskolot.
Сначала были карты, построенные волновым алгоритмом по клеткам, для каждой целевой точки по одной.
Потом вместо клетки я сделал 12 направлений в ней (4 прямых и 8 диагональных), взял с потолка матрицы переходов, и генерировал карту (многоуровневую) для всей трассы.
После, вместо одного значения на клетку стал считать псевдонепрерывное расстояние до финиша с учетом ориентации машинки.
Перебор траекторий я задумывал состоящим из двух частей: построение траектории с нуля и мутация лучших.
Мутационная часть должна была помочь с недостаточной точностью предсказания физики и выправлять "уплывшие" траектории,
но, в итоге, это работало недостаточно хорошо и опыт santa324 показал, что лучше было бы заняться оптимизацией точного 10-итерационного предсказателя.
Ну, а теперь, самое интересное — генератор траекторий.
В первых версиях траектории набирались из кусков некоторой фиксированной полной продолжительности, внутри которых была пара поворотов в случайные моменты времени.
Причем, я давал машинке, после достижения времени окончания куска, проехать еще пару тайлов и запоминал состояние в момент пересечения границ этих тайлов.
Из всех таких состояний для разных траекторий выживали только с максимальным пройденным путем (в тайлах) и максимальным без единицы.
Для этих двух расстояний выживала не одна лучшая или, наоборот, все траектории; я проводил классификацию состояний машинки и запоминал лучшее в каждой группе.
Классификация была по положению в тайле (2 или 4 группы на границе клетки) и ориентации (16 вариантов), потом добавился 1 бит от модуля скорости.
В качестве стартовых состояний для следующего куска траектории я брал все сохранившиеся из группы пред-максимальных по расстоянию.
Также со всеми сгенерированными траекториями конкурировал соответствующий кусок лучшей стратегии с прошлого тика.
Добавив поддержку тормоза в старую схему, задействовав ранее неиспользованный вариант с двумя поворотами в одну сторону, я понял, что это тупик.
В итоге, сделал универсальную схему: план движения описывается набором действий в разные моменты времени (поворот {−1, 0, +1}, газ {−1, +1}, тормоз on/off, нитро).
Для генерации куска траектории исполняется байткод общего вида с командами типа: выполнить действие, случайное/фиксированное ожидание, безусловный переход и раздвоение на относительное смещение.
Команда "раздвоения" рекурсивно исполняла обе ветки: со следующей команды и по смещению.
После этого моя машинка научилась ездить задом и использовать нитро.
Ездила задом она плохо, поэтому я стал допиливать механизм генерации.
Вместо одной программы стало несколько, каждая со своей продолжительностью в тиках.
Из всех программ выбирались те, что соответствовали текущему состоянию управления машинки.
Теперь машинки не ехали два тайла после достижения времени окончания, а запоминались все пересечения тайлов, которые в плюс по дистанции, за время работы программы.
Из этих прохождений тайлов, для продолжения генерации, по прежнему, выбирались два последних, однако, сама генерация шла не фиксированное количество раз, а до достижения целевого расстояния (8 тайлов).
Где-то в это время мне надоело вручную высчитывать смещения для операций перехода и я запилил ассемблер байткода с текстовыми метками :)
Для всякой стрельбы и полива маслом я предсказывал положение врагов по 3-м сценариям: тапка в пол и поворот на {−1, 0, +1} и брал наихудший результат стрельб.
Для езды в паре сделал избегание своих выбранных тракторий, однако это часто приводило к тому, что лидер тормозил и пропускал отстающего, поэтому ближняя машинка к финишу стала ездить без оглядки на дальнюю.
Ну и перебирал дикое количество разных функций оценок и коэффициентов.
P. S. Надо будет в следующий раз сесть за неделю до бета-теста и запилить фреймворк для визуализации, а то уже 4-й конкурс руки не доходят (в первых 2-х у меня был модный ASCII-арт, но сейчас его уже не хватает).
P. P. S. Размер моей стратегии из года в год монотонно растет: 42k, 50k, 73k, 87k. Боюсь подумать, что будет дальше.
− Скрыть
метод pk_delta_mul_n_x_bons - оценочная функция по которой выбирается план
struct t_plan_result{
...
real bons_mass()const
{
real out=0;
out+=nit*75;
out+=bon>1?bon*350:bon*125;
out+=pro*45;
out+=oil*10;
out+=kit*40;
return 1.0+out*0.075;
}
real penalty_koef()const{
return (1.0-err*inv_max_err)*(1.0-real(cd2fails)/real(n*2));
};
real delta()const{
return way.delta();
}
real pk_delta()const
{
return penalty_koef()*delta();
}
real pk_delta_mul_n_x_bons()const
{
return penalty_koef()*delta()*n*bons_mass();
}
};// функция генерирующая траектории.
static i_plan_laws&v73(const t_car_body&car,vector<t_plan>&arr,int n)
{
real maxspeed=28.1;real dspd=4; real dang=0.125;
if(car.v.Mag()>24){maxspeed=48.1;dspd=3.5;dang=0.1;}
for(int ep=-1;ep<=+1;ep++)if(ep==1)
{
qap_add_back(arr).set(car).addlim(n,ep,0,99);
for(int wt=-1;wt<=+1;wt++)
{
if(wt!=0)
{
qap_add_back(arr).set(car).addlim(n,ep,wt,99);
qap_add_back(arr).set(car).addlim(n,ep,wt*0.01,99);
qap_add_back(arr).set(car).addlim(n,ep,wt*0.05,99);
for(real k=dang;k<=1.0001;k+=dang)for(int speed=8;speed<=maxspeed;speed+=4){
qap_add_back(arr).set(car).addlim(n,ep,wt*k,speed);
}
}
if(wt!=0)
{
for(real k=dang;k<=1.0001;k+=dang)for(int speed=8;speed<=maxspeed;speed+=4){
qap_add_back(arr).set(car).addlim(n/3,ep,-wt*k*1.2,speed).addlim(n,ep,wt*k,speed);
}
for(real k=dang;k<=1.0001;k+=dang)for(int speed=8;speed<=maxspeed;speed+=4){
qap_add_back(arr).set(car).addlim(n/3,ep,-wt*k,speed).addlim(n,ep,wt*k*1.2,speed);
}
for(real k=dang;k<=1.0001;k+=dang)for(int speed=8;speed<=maxspeed;speed+=4){
qap_add_back(arr).set(car).addlim((n*2)/3,ep,-wt*k,speed).addlim(n,ep,wt*k*1.2,speed*0.33);
}
for(real k=dang;k<=1.0001;k+=dang)for(int speed=8;speed<=maxspeed;speed+=4){
qap_add_back(arr).set(car).addlim((n*1)/8,ep,-wt*k,speed).addlim((n*6)/8,ep,wt*k,speed).addlim((n*7)/8,ep,wt*k,speed*0.25).addlim(n,ep,wt*k,speed);
}
}
}
}
return dmn_with_ddn::get();
}
Класс конвертирующий тип тайла в фрагмент карты размером 10x10. Вся карта собирается из этих фрагментов.
struct t_tile{
t_map map;
string gen(const string&s){
string d;
map.w=10;
map.h=10;
map.mem.resize(100);
if(s.size()!=100)QapNoWay()
for(int i=0;i<10;i++)d+=s.substr(i*10,10)+"\n";
int gg=1;
for(int i=0;i<100;i++){
map.mem[i]=bool(s[i]=='.');
}
return d;
}
string toStr(){return map.toStr();}
void rot(int n=1){
auto src=toStr();
for(int i=0;i<n;i++)
{
t_map out=map;
for(int y=0;y<map.h;y++)for(int x=0;x<map.w;x++){
out.get(map.h-y-1,x)=map.get(x,y);
}
map=out;
auto dmg=toStr();
int gg=1;
}
}
void VERTICAL(){string line="X........X";string out;for(int i=0;i<10;i++)out+=line;gen(out);}
void HORIZONTAL(){VERTICAL();rot();}
void LEFT_TOP_CORNER(){string h="XXXXXXXXXX";string out=h;for(int i=0;i<8;i++)out+="X.........";gen(out+"X........X");}
void RIGHT_TOP_CORNER(){LEFT_TOP_CORNER();rot(1);}
void RIGHT_BOTTOM_CORNER(){LEFT_TOP_CORNER();rot(2);}
void LEFT_BOTTOM_CORNER(){LEFT_TOP_CORNER();rot(3);}
void LEFT_HEADED_T(){string h="X........X";string out=h;for(int i=0;i<8;i++)out+=".........X";gen(out+h);}
void TOP_HEADED_T(){LEFT_HEADED_T();rot(1);}
void RIGHT_HEADED_T(){LEFT_HEADED_T();rot(2);}
void BOTTOM_HEADED_T(){LEFT_HEADED_T();rot(3);}
void CROSSROADS(){string h="X........X";string out=h;for(int i=0;i<8;i++)out+="..........";gen(out+h);}
void EMPTY(){string s;s.resize(100,'.');gen(s);}
void UNKNOWN(){return EMPTY();}
#define LIST(F)\
F(EMPTY );\
F(VERTICAL );\
F(HORIZONTAL );\
F(LEFT_TOP_CORNER );\
F(RIGHT_TOP_CORNER );\
F(RIGHT_BOTTOM_CORNER);\
F(LEFT_BOTTOM_CORNER );\
F(LEFT_HEADED_T );\
F(TOP_HEADED_T );\
F(RIGHT_HEADED_T );\
F(BOTTOM_HEADED_T );\
F(CROSSROADS );\
F(UNKNOWN );\
int test()
{
string log;
#define F(NAME)NAME();log+=#NAME"\n";log+=toStr()+"\n";
LIST(F)
#undef F
int gg=1;
return 0;
}
static const t_map&make(const TileType&type){
#define F(NAME)if(type==::NAME){static t_tile t;if(t.map.mem.empty())t.NAME();return t.map;}
LIST(F)
#undef F
QapNoWay()
static t_map fail;
return fail;
}
#undef LIST
};
метод заливающий карту модифицированным волновым алгоритмом и по ней определяется расстояние до waypoint`а.
bool find_way(t_map&out,const vector<vec2i>&points,vec2i to)
{
bool ok=false;
const auto&gmap=g_buff.g_map;
t_map map=gmap;
map.fill(1000000);
vector<vec2i> cur;
vector<vector<vec2i>> t2np;
cur.resize(points.size());
auto add=[&](const vec2i&p,int mass)->bool
{
if(!gmap.check(p))return false;
if(!gmap.get_unsafe(p))return false;
auto&c=map.get(p);
if(c<=mass)return false;
c=mass;
for(;t2np.size()<=mass;)qap_add_back(t2np);
qap_add_back(t2np[mass])=p;
return true;
};
for(int i=0;i<points.size();i++){
add(points[i],0);
};
for(int t=0;t<t2np.size();t++)
{
if(t2np[t].empty())continue;
vector<int> t2n;
t2n.resize(t2np.size());for(int i=0;i<t2n.size();i++)t2n[i]=t2np[i].size();
cur=std::move(t2np[t]);
for(int i=0;i<cur.size();i++)
{
auto&p=cur[i];
{vec2i dv(1,0);for(int i=0;i<4;i++){add(p+dv,t+5);dv=dv.Ort();}}
{vec2i dv(1,1);for(int i=0;i<4;i++){add(p+dv,t+7);dv=dv.Ort();}}
}
int gg=1;
}
out=std::move(map);
int result_time=out.get(to);
int end=1;
return ok;
}
метод проверяющий столкновение со стеной.
bool has_cd(const vec2d&pos,const vec2d&dir,real cr=80)
{
static auto wh=vec2d(self.getWidth(),self.getHeight())*0.5;
static auto whm=wh.Mag();
static auto offset=vec2d(1,1)*tts*0.5;
auto real_tc=world2map(pos);
if(real_tc.y<0)return true;
if(real_tc.x<0)return true;
if(real_tc.x>=this->wh.x)return true;
if(real_tc.y>=this->wh.y)return true;
auto tile_coords=tovec2i(real_tc);
auto tc=map2world_with_offset(tile_coords);
auto tile=tiles[tile_coords.x][tile_coords.y];
vec2d d=pos-tc;
for(;;)
{
#define F(COND,T)if(T==tile){\
auto wall=tts/2-cr;\
vec2d diag0=wh.UnRot(dir);\
vec2d diag1=wh.inv_x().UnRot(dir);\
{auto dv=d+diag0;if(COND)return true;}\
{auto dv=d-diag0;if(COND)return true;}\
{auto dv=d+diag1;if(COND)return true;}\
{auto dv=d-diag1;if(COND)return true;}\
}
F((dv.x>+wall)||(dv.y<-wall),RIGHT_TOP_CORNER);
F((dv.x>+wall)||(dv.y>+wall),RIGHT_BOTTOM_CORNER);
F((dv.x<-wall)||(dv.y<-wall),LEFT_TOP_CORNER);
F((dv.x<-wall)||(dv.y>+wall),LEFT_BOTTOM_CORNER);
F(dv.x>+wall,LEFT_HEADED_T);
F(dv.y>+wall,TOP_HEADED_T);
F(dv.x<-wall,RIGHT_HEADED_T);
F(dv.y<-wall,BOTTOM_HEADED_T);
#undef F
if(tile==VERTICAL){
auto wall=tts/2-cr;
if(abs(d.x)<wall-whm)break;
vec2d diag0=wh.UnRot(dir);
vec2d diag1=wh.inv_x().UnRot(dir);
real max_x=abs(d.x)+std::max(abs(diag0.x),abs(diag1.x));
if(max_x>wall)
{
return true;
}
}
if(tile==HORIZONTAL){
auto wall=tts/2-cr;
if(abs(d.y)<wall-whm)break;
vec2d diag0=wh.UnRot(dir);
vec2d diag1=wh.inv_x().UnRot(dir);
real max_y=abs(d.y)+std::max(abs(diag0.y),abs(diag1.y));
if(max_y>wall)
{
return true;
}
}
break;
}
if(!d.x||!d.y)return false;
d=vec2d::sign(d).Mul(offset);
vec2d p=tc+d;
auto tc_to_p=p-pos;
if(abs(tc_to_p.x)>cr+whm)return false;
if(abs(tc_to_p.y)>cr+whm)return false;
auto co=tc_to_p.Rot(dir);
if(abs(co.y)>wh.y+cr)return false;
if(abs(co.x)>wh.x+cr)return false;
auto v=vec2d::sign(co).Mul(wh);
if((v-co).SqrMag()>cr*cr)return false;
int gg=1;
return true;
}
запись в t_plan которая генерирует t_move.
struct t_plan_rec{
int tick;
t_move sys_move;
real speed_limit;
t_plan_rec(){tick=-1;speed_limit=-1;}
t_move get_move(const t_car_body&car)
{
t_move out=sys_move;
if(speed_limit>=0)if(car.v.SqrMag()>speed_limit*speed_limit)out.br=true;
return out;
}
t_plan_rec with_offset(int offset)const
{
t_plan_rec out=*this;
out.tick+=offset;
return out;
}
};
struct t_plan{
string info;
vector<t_plan_rec> arr;
t_plan_result result;
t_car_body current;
t_plan_rec&add(int tickОшибка: Длина поля Текст сообщения превышает допустимые 10000 символов.
