Russian AI Cup

Расширенный поиск  
Страницы: [1]

Автор Тема: объезд препятствий  (Прочитано 2122 раз)

Deo

  • Jr. Member
  • **
  • Сообщений: 47
объезд препятствий
« : Ноября 21, 2016, 05:53:05 pm »

если кто-то не сильно жадный, киньте в личку код миньонов для объезда препятствий
Записан

zuko3d

  • Jr. Member
  • **
  • Сообщений: 20
Re: объезд препятствий
« Ответ #1 : Ноября 22, 2016, 06:38:14 am »

если кто-то не сильно жадный, киньте в личку код миньонов для объезда препятствий
Я что-то упустил или где-то уже "разобрали" localrunner? Тогда было бы ещё интересно взглянуть на код выбора цели для атаки у миньонов (по поводу башен информация уже есть).
« Последнее редактирование: Ноября 22, 2016, 06:40:42 am от zuko3d »
Записан

OMykhalevych

  • Newbie
  • *
  • Сообщений: 2
Re: объезд препятствий
« Ответ #2 : Ноября 22, 2016, 10:12:53 am »

Для объезда припятствий использую уравнение для определения пересечения прямой и окружности. Если есть общие точки, тогда проверяю угол до препятствия: угол отрицательный - смещаюсь вправо; угол положительный - смещаюсь в лево.

Вот код для опредления пересечения прямой и окружности:
bool commonSectionCircle(double x1, double y1, double x2, double y2,
double xC, double yC, double R)
{
x1 -= xC;
y1 -= yC;
x2 -= xC;
y2 -= yC;

double dx = x2 - x1;
double dy = y2 - y1;

//составляем коэффициенты квадратного уравнения на пересечение прямой и окружности.
//если на отрезке [0..1] есть отрицательные значения, значит отрезок пересекает окружность
double a = dx*dx + dy*dy;
double b = 2.*(x1*dx + y1*dy);
double c = x1*x1 + y1*y1 - R*R;

//а теперь проверяем, есть ли на отрезке [0..1] решения
if (-b < 0)
return (c < 0);
if (-b < (2.*a))
return ((4.*a*c - b*b) < 0);

return (a + b + c < 0);
}
Записан

Deo

  • Jr. Member
  • **
  • Сообщений: 47
Re: объезд препятствий
« Ответ #3 : Ноября 22, 2016, 11:47:39 am »

спасибо!
Записан

mortido

  • Full Member
  • ***
  • Сообщений: 96
Re: объезд препятствий
« Ответ #4 : Ноября 22, 2016, 12:07:15 pm »

...было бы ещё интересно взглянуть на код выбора цели для атаки у миньонов...
Не уверен, но вроде всегда ближайшего + кейс с ближайшим деревом у диких лесорубов.
Записан

tyamgin

  • Sr. Member
  • ****
  • Сообщений: 196
Re: объезд препятствий
« Ответ #5 : Ноября 22, 2016, 03:16:24 pm »

...было бы ещё интересно взглянуть на код выбора цели для атаки у миньонов...
Не уверен, но вроде всегда ближайшего + кейс с ближайшим деревом у диких лесорубов.

А случайно не того к кому меньше поворачиваться?
Записан

morph

  • Newbie
  • *
  • Сообщений: 4
Re: объезд препятствий
« Ответ #6 : Ноября 22, 2016, 03:44:04 pm »

если кто-то не сильно жадный, киньте в личку код миньонов для объезда препятствий
Я что-то упустил или где-то уже "разобрали" localrunner? Тогда было бы ещё интересно взглянуть на код выбора цели для атаки у миньонов (по поводу башен информация уже есть).

А подскажите, пожалуйста, где посмотреть информацию по башне. Если вдруг про миньонов уже известно, тоже буду рад узнать.
Записан

Equinox

  • Newbie
  • *
  • Сообщений: 7
Re: объезд препятствий
« Ответ #7 : Ноября 23, 2016, 04:01:51 am »

А подскажите, пожалуйста, где посмотреть информацию по башне. Если вдруг про миньонов уже известно, тоже буду рад узнать.

В этой теме раскрыли выбор цели у башни:
http://russianaicup.ru/forum/index.php?topic=598.0
Записан

IuriiCh

  • Newbie
  • *
  • Сообщений: 8
Re: объезд препятствий
« Ответ #8 : Ноября 23, 2016, 06:21:39 am »

С такой формулой можно запереться между двумя минионами. У себя использую алгоритм pathfind https://en.wikipedia.org/wiki/A*_search_algorithm Жрет больше процессора но с оптимизациями пока не выкидывает из игры:)
Записан

271828182845904

  • Jr. Member
  • **
  • Сообщений: 27
Re: объезд препятствий
« Ответ #9 : Ноября 24, 2016, 12:09:39 am »

С такой формулой можно запереться между двумя минионами. У себя использую алгоритм pathfind https://en.wikipedia.org/wiki/A*_search_algorithm Жрет больше процессора но с оптимизациями пока не выкидывает из игры:)
Отличный вброс)) На очень мелкодискретном поле "оптимизации" - это 98% сложности алгоритма поиска пути, и только оставшиеся 2% на поиск по графу.
Записан

ALEXks

  • Jr. Member
  • **
  • Сообщений: 19
Re: объезд препятствий
« Ответ #10 : Ноября 24, 2016, 03:25:55 pm »

Для объезда припятствий использую уравнение для определения пересечения прямой и окружности. Если есть общие точки, тогда проверяю угол до препятствия: угол отрицательный - смещаюсь вправо; угол положительный - смещаюсь в лево.

Вот код для опредления пересечения прямой и окружности:
bool commonSectionCircle(double x1, double y1, double x2, double y2,
double xC, double yC, double R)
{
x1 -= xC;
y1 -= yC;
x2 -= xC;
y2 -= yC;

double dx = x2 - x1;
double dy = y2 - y1;

//составляем коэффициенты квадратного уравнения на пересечение прямой и окружности.
//если на отрезке [0..1] есть отрицательные значения, значит отрезок пересекает окружность
double a = dx*dx + dy*dy;
double b = 2.*(x1*dx + y1*dy);
double c = x1*x1 + y1*y1 - R*R;

//а теперь проверяем, есть ли на отрезке [0..1] решения
if (-b < 0)
return (c < 0);
if (-b < (2.*a))
return ((4.*a*c - b*b) < 0);

return (a + b + c < 0);
}

Ох какой топорный алгоритм =)
Записан

OMykhalevych

  • Newbie
  • *
  • Сообщений: 2
Re: объезд препятствий
« Ответ #11 : Ноября 24, 2016, 04:37:54 pm »

Предложите лучше, не откажусь. ))
Записан

kipar

  • Jr. Member
  • **
  • Сообщений: 12
Re: объезд препятствий
« Ответ #12 : Ноября 24, 2016, 05:27:02 pm »

Отрезок движения может пересекать окружность, важно только чтобы позиция в конце тика не была в окружности. Так что проверять - в окружности точка или нет, если в окружности - искать пересечение эллипса допустимых ходов с ней (ну или отбрасывать это перемещение).
Записан

DVS

  • Hero Member
  • *****
  • Сообщений: 689
Re: объезд препятствий
« Ответ #13 : Ноября 24, 2016, 10:00:31 pm »

Понял!
нужно уметь решать квадратные уравнения, объезд тогда закодируется в 20 строк.

а я вот забыл как это, и у меня алгоритм в 500 строк (только обезд) и 37 секунд проца на игру
Записан
Страницы: [1]