В догонку (не ради стратегии, а просто как возможный алгоритм):
Этот же параметр можно использовать в качестве маркера размерности паттернов карты.
Проще говоря:
карту «воды» вокруг своего муравейника (размером половины расстояния между муравейниками) накладывать на каждый найденный вражеский муравейник. Но тут еще надо будет учесть зеркальное наложение (и по каким осям зеркальное) или прямое.
На самом деле это не так сложно реализовать. Даже без сложного поиска паттернов карты.
Как только находим любой вражеский муравейник, то запускаем цикл с учетом зеркальной замкнутости карты, в котором собираем набор из координат с одинаковым смещением по осям между своим и вражеским муравейником.
Проще говоря:
свой муравейник 0,0
вражеский 7,10
значит еще один вражеский будет в 14,20 и так далее по циклу зеркальных координат, пока снова не встретится клетка своего же муравейника.
Это конечно не всегда с первого раза найдет абсолютно все муравейники, но найдет те, которые лежат на одной оси симметрии. А если это был вообще ближайший муравейник, тогда скорее всего сразу все, потому что ось симметрии скорее всего опишет по спирали всю карту и вернется к своему же муравейнику.
Тут вы правы. Именно при поиске других муравейников имеет смысл использовать.
Насчет простого открытия карты не столь важно, потому что важно не открыть всё, и иметь открытым как можно больше, чтобы быстрее собирать появляющуюся еду.
Кстати из этого тогда вытекает идея использования симметрии карт, потому что симметричны не только вода, но расположение самих муравейников. Таким образом можно даже находить паттерны на карте и на их основе рассчитывать симметрию, и как следствие расположение вражеских муравейников и не открытую карту.
1. Радиус атаки 5 это не радиус в 5 клеток (посмотрите описание расчета радиуса), это радиус примерно 2 клетки, к тому же еда появляется на карте случайным образом. Так что возможна ситуация, когда еда появится в клетке, которая будет равноудалена для двух муравьев, которые сходили навстречу друг другу.
2. На муравейник надо именно «наступить».
3. Тут само собой на ваше усмотрение, это лишь классический подход. Он выбран таким в связи с тем, что для расчета пути выгоднее предполагать, что неизвестная область проходима, нежели обратное. Иначе бот будет пытаться прокладывать маршрут только по открытым областям, и, как следствие, алгоритм поиска пути не всегда будет находить путь, если например вы «открыли» часть суши на другом берегу от воды. В результате любая попытка расчета пути до такой точки будет заставлять бота запускать анализ пути, в который попадут все ячейки открытой карты, но путь так и не будет найден.
4. Все радиусы задаются при старте игры. Соответственно логично предположить, что универсальный алгоритм должен основываться на настройках, переданных при старте. На случай если они изменятся.
Однако можно и использовать конечно подход фиксированного радиуса. Тогда получается несколько проще (я просто тоже продумывал этот алгоритм).
В частности тогда можно создавать набор шаблонов расположения муравьев (где стоят свои, где враги и сколько их), их делить на шаблоны наличия заблокированных клеток, а дальше уже применять соответствующий алгоритм хода для всех муравьев, удовлетворяющих шаблону. Соответственно шаблоны должны вращаться. Для них даже можно вводить хеши для более быстрого поиска.
Но это лишь для самых стандартных ситуаций, для динамического радиуса это не подойдет. Гораздо более эффективным будет как раз описанный в статье механизм расчета «карты сил».
Можно. В статье я описал, что нужно учитывать, чтобы можно было контролировать каждого своего муравья из хода в ход. Посмотрите раздел «Область видимости и отслеживание ситуации». Можете также код бота посмотреть, там есть этот механизм.
Настройки игры передаются при инициализации бота в начале игры.
А с каждым ходом в бот передается следующая информация:
о новой увиденной воде (а не вообще видимой воде),
о всех видимых муравьях (с указанием номера бота-владельца),
о всех видимых муравейниках (с указанием номера бота-владельца),
о мертвых муравьях по результатам прошлого хода (с указанием номера бота-владельца),
о всей видимой еде,
текущий номер хода.
Соответственно эту информацию нужно обрабатывать (корректировать) каждый ход.
Я реализовывал это немного по-другому. Сразу уточню, что в этом алгоритме не отработан момент сложного поведения в случае нападения толпой. Это упрощенный вариант:
1. На вход метода $ant->move() поэлементно подается массив направлений, расставленный в порядке приоритета. Например (n,e,w,s), то есть сперва попробовать на север, потом восток и т.д.
Цикл заканчивается когда хотя бы одно их направлений будет подтверждено.
2. Если в «ходить в эту клетку» уже был приказ, или там еда или вода, то отказать.
3. Если на этой клетке муравей и он не двигался (!$ant->isMoved()), тогда приказать ему
двигаться и снова попробовать сходить в этом направлении.
4. Если клетка является тупиком — то отказать в направлении.
5. Если сила вражеских муравьев в клетке равносильна смерти муравья, то отказать в направлении.
Там же «зашит» алгоритм, помнящий к какой цели шел муравей и как долго он уже к ней идет. Чтобы муравьи не «зависали» над одной и той же целью слишком долго.
А дальше уже сохраняем куда именно пошел муравей, обновляем «карту сил», какое направление было выбрано (для расчета последних приоритетных направлений) и собственно отдаем сам приказ о движении.
Такой механизм в принципе не требует кеширования команд. Но вот для сложных баталий конечно кешировать уже будет удобнее.
Спасибо за сведения.
Статья писалась примерно неделю назад (пока шла через песочницу, потом через топики и тд.), так что актуальность потерялась. Тот бот скатился на 160 место уже.
С тех пор не заходил на сайт соревнований.
То что не реализуют защиту муравейника — это большой стратегический минус, на этом многие пролетают.
А алгоритмы поиска пути и сбора еды — один из самый простых аспектов, вот только нагрузка у поиска пути довольно большая. Пробовал на PHP прикрутить A*. Работает отлично, но на 200+ муравьев и сложных траекториях часто давал timeout, не успевал за ход. Можно было конечно и по-оптимизировать, но уже было не до этого.
Своим муравьем можно убить, только если двух в одну клетку послать, а это бот контролирует (об этом в «Область видимости и отслеживание ситуации» было написано). Хранит клетки, куда уже были отданы приказы.
Касательно самого бота это только forFun, чтобы можно было «человеко-читаемо» писать логику поведения. Меня не столько интересовала фактическая победа и реализация, сколько стратегическая логика игры. Просматривал логи, поведение, механику, алгоритмы и т.п.
Обо всем этом и написал.
Проще всего это понять просмотрев «в живую».
Откройте любую игру, хотя бы и эту к примеру. Увеличьте зумом на любом муравье и наведите мышкой на самого муравья или клетку рядом с ним.
Если увидите что появился круг вокруг муравья, значит эта клетка в пределах его радиуса атаки.
А зону видимости можно посмотреть включив туман войны, это меню в левой колонке плеера (для каждого игрока свой «туман войны»).
Этот же параметр можно использовать в качестве маркера размерности паттернов карты.
Проще говоря:
карту «воды» вокруг своего муравейника (размером половины расстояния между муравейниками) накладывать на каждый найденный вражеский муравейник. Но тут еще надо будет учесть зеркальное наложение (и по каким осям зеркальное) или прямое.
Как только находим любой вражеский муравейник, то запускаем цикл с учетом зеркальной замкнутости карты, в котором собираем набор из координат с одинаковым смещением по осям между своим и вражеским муравейником.
Проще говоря:
свой муравейник 0,0
вражеский 7,10
значит еще один вражеский будет в 14,20 и так далее по циклу зеркальных координат, пока снова не встретится клетка своего же муравейника.
Это конечно не всегда с первого раза найдет абсолютно все муравейники, но найдет те, которые лежат на одной оси симметрии. А если это был вообще ближайший муравейник, тогда скорее всего сразу все, потому что ось симметрии скорее всего опишет по спирали всю карту и вернется к своему же муравейнику.
Насчет простого открытия карты не столь важно, потому что важно не открыть всё, и иметь открытым как можно больше, чтобы быстрее собирать появляющуюся еду.
Кстати из этого тогда вытекает идея использования симметрии карт, потому что симметричны не только вода, но расположение самих муравейников. Таким образом можно даже находить паттерны на карте и на их основе рассчитывать симметрию, и как следствие расположение вражеских муравейников и не открытую карту.
Просто не могу найти пример, когда это принципиально важно для какого-либо алгоритма.
1. Радиус атаки 5 это не радиус в 5 клеток (посмотрите описание расчета радиуса), это радиус примерно 2 клетки, к тому же еда появляется на карте случайным образом. Так что возможна ситуация, когда еда появится в клетке, которая будет равноудалена для двух муравьев, которые сходили навстречу друг другу.
2. На муравейник надо именно «наступить».
3. Тут само собой на ваше усмотрение, это лишь классический подход. Он выбран таким в связи с тем, что для расчета пути выгоднее предполагать, что неизвестная область проходима, нежели обратное. Иначе бот будет пытаться прокладывать маршрут только по открытым областям, и, как следствие, алгоритм поиска пути не всегда будет находить путь, если например вы «открыли» часть суши на другом берегу от воды. В результате любая попытка расчета пути до такой точки будет заставлять бота запускать анализ пути, в который попадут все ячейки открытой карты, но путь так и не будет найден.
4. Все радиусы задаются при старте игры. Соответственно логично предположить, что универсальный алгоритм должен основываться на настройках, переданных при старте. На случай если они изменятся.
Однако можно и использовать конечно подход фиксированного радиуса. Тогда получается несколько проще (я просто тоже продумывал этот алгоритм).
В частности тогда можно создавать набор шаблонов расположения муравьев (где стоят свои, где враги и сколько их), их делить на шаблоны наличия заблокированных клеток, а дальше уже применять соответствующий алгоритм хода для всех муравьев, удовлетворяющих шаблону. Соответственно шаблоны должны вращаться. Для них даже можно вводить хеши для более быстрого поиска.
Но это лишь для самых стандартных ситуаций, для динамического радиуса это не подойдет. Гораздо более эффективным будет как раз описанный в статье механизм расчета «карты сил».
А с каждым ходом в бот передается следующая информация:
о новой увиденной воде (а не вообще видимой воде),
о всех видимых муравьях (с указанием номера бота-владельца),
о всех видимых муравейниках (с указанием номера бота-владельца),
о мертвых муравьях по результатам прошлого хода (с указанием номера бота-владельца),
о всей видимой еде,
текущий номер хода.
Соответственно эту информацию нужно обрабатывать (корректировать) каждый ход.
1. На вход метода $ant->move() поэлементно подается массив направлений, расставленный в порядке приоритета. Например (n,e,w,s), то есть сперва попробовать на север, потом восток и т.д.
Цикл заканчивается когда хотя бы одно их направлений будет подтверждено.
2. Если в «ходить в эту клетку» уже был приказ, или там еда или вода, то отказать.
3. Если на этой клетке муравей и он не двигался (!$ant->isMoved()), тогда приказать ему
двигаться и снова попробовать сходить в этом направлении.
4. Если клетка является тупиком — то отказать в направлении.
5. Если сила вражеских муравьев в клетке равносильна смерти муравья, то отказать в направлении.
Там же «зашит» алгоритм, помнящий к какой цели шел муравей и как долго он уже к ней идет. Чтобы муравьи не «зависали» над одной и той же целью слишком долго.
А дальше уже сохраняем куда именно пошел муравей, обновляем «карту сил», какое направление было выбрано (для расчета последних приоритетных направлений) и собственно отдаем сам приказ о движении.
Такой механизм в принципе не требует кеширования команд. Но вот для сложных баталий конечно кешировать уже будет удобнее.
Статья писалась примерно неделю назад (пока шла через песочницу, потом через топики и тд.), так что актуальность потерялась. Тот бот скатился на 160 место уже.
С тех пор не заходил на сайт соревнований.
То что не реализуют защиту муравейника — это большой стратегический минус, на этом многие пролетают.
А алгоритмы поиска пути и сбора еды — один из самый простых аспектов, вот только нагрузка у поиска пути довольно большая. Пробовал на PHP прикрутить A*. Работает отлично, но на 200+ муравьев и сложных траекториях часто давал timeout, не успевал за ход. Можно было конечно и по-оптимизировать, но уже было не до этого.
Своим муравьем можно убить, только если двух в одну клетку послать, а это бот контролирует (об этом в «Область видимости и отслеживание ситуации» было написано). Хранит клетки, куда уже были отданы приказы.
Касательно самого бота это только forFun, чтобы можно было «человеко-читаемо» писать логику поведения. Меня не столько интересовала фактическая победа и реализация, сколько стратегическая логика игры. Просматривал логи, поведение, механику, алгоритмы и т.п.
Обо всем этом и написал.
Откройте любую игру, хотя бы и эту к примеру. Увеличьте зумом на любом муравье и наведите мышкой на самого муравья или клетку рядом с ним.
Если увидите что появился круг вокруг муравья, значит эта клетка в пределах его радиуса атаки.
А зону видимости можно посмотреть включив туман войны, это меню в левой колонке плеера (для каждого игрока свой «туман войны»).