Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 32
Мои поздравления :) Кто знает, что было бы, если бы волн было шесть, как в первой части финала.
Спасибо, очень захватывающий рассказ.
Интересно было бы узнать впечатления и от других финалистов.
Интересно было бы узнать впечатления и от других финалистов.
Молодца, болел за тебя в финале, как ни за кого другого и не зря! Удачи в след боях ) Жене особый респект за терпение, ну или за понимание )
Спасибо! Все это читается как какая-то магия!
А можете поделиться ссылками на репозитории, было бы очень интересно посмотреть как такие вещи реализуются?
И еще раз мои поздравления!
Спасибо!
Учитывая количество запросов по поводу кода — попробую восстановить git репозиторий… Выглядит так, что пару первых коммитов сломано. В крайнем случае чуть позже выложу итоговый код, без истории коммитов. Думаю история слабо интересна
Учитывая количество запросов по поводу кода — попробую восстановить git репозиторий… Выглядит так, что пару первых коммитов сломано. В крайнем случае чуть позже выложу итоговый код, без истории коммитов. Думаю история слабо интересна
Частично восстановил гит репозиторий. Основная ветка сохранилась практически полностью.
Читал на одном дыхании. Очень мотивирующе, отличная работа!
Огромный труд.
Мне показалось, что дискретизировать и прикручивать поиск пути на графе здесь будет лишним, а больше подойдёт простое сложение векторов, исходя из круглой формы всех объектов:
В результате обход препятствий работал очень хорошо. Правда, потом я прикинул объём необходимого кода для полноценной стратегии и количество велосипедов и if-else, особенно с учётом, что всё надо писать своими руками (запрет на подключение компонентов), и не стал участвовать :)
Мне показалось, что дискретизировать и прикручивать поиск пути на графе здесь будет лишним, а больше подойдёт простое сложение векторов, исходя из круглой формы всех объектов:
посмотреть
В результате обход препятствий работал очень хорошо. Правда, потом я прикинул объём необходимого кода для полноценной стратегии и количество велосипедов и if-else, особенно с учётом, что всё надо писать своими руками (запрет на подключение компонентов), и не стал участвовать :)
Да, будет работать, и неплохо. Вроде у Антона (Antmsu) так и было сделано. Этот способ проигрывает в позиционировании (для одиночного мага), но гораздо более экономичен по процессору и памяти, что оставляет больше простора для просчёта стрельбы и уворотов. Оба варианта возможны, Правильно замечено, что тут больше был вопрос в количествах if-else :)
при таком подходе можно зайти «удачно» между 4 деревьев и «зависнуть» там.
Очень интересно!
Из возможных оптимизаций подумалось тут — а не эффективнее ли было бы строить диаграмму Вороного динамически в качестве сетки? Вроде строится она достаточно быстро., Точек там было бы сильно меньше. Правда возможно потребовалось бы добавлять контрольные точки для поиска пути (делать не сложно, но общее количество точек бы значительно выросло)
И второй вариант — работать с сеткой графически. Т.е. просто на сетку накладывать спрайты с соответствующими коэффициентами. Тоже должно было бы работать достаточно быстро.
Из возможных оптимизаций подумалось тут — а не эффективнее ли было бы строить диаграмму Вороного динамически в качестве сетки? Вроде строится она достаточно быстро., Точек там было бы сильно меньше. Правда возможно потребовалось бы добавлять контрольные точки для поиска пути (делать не сложно, но общее количество точек бы значительно выросло)
И второй вариант — работать с сеткой графически. Т.е. просто на сетку накладывать спрайты с соответствующими коэффициентами. Тоже должно было бы работать достаточно быстро.
Может было бы и эффективней, но в первую очередь хотелось достичь простоты логики, иначе потом с ней можно было бы провозиться сильно дольше. А писать надо было достаточно много и кроме поиска пути. Поэтому нечто более сложное, чем поиск в ширину, писать не хотелось. Слишком давно я никаких новых алгоритмов не рассматривал и тем более не изучал.
Так второй вариант не меняет ничего, кроме принципа заполнения сетки коэффициентами. Там просто выкидываются все расчёты дистанции для каждой точки и заливается сразу готовые. А (судя по тексту) это было одно из перегруженных мест.
Я не понимаю, что под этим имеется ввиду. Ускорять, конечно, можно было. И как сделать оптимальней тоже можно придумать. По крайней мере у меня мысли есть, и, возможно, они о том же, о чём вы имеете ввиду. Да и во время оптимизации этой сетки 1.5 месяца назад мысли на эту тему тоже были. Но ускорять ещё сильнее, на мой взгляд, особо не требовалось, поэтому оставил как есть.
Грубо говоря сетку на игровом поле считать картинкой и копировать на неё заранее просчитанные спрайты дистанций/коэффициентов. Тогда из всех операций будет только умножение на поправочный коэф для данного параметра и, может, масштабирование. И то и другое крайне дёшево.
Кстати, если я правильно понял, для каждого мага используется своя матрица. Тут можно было бы использовать одну на всё поле и на всех. Что для близко расположенных дополнительно сэкономило бы на дублировании расчётов.
Кстати, если я правильно понял, для каждого мага используется своя матрица. Тут можно было бы использовать одну на всё поле и на всех. Что для близко расположенных дополнительно сэкономило бы на дублировании расчётов.
Собственно управляем каждым магом в отдельном процессе. И матрица соответствено одна на процесс. А графику в её изначальном виде однозначно не знаю, как прикрутить. Если что — видеокарты там нет, библиотек нет, используем только стандартные вещи (наподобие stl в С++). Да и даже если бы было — рисовать так, чтобы было адекватное смешение, мне неясно, как.
Матрицу в таком случае можно просто готовить вначале такта, а потом расшаривать на всех.
Графика — это лишь общий принцип, для наглядности. Все алгоритмы существуют ещё из тех времён, когда видеокарта умела рисовать лишь текст. Скопировать маленький 2д-массив внутрь большого 2д-массива — сложностей никаких совершенно. Смешение — в зависимости от требуемого результата. Как я понимаю коэф просто складываются в основном. Т.е. просто не заменяем значение а добавляем. Да и в любом другом случае смешение идёт как и в оригинальном алгоритме, просто все значения уже готовы и не требуется тратить время на их подсчёт.
Графика — это лишь общий принцип, для наглядности. Все алгоритмы существуют ещё из тех времён, когда видеокарта умела рисовать лишь текст. Скопировать маленький 2д-массив внутрь большого 2д-массива — сложностей никаких совершенно. Смешение — в зависимости от требуемого результата. Как я понимаю коэф просто складываются в основном. Т.е. просто не заменяем значение а добавляем. Да и в любом другом случае смешение идёт как и в оригинальном алгоритме, просто все значения уже готовы и не требуется тратить время на их подсчёт.
Расшарить её невозможно. Данных много, а взаимодействие между процессами считай никакое. Пару байт в тик только для верховного мага вообще ни о чём. И он имеет свойство умирать, когда он ничего не считает и не передаёт.
А то, что там складывать надо, каждый раз заново не считалось (после первой же оптимизации). Каждый раз считалось только расстояние от точки до врага (один раз от каждого до каждой), который добавляет штрафы/бонусы. И это можно было ещё попытаться оптимизировать — прогонять значения «волной», наподобие рисования круга (других форм я не рисовал). И это похоже на то, что вы предлагаете. Но повторюсь ещё раз — не было необходимости всё усложнять, и так работало достаточно хорошо. Да и не совсем понятно, насколько это помогло бы, учитывая, что от каждого вражеского объекта генерировалось обычно больше 4 полей разных радиусов. А провозиться с этим вечер или два мне бы пришлось.
А то, что там складывать надо, каждый раз заново не считалось (после первой же оптимизации). Каждый раз считалось только расстояние от точки до врага (один раз от каждого до каждой), который добавляет штрафы/бонусы. И это можно было ещё попытаться оптимизировать — прогонять значения «волной», наподобие рисования круга (других форм я не рисовал). И это похоже на то, что вы предлагаете. Но повторюсь ещё раз — не было необходимости всё усложнять, и так работало достаточно хорошо. Да и не совсем понятно, насколько это помогло бы, учитывая, что от каждого вражеского объекта генерировалось обычно больше 4 полей разных радиусов. А провозиться с этим вечер или два мне бы пришлось.
Нуу, возможно это действительно в вашем случае не имело особого смысла. Не уверен, т.к. плохо представляю вашу реализацию.
Почему нельзя расшарить непонятно. Обычно память можно делать общей как для тредов (собственно она там и так общая) так и для процессов без лишних заморочек.
Расстояние можно было загнать в текстуру готовое, а не пересчитывать каждый раз.
Если радиусы полей постоянные — то их так же можно было просто запечь в одну текстуру и рисовать одним проходом.
Почему нельзя расшарить непонятно. Обычно память можно делать общей как для тредов (собственно она там и так общая) так и для процессов без лишних заморочек.
Расстояние можно было загнать в текстуру готовое, а не пересчитывать каждый раз.
Если радиусы полей постоянные — то их так же можно было просто запечь в одну текстуру и рисовать одним проходом.
И радиусы непостоянные (например, когда у врага КД или он смотрит в другую сторону, можно подойти к нему чуть ближе), и центр врага явно находится не ровно в одной из точек матрицы, отчего будет погрешность +- точка. Да и радиус некоторых полей аж 600, если строить все нужные дистанции, то памяти потребовалось бы на такие текстуры больше, чем есть. Хотя для подсчёта пути в целом была бы годная оптимизация, но погрешность надо было бы учитывать. Те же самые башни — подошёл на 0.001 ближе, чем стоило — получи разряд.
На самом деле все не нужно, достаточно одну большую масштабировать. Текстура дистанций вообще нужна всего одна на максимальный размер. Да, и от всех текстур реально нужна только четверть естественно.
Погрешность да, учитывать пришлось бы, но разве там требуется такая субпиксельная точность? Вроде достаточно просто не подходить слишком близко, т.е. достаточно один раз заложить погрешность в +1 шаг сетки и всё. Разве что стоит задача просачиваться мимо них. Но, вроде, башни стоят не вплотную и места для манёвра там хватает.
Просто я давным давно (ещё на первых пнях) с похожей задачей сталкивался и там это давало огромную разницу в скорости. Дистанции считать было очень дорого.
Погрешность да, учитывать пришлось бы, но разве там требуется такая субпиксельная точность? Вроде достаточно просто не подходить слишком близко, т.е. достаточно один раз заложить погрешность в +1 шаг сетки и всё. Разве что стоит задача просачиваться мимо них. Но, вроде, башни стоят не вплотную и места для манёвра там хватает.
Просто я давным давно (ещё на первых пнях) с похожей задачей сталкивался и там это давало огромную разницу в скорости. Дистанции считать было очень дорого.
Думаю можно так попытаться сделать, но опять же — для меня это ненужное усложнение. Я такими вещами никогда ещё не занимался и не особо имею представление, как и что можно с этим сделать, чтобы работало достаточно быстро. Но если иметь опыт — всё возможно. Песочница ещё открыта, как и код, можно пробовать :-)
А про расшарить — у меня Java отказалась даже на NotImplementedException из пакета sun.reflect.generics.reflectiveobjects.notimplementedexception посмотреть, java.security.AccessControlException выдало. Мол, не секьюрно и вообще. Так что маловероятно. Запуск процессов никак нами не контролируется, да и вообще гарантии нет, что все процессы запускаются на одной машине.
А среди стратегий была версия с расчетом потенциалов?
Так для снарядов создаём полосу положительного потенциала, и маг автоматически попытается уйти от выстрела. Для миньонов и вражеских магов потенциал считать по нескольким слагаемым: спереди положительный, сзади — отрицательные и потенциал для КД.
Тогда в простейшем случае достаточно двигаться в сторону уменьшения потенциала и сэкономить на расчёте матрицы очков. Осталось решить проблему потенциальной ямы.
Так для снарядов создаём полосу положительного потенциала, и маг автоматически попытается уйти от выстрела. Для миньонов и вражеских магов потенциал считать по нескольким слагаемым: спереди положительный, сзади — отрицательные и потенциал для КД.
Тогда в простейшем случае достаточно двигаться в сторону уменьшения потенциала и сэкономить на расчёте матрицы очков. Осталось решить проблему потенциальной ямы.
100% такие варианты были, и много. Но увороты рассчитывать потенциалами плохой подход, на мой взгляд. А вообще топ 1 решение было вроде на потенциалах. Хотя я не вижу серьёзной разницы между топ 1 и топ 3, по сути первые 3 места распределил рандом.
На потенциальных полях было много стратегий. Как минимум, навскидку, знаю около 10 таких в топ-60. Стратегия победителя (Antmsu) тоже была на ПП. Но увороты через них работали плохо, знаю по себе. Потенциальная яма не была особой проблемой в бою, потому что бои были довольно динамичные, все постоянно менялось.
Серьезная работа, очень познавательно, спасибо!
Присоединяюсь к поздравлениям. Времени убито гораздо больше, чем у меня =) Но, возможно, оно того стоит.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
История участия (и почти победы) в ежегодном соревновании Russian AI Cup 2016