План работ
- Распознать иконки героев на изображении плохого качества с искажениями;
- Провести анализ выбранных героев и подобрать для каждой команды хорошую комбинацию;
- Показать результат.
Для начала было решено разработать x86 приложение (C++ / OpenCV), позже портировать под Android с реальной камерой. Нужен был быстрый и точный алгоритм сравнения изображений. После продолжительного поиска выяснились наиболее популярные подходы:
- Simple euclidean distance
- Cross Correlation
- Histogram comparison
- Detectors of salient points/areas
Остальные варианты отброшены как слишком сложные или не реализованные в OpenCV.
В ходе экспериментов стало понятно, что необходимо сначала распознать контуры героев, а уже потом сравнивать их содержимое с оригинальными иконками. Искать на большом скриншоте маленькую иконку с помощью template matching очень медленно. Принцип работы такой:
- Подготовить двоичную маску иконок
- Найти контуры
- Отфильтровать ложные срабатывания
- Запустить потоки распознавания
Оригинальное изображение:
Маска:
Контуры героев:
Пришлось очень много возиться с распознаванием контуров, подстраивать оптимальные параметры для маски и фильтра ложных срабатываний. Изображение может быть плохого качества или с искажениями, на разных мониторах разные пропорции.
Для распознавания иконок был написан крутой велосипед, который комбинировал cv::matchTemplate для ранней фильтрации и cv::FlannBasedMatcher для точного сравнения. На базе этих коэффициентов вычислялся вес похожести и возвращался герой с наивысшим весом.
Долго боролся с проблемой сравнения похожих иконок, но в итоге забил, т.к. редкое явление. Например, входное изображение A распознается как герой C:
Итого, по результатам распознавания погрешность около 10%, один кадр на Core i5 вычисляется до 200ms, на Nexus7 до 2sec. Наверняка можно много чего оптимизировать, но для прототипа было достаточно.
Основной функционал приложения был готов, оставалось портировать его на Android, добавить поддержку камеры и отобразить результат. Тут я очень сильно ошибался, около 70% времени работы над приложением ушло на борьбу с багами Android на разных устройствах.
Особенно порадовал camera API. Управление фокусом, разрешение видео искателя и фотографии – все это может вызвать проблемы вплоть до полного зависания. Советую тестировать на малобюджетных китайских телефонах, чтобы поймать максимум багов.
Стоит упомянуть, что JNI это боль. Поэтому я решил просто передавать данные в ByteBuffer. Да, есть всякие генераторы вроде SWIG, но они ужасно громоздкие и код выхлопа страшный.
Небольшой совет по оптимизации размера apk. Весь native код я собрал в одну shared library и удалил лишнее, в результате общий размер сократился в 3 раза:
CFLAGS := -DANDROID_NDK -DNDEBUG -O3 -Ofast -flto -fvisibility=hidden -ffunction-sections -fdata-sections
LDFLAGS := -Wl,--gc-sections -Wl,--exclude-libs=ALL
Комментарии (24)
Smi1e
15.06.2015 22:22Что обозначают подобранные герои, которые отображает приложение? Это связанные пятерки или одиночные герои? По каким параметрам они подбираются и какие показатели при этом учитываются?
realimba Автор
15.06.2015 23:45+1Приложение показывает наиболее удачных героев по мнению dotabuff. Там у каждого героя есть поле best versus и worst versus которые dotabuff вычисляет по своим алгоритмам на базе собранной статистики. Генератор крутых пиков планировался на потом.
nikolayvaganov
16.06.2015 10:32+2Не хочу уходить в терминологию и тонкости, которые могут быть не понятны людям, далеким от dota, но удачность контрпика на основе best/worst одиночных героев даст больше вреда чем пользы, потому как в данный конкретный момент основной профит все же идет от связок героев ( два и более ), когда, например, очень слабые сами по себе слабые саппорты дают много больше пользы в связке, чем более менее сильные в одиночку.
nikolayvaganov
16.06.2015 08:44+2Очень давно уже есть мысль хотя бы снять более менее достоверную статистику по контрпикам героев, связкам и прочим, но слишком много неизвестных в итоге и вся статистика нивелируется. Вот несколько пунктов, которые нужно учитывать:
1. Личный скилл
В команде нужно два саппорта, но статистика игроков в команде по саппортам ниже плинтуса
2. Лайнинг
Та самая ситуация, когда трое хотят мид :) либо невозможность объяснить нестандартную расстановку героев
3. Адекватность и возраст
Беспощадный русский паб, когда все хотят идти убивать ( я не саппорт, а керри )
4. Новые патчи
С каждым мажорным патчем баланс по героям и пикам меняется и после выхода нового с очень большой вероятностью до набора большого количества сыгранный матчей от подобной статистики будет больше вреда, чем пользы.
5. Уровень алкоголя в крови игроков твоей любимой команды
Тут все понятно. =)
SKY_nv
А как приложение учитывает кривизну рук игроков при подборе «победной комбинации»?
realimba Автор
В планах было получать статистику по игроку через dotabuff и давать приоритет лучшим героям. Но не судьба.
SKY_nv
Даже для такого подхода вам нужно для начала получить статистику по героям у соперников. Потому что даже если герой как-бы контрится, но при винрейте 60-70+ есть вероятность что просто взять контрпик будет недостаточно. НУ это само собой не работает со скрытыми профилями. А значит в текущей реализации приложение чуть меньше чем бесполезное.
Помимо контрпиков нужно еще и синергию героев учитывать и навыки игроков, учитывать лайнинг и т.д. Слишком много неизвестных.
AtomKrieg
Вы люто бешено категоричны. Вся дота построена на контр пиках. Синергию конечно стоит учитывать, но это лучше отдать на откуп игрокам.
Aios
Ну я посмотрю как Вам поможет контрпик, когда с Вами вместе попадется 4
ракообразныхне очень хорошо играющих существа.AtomKrieg
Вообще-то в игре есть рейтинг. Поэтому такие ситуации редки.
Aios
Знаете мне и на 6000+ попадаются интересные особы. Никто не застрахован.
AtomKrieg
купленные акки
Aios
Ну тогда вернемся к тому что Синергию 100-пудово нужно учитывать. А точнее ее учет должен быть на первом месте.
BupycNet
Можно вообще создать сервис сразу для компа. Нажал комбинацию — распознал героей, показал на экране что пикать.
При этом будут учитываться профили по дотабафу. Более того — если профиль закрыт, то тут в игру вступает популярность. Т.е. для использования сервиса надо дать доступ к своим данным. И в итоге, чем больше человек использует — тем проще контрпикать.
Но тут есть одна беда — у обычных игроков будет меньше шансов.
Хотя возможно наоборот, игра будет как раз веселее, ведь пик будет балансным, и все будет уже зависеть от игроков.
Temirkhan
Может тогда уж сразу на ИИ сфокусироваться, который будет выбирать и играть заместо игроков? К чему вся эта возня? Ладно, быстрая напоминалка соотношений контрпиков, но вести подсчет всех карт в игре — это уже перебор.
josser
Вы наверно про-дотер, на рейтинге 2000-2500 победа это хотя бы не пикнуть бесполезного героя.
SKY_nv
Не бесполезный герой еще может быть сложен в реализации. 4500-4700.
VioletGiraffe
Бред, 2500 отнюдь не плохой уровень.
P. S. В системе MMR что-то очень сильно поломано. ИМХО рандом лучше.
Temirkhan
Вы правы лишь отчасти. Однако, система ММР — это не то, что воспринимается, как уровень игры. Это психологический портрет. Люди, у которых ММР ниже 2000, часто могут превосходить игроков с 3000-3500 ммр по всем игровым пунктам (фарм, добивания, закупка предметов, подбор героев, манипуляция игровой механикой и т.д). Однако, последние имеют более устойчивую психику(решения более обдуманы, решения анализируются не только за своего героя, но всю команду. Настрой на победу и позитивное отношение к команде тянутся дольше, чем у первых. И, как результат, они всегда или почти всегда побеждают у первых. Точно так же отличаются игроки 3-3.5к от более высоких рангов. Это не шкала от 0 до 10. Это аттрибуты, которые есть у игроков более высокого ранга, и, которых нет у более низких.
Wigaro
Мои друзья делают сбор статистики пик к пику, чтобы находить контр-пики, сайт dota2picker.com. Если есть что с ними обсудить, могу дать контакты