Як шукати шлях до перемоги на Russian AI Cup 2016, але не в тому напрямку

є тільки два шляхи, до перемоги або до лісу
Після не дуже довгих умовлянь, мене переконали, що 30 місце не так вже й погано, і написати статтю варто. Я – учасник з ніком Stef, і зайняв в пісочниці близько 30 місця.
Картинка намальована поруч, має глибокий сенс – замість того, щоб приділити достатньо часу і бути призером змагання, я пішов іншим шляхом — витратив одну третину часу на те, що робити було не обов'язково. Якщо бути точніше, то я зайнявся алгоритму пошуку шляху в просторі, де немає нездоланних стін, а є лише дерева, які можна або рубати або проходити поруч з ними.
Що з цього вийшло, можна подивитися в відео, а охочих пізнати всі таємниці лісу прошу під кат.


Спочатку трохи розповім про змаганні. В цьому році правила змагань базувалися на популярному в світі комп'ютерному жанрі MOBA. Основні концепції даного жанру були збережені — поява крип на 3 лініях близько баз; річка з рунами; 5 героїв з кожної сторони. Але не дивлячись на це, повноцінної MOBA це не було – мало ефективно переходить з лінії на лінію, захищати базу за фактом теж, і розвиток було лише у вигляді прокачування скілів з заданого обмеженого набору. Фінал серед топів звівся до того, що гра проходила за принципом: «хто швидше знесе базу супротивника по центральній лінії, той і виграв», а вона зносилася махом, від 4 до 6 хвиль крип.
Як людина знайомий з цим жанром не з чуток, в самому ж початку змагань я запідозрив недобре і висловив припущення, що у фіналі буде саме така тактика – все по мзс. На жаль, баланс в кращу сторону не змінився, а я вирішив грати у свою гру, а не в ту, що призведе до перемоги.

Архітектура
В цьому році я писав стратегію на C++, який, як я думав, мені близький. Про таке рішення пошкодував — можливостей з високорівневих мов мені не вистачило, уже звик до них. До фіналу моя програма включала 141 файл .h або .cpp. Виглядало це якось так: лісу архітектури
З цієї картинки можна побачити основну ідею архітектури:
  • Шар загального призначення – У нього входять такі папки: Algorithms, Common, Environment. Розташування класів між цими папками не зовсім коректно, особливо між папкою Algorithms і Environment.
  • Шар команд – набір класів, що реалізує один з трьох протоколів: MoveCommand, AttackCommand, CastCommand. Відповідали за логіку: куди йти, кого атакувати, що кастовать.
  • Шар тактики – В нього входять папки Strategy, Tactics, Role:
    • Strategy – суматор результатів команд і містить у собі базовий набір для спрощення роботи з командами.
    • Role – базові класи визначають поведінку мага — просто набір цифр.

    • Tactics – Описує стратегію, і ролі для цієї стратегії. Під кожен раунд вони різні. А на фінал їх кілька.
Архітектура вийшла досить великий і надмірною, особливо шар команд. Що призвело до деяких перевитрат по часу.


Перед початком змагань я встановив собі програму для підрахунку часу (toggl), і їй постійно користувався. Відразу відповім на одне питання, що цікавить багатьох – чи багато часу і сил витрачається на олімпіаду? – Так багато. Її дуже складно поєднувати з роботою і родиною, і за фактом доводиться жертвувати сном заради неї. Студентам в цьому плані простіше, але думаю теж нелегко.
Витрачений час по тижнях:
  • Перша – 26 годин
  • Друга – 26 годин
  • Третя – 27 годин
  • Четверта – 34.5 годин
  • П'ята – 38.5 годин
  • Шоста (перед фіналом) – 10 годин
  • Після фіналу – 15 годин
Загальна: 177 годин.

У другому раунді я зайняв 103 місце, незважаючи на те, що в пісочниці був високо в рейтингу, і хотів потрапити у Фінал через пісочницю, але так і не зміг. Перед фіналом я був на 80-90 місці c розумінням, що вже втомився і не можу продовжувати далі писати по ночах, з цієї причини закинув написання олімпіади на тиждень, ну і як наслідок, не пройшов у фінал.

Після деякого відпочинку та закінчення фіналу, я витратив ще близько 17 годин на виправлення багів і невеликі поліпшення стратегії, що допомогло мені піднятися з 80-90 місць до 20-30. В цей момент я остаточно усвідомив, що написання олімпіади ночами було поганою ідеєю — майже всі поліпшення коду складалися з виправлень помилок, які в свою чергу з'являлися з-за неуважності, яка сильно страждає вночі.

Витрачено часу за завданнями:
  • Підтримка Архітектури — 28 годин
  • Написання Алгоритму Пошуку шляху — 49 годин
  • Написання Алгоритму Уворота — 26 годин
  • Інше — 67 годин


У списку виділено 3 основні завдання, які відняли найбільше часу: Архітектура, Пошук шляху, Оберти. В «інше» потрапили такі речі як: балансування і підгонка констант, виправлення багів та алгоритми які не забрали багато часу.

Тепер можна переходити до самої цікавої частини – алгоритмами, яких я написав досить багато, і не у всіх розкрив їх потенціал.

Алгоритми
За час олімпіади були реалізовані наступні алгоритми:
  • Карта впливів — дозволяє легко оцінити перевагу сил по лініях і знайти точку де зараз стоїть знаходиться на лінії
  • Передбачення знаходження ворога в невидимій зоні — потрібно в першу чергу для більш точного прорахунку карти впливів
  • Оцінка результату локальної битви – потрібен для розуміння коли нападати, а коли захищатися
  • Ухилення від снарядів — один з найважливіших алгоритмів
  • Пошук оптимальної позиції — другий за важливістю алгоритм. Оцінює куди краще йти і повертатися в поточний твк. Найслабша ланка моєї стратегії
  • Пошук шляху — дозволяє оцінити відстань до точки і знайти які дерева заважають, щоб її досягти
  • Обхід перешкод – потрібен щоб обходити близькі перешкоди по найкоротшому шляху


Карта впливів
Була зроблена після першого раунду. Спочатку створювалася в першу чергу для прийняття тактичних рішень у фіналі.
За фактом основне її призначення — це визначення лінії фронту, точки, де зараз відбувається бій.
Крім цього карта впливів важлива при оцінці результату локальної битви, та оцінки на якій лінії краще стояти.
Виглядає вона якось так:

Якщо подивитися уважно, то можна побачити, що основний вплив чинять крип. Маги виявляються маленьке вплив в силу їх непостійності, а вежі слабкі, і не здатні дати відсіч у разі нападу. В принципі слабкість веж і є однією з найбільших причин іншого балансу в грі, ніж у MOBA.
Будувалася вона досить легко:
Проходимо по всім юнітам, будівлям, магам на карті, і заповнюємо сітки навколо. Всього є дві сітки: дружня і ворожа, обидві сітки розміром 80x80 і на всю карту.

Для того, щоб знайти де зараз лінія фронту, алгоритм йде від своєї бази до ворожої і перевіряє вплив ворогів навколо поточної точки перевірки. Якщо ворожий вплив навколо цієї точки є, то значить лінія фронту в цій точці.

Насправді спочатку алгоритм діяв за іншим принципом, і видавав точки де вперше зустрічається «жовта» зона з боку противника. Але учасник під ніком core2duo змінив мою думку про те, де повинна знаходиться лінія фронту – його стратегія в фіналі нападала на верхню вежу, обходячи по лісі і не заходячи на лінію, тим самим крип проходили повз його магів не звертаючи на них уваги.

Оцінка, на якій стороні перевага сил по лініях, виходить з допомогою суми всіх впливів на цій лінії. І з допомогою алгоритму нижче, це оцінка була достатньо точною, щоб можна було сказати, коли лінія починає програвати або навпаки вигравати. Щоправда, з-за моєї ліні, сума впливів вважається неправильно, і наскільки сильніше або слабкіше лінія сказати вже не так легко.

Передбачення знаходження ворога в невидимій зоні
Існує три передбачення: знаходження ворожих крип, знаходження магів, вишки. Перше передбачення достатньо точний, але і не використовується безпосередньо. Воно потрібно тільки для оцінки сили лінії, так як без цього алгоритм майже завжди вважав, що наші лінії виграють.
Для передбачення ворожих крип використовується досить простий алгоритм — раз на 750 тиків, час появи крип, з точки появи пускаються 4 кріпа завжди в одній і тій же силі, і з однією і тією ж швидкістю. Як тільки вони доходять до зони, де є видимість, то вони зникають.
З магами інша історія — вони мало впливають на карту впливів, але при цьому іноді було б непогано мати можливість наздогнати ворожого мага, який втік за край екрану. Тому всі ворожі маги після першого їх появи в зоні видимості зберігаються в локальному світі, і якщо вони зникли з зони видимості, йде емуляція їх відходу до бази. Тобто стратегія завжди вважає — якщо мага більше не видно, значить, він біжить до бази.

Також в силу того, що вишки стріляють на таку ж відстань, що і радіус огляду у мага, то позиції ворожих башт забиваються спочатку гри симетрично своїм, щоб завжди знати про їх існування. Також для них автоматично вважається час до атаки. Тут правда треба врахувати, що забирати треба dt а не 1, так як якщо маг помер або його заморозили, то стратегія не отримує контроль над цим магом.

Оцінка результату локальної битви
До появи цього алгоритму, моя стратегія завжди грала від захисту, єдиний випадок коли маг міг напасти — випадки зміщення лінії фронту сильно в бік ворожої бази. Або ворожий маг сам прийшов, щоб його вбили.
Поява цього алгоритму явно дало перевагу серед топ стратегій — топ стратегії майже не роблять помилки і рідко можна сказати, що якщо нападешь, то точно виграєш, а ось більш слабкі стратегії рано чи пізно зроблять помилку і в цей момент провісник результату битви скаже — все можна нападати.
Хоча основна перевага він дав у нападі, створювався він в першу чергу заради того, щоб не робити помилки при дисбалансі на лінії або, по-іншому, якщо ворожих магів більше ніж своїх. В цьому випадку краще стояти трохи подалі від ворогів, так як якщо допустити хоча б одну помилку, то великі шанси, що твого мага вб'ють.
Спосіб розрахунку результату локальної битви до неможливості простий, але, незважаючи на це досить ефективний.
Спочатку визначимося з вхідними параметрами — на вході ми маємо свого мага і точку, куди ми хочемо напасти. Існує також більш просунутий варіант — на вхід подається свій маг + ворожий, в такому випадку викликається два рази функція оцінки шансу на перемогу — один раз для свого і один раз для ворожого мага. Такий підхід допомагає більш точно оцінити шанси на перемогу, ніж через точку, так як в разі рівності сил він видасть число більш близьке до нуля, а в разі великої різниці навпаки підсилить цю різницю ще сильніше.

Основна ж функція розрахунку виглядає так:
  1. Якщо в поточний твк по мені можуть завдати шкоди більше ніж у мага хп, за умови, що всі одночасно у нього вистрілять, то повертаємо негативний шанс на перемогу
  2. Додаємо суму небезпеки дружніх магів які знаходяться приблизно на тому ж відстані до контрольної точки або ближче ніж мій маг.
  3. Віднімаємо суму небезпеки ворожих магів, які знаходяться між своїм магом і контрольною точкою.
  4. Додаємо перевага сил у колі заданого радіусу і в центрі між положенням мага і контрольною точкою.
  5. Нормалізуємо отримані значення і вуаля — шанс перемоги є.
Шанс на перемогу 100%, якщо сили союзників більше на півтора мага першого рівня, ніж ворожі сили.
Тому в іграх без рівня я не часто нападає, так як для атаки шанс на перемогу має бути більше 50%, що не так часто трапляється, за умови, що крип становлять близько 20% сили одного мага, і хп магів найчастіше рівні.

Небезпека мага оцінюється як сума 10 значень: дпс, наявність певних магій, кількість хп, наявність бафів і дебафов, кулдаун магії, кількість мани. Кожен коефіцієнт підбирався на око і потім потихеньку підганявся. В принципі написання більш точних коефіцієнтів в цьому місці, не може значно поліпшити стратегію.

Ухилення від снарядів

Самий ефективний алгоритм з усіх існуючих, і при цьому майже найпростіший.
Спочатку для ухилення була написана функція емуляції руху в заданому напрямку. Тобто стратегія оцінює, скільки снаряду ще максимум летіти тиків і емулює, рух мага в деякому напрямку, з урахуванням, що він повертається на кожному твк до нього. Якщо снаряд потрапив в мага, значить, даний напрямок помилкове і треба подивитися в іншому напрямку. Якщо у всіх напрямках потрапляє снаряд, значить ухилитися неможливо.
Спочатку стратегія вважала 3 напрями, або в 6 якщо розглядати руху передом і задом за різні напрямки. Але через деякий час зрозумів, що такі відхилення не дають часу для нападу чи відступу і став спочатку вважати куди краще йти, а потім проганяти ухилення для 60 напрямків, щоб знайти те, яке найкращим чином збігається з напрямком руху.

Тут слабким місцем, я вважаю той факт, що при увороте я завжди рухаюся і повертаюся в одному напрямку. У теорії цей алгоритм можна поліпшити і знаходити не найкраще відхилення руху, але при цьому мінімальне відхилення по кутку. Такий підхід збільшив шанси на перемогу в сутичці, так як щоб стріляти в супротивника треба зробити поворот на менший кут, ніж при поточному алгоритмі. Це могло б заощадити 2-3 тика, що дуже істотно при умові, що маг може стріляти раз в 60 тиків, а снаряд летить до мага близько 12 тактів.

Але я не описав одного нюансу — при ухиленні варто враховувати ще перешкоди навколо: дерева, крип, магів, будівлі. Для цих цілей, перш ніж вважати напрям руху, шукаються всі перетину в цьому напрямку, і вибирається саме наиближайшее до нас. Тобто в підсумку виходить не вектор, в якому рухатися, а відрізок. Так як частина об'єктів кожен тик зміщуються, але у них немає інерції, то щоб зайвий раз не обрізати собі можливість уворота, радіус об'єкта кожен «тік» зменшується на швидкість об'єкта. Для магів це їх максимальна швидкість, а для крип залежить від напрямку руху. Так, якщо крип рухався в нашому напрямку, то його радіус навпаки збільшиться, а не зменшиться. «твк» я взяв у лапки, так як там немає симуляції руху, за місце цього там формула, яка вираховує твк грунтуючись на відстані до перетину з об'єктом.

Пошук оптимальної позиції
Якщо вважати користь алгоритму як – 'перевага дане алгоритмом'/'кількість рядків коду', то це самий непотрібний алгоритм. Але, на жаль, без нього маг б не зміг рухатися. Всі команди знаходяться в папці move і defense + парочка з attack відповідають за підрахунок руху. Точніше кожна команда повертає вектор, куди треба рухатися, пріоритет руху в цьому напрямку і таку ж пару для повороту. Часто поворот і рух збігаються, але не завжди. Самі команди — це деякі складні функції, які за деякими критеріями вважають ці вектора. Всього існує 9 команд руху:
  • Переслідувати ворожого мага
  • Бігти атакувати в ближній бій
  • Триматися на відстані від вежі
  • Триматися на відстані від кріпа
  • Ухилятися від снаряда
  • Триматися на відстані від ворожого мага
  • Підбігти, щоб отримати досвід
  • Бігти до бонусу
  • Бігти до лінії фронту
Майже кожна з них може повторюватися, і у них різний пріоритет, який в свою чергу залежить від різних факторів. Наприклад, для атаки в ближньому бою шанси на перемогу мають бути високі. Або якщо ворожий маг може ухилитися від снаряда, то стріляти в нього будемо в останню чергу. Описувати всі пріоритети може зайняти ще одну статтю, а сенсу в цьому майже немає – все одно вони підбиралися на око.

Після підрахунку всіх таких векторів, стратегія знаходить серед них обов'язковий з максимальним пріоритетом. Якщо такого немає, то знаходить серед усіх вектор з максимальним пріоритетом і усереднює його. Обов'язковими вважаються два види векторів — увороти від снаряда і відхід від вежі. Під усередненням розуміється сума векторів, які відхилені від максимального не більше ніж на 45 градусів і з урахуванням їх пріоритету. Зроблено це для більшої точності, куди відходити, якщо поруч з магом багато майже однакових векторів — наприклад, поруч два ворожих кріпа. При цьому для обов'язкових векторів таке робити не бажано – вони розраховані так, що якщо їм не слідувати, то можна отримати шкоди.

Пошук шляху
Перша версія пошуку шляху була досить простий, і була написана до раунду 1 – за заданим точкам, яких було близько 50, був створений статичний граф, в якому знаходився найкоротший шлях до точки. Так як кінцева точка і точка де знаходиться маг, були не на самому шляху, то з цих точок будувався перпендикуляр до наиближайшим заданим ребрах графа.
Найбільший мінус, який я бачив у такого підходу – це був далеко не найліпший шлях і щоб оцінити час за яке можна дійти до точки, що була написана простенька евристика яка давала якийсь наближений коефіцієнт – наскільки теоретично найкоротший шлях відрізняється від підрахованого.

Тому до раунду 2 був написаний більш складний, але і більш точний пошук шляху. Крім кращої оцінки довжини шляху, він ще дозволяв оцінити шлях з урахуванням рубки дерев, що в ряді випадків дозволяє заощадити час. Алгоритм являє собою об'єднання Чи і Дейкстри і принцип його роботи можна описати так:

Створюємо сітку розміром 125x125 з цінами на карті. Там де нікого немає – ціна 1, по краях карти ціна нескінченна. Після до ціни додається ціна за прохід по дереву, яка залежить від радіуса дерева — в центрі дерева вона максимальна, а до країв знижується. Для крип і веж встановлюються майже нескінченний ціни. Також карта впливів для ворожої сторони теж відмовляє невеликий вплив на ціни в пошуку шляху – потрібно це щоб не лізти в центр битви, а обходити його.

Після чого пускалася хвиля з поточної точки мага, схожа з хвилею з алгоритму, але пускалася вона завжди на всю карту, і враховувала ваги переходу в клітку. Саме із-за ваг переходу сам алгоритм все ж більше схожий на Дейксту ніж на:
  1. Створюється карта ваг – всі ваги нескінченні, і створюється стек точок переходів
  2. Для поточної точки встановлюємо нульову вагу, і вона заноситься як точка переходу
  3. В циклі, поки є точки переходу:
    1. Дістаємо першу точку переходу
    2. Переглядаємо всіх сусідів (4 сусідні клітини), і вважаємо попередні ваги в цих клітинах – поточний вага клітки + ціна у сусіда

    3. Якщо отриманий вага менше поточного ваги в клітці, то міняємо вагу, і додаємо клітку в стек точок переходу
    4. Переходимо до наступної ітерації
Якщо проаналізувати цей алгоритм, то така реалізація алгоритму, без урахування ціни переходу, має оцінку O(N*M), тобто кожну клітину алгоритм обійшов рівно один раз. Можна ще додати множник `*4` так як йде перевірка сусідніх клітин. З-за наявності ваг кожну клітину алгоритм може відвідати кілька разів, але це не критично. Правда одне обмеження якого немає у Чи додається – треба обов'язково обійти всю карту. Але для нас це не критично, так як в подальшому по цій карті можна швидко знайти шлях до будь-якої точки, яких в середньому за тик близько 5, а в екстремальних ситуаціях може доходити до 10 і більше.
Щоб ще сильніше зменшити час побудови, дана карта перераховується раз на 30 твк. Якщо маг за цей час змінює клітку в якій він зараз перебуває, то відпрацьовує швидка підміна ваги. Підміну ваги коротко можна описати так — у новій клітці вага робимо нульовою, в старій встановлюємо значення дещо менше одиниці. Значення дещо менше одиниці залежить від того, скільки разів ми змінили клітку за останні 30 тиків. Це потрібно, щоб в подальшому, при пошуку шляху, алгоритм завжди міг потрапити в поточну точку, яка з нульовим вагою.

Сам пошук шляху по карті ваг не представляє нічого складного: З деякої точки будуємо шлях так, щоб завжди вибирати найменшу ціну з сусідніх клітин. Правда тут вже сусідів 8, а не 4 і для діагональних сусідів ціна переходу завищується на sqrt(2).

Рубка лісу
Після того як шлях побудований, можна запросити інформацію про те, які дерева треба зрубати. Будь шлях представляється у вигляді набору коротких відрізків, які були побудовані по сітці. Ці відрізки я буду називати сегменти. Для отримання інформації про те, які дерева заважають, застосовується наступний алгоритм:

Йдемо по шляху і знаходимо дерево, яке найближче до нашого поточного сегменту шляху і при цьому не далеко від нього. Переконуємося, що це дерево нам насправді підходить — його не можна обійти. Для цього образно ділимо наше ігрове поле на дві частини – по одну сторону шляху і за іншу. Якщо є таке дерево, яке належить іншій стороні дороги і між цими двома деревами не можна пройти, значить, поточне дерево треба рубати.

Правда є проблема — у місцях, коли шлях проходить близько до середини дерева і дерево в підсумку виявляється не в тій половині шляху, в якій би коштувало, дерево може бути не позначено під зруб, незважаючи на те, що таким є. Можлива і зворотна ситуація, коли дерево начебто не мішається, але потрапив не в ту половину шляху.

На цю проблему я закрив очі – виявилася не критичною, хоча можна вирішити не дуже складним чином.

Обхід перешкод
Самий перший алгоритм, який був написаний і самий не змінний. За фактом алгоритм пошуку шляху описаний вище, не обов'язковий і писався з розрахунків, що алгоритм обходу перешкод вже є і він робочий.

На те як маг ходить з використанням тільки обходу перешкод можна подивитися в відео. Відео трохи загальмований, з-за того що знімалося в режимі debug.

Сам алгоритм заснований на прорахунку внутрішніх дотичних між об'єктами. Це було можливо, так як всі об'єкти в світі представляються колами.

Перше, що кидається в очі при перегляді відео, то це постійно сіпаються фіолетові лінії. Самі лінії в алгоритмі не використовувалися, але таке відображення виявилося найбільш ефективним, щоб розуміти, де яка група об'єктів. Щоб зрозуміти, що таке група об'єктів, можна подивитися на 40 секунду відео – там маг йде в ліс і проходить між двома групами. Якщо давати визначення, групи об'єктів – це не перетинаються підмножини всього безлічі об'єктів на карті, такі що між будь-якими двома об'єктами з різних підмножин може пройти маг, ну або відстань між двома об'єктами більше ніж діаметр мага + радіус першого об'єкту + радіус другого об'єкта.

Перша частина алгоритму займається побудовою цих груп. Робиться це так:
Спочатку маємо безліч об'єктів і пусте безліч груп. Беремо об'єкт з множини об'єктів і перевіряємо – якщо він потрапляє в одну групу, тобто знаходиться близько до одного з об'єктів групи, то додаємо його туди. Якщо він потрапляє більше ніж в одну групу, то об'єднуємо всі такі групи і додаємо в нову велику групу новий об'єкт.

Далі йде визначення, куди рухатися у поточному тику. Робиться це на підставі: безлічі груп, позиції мага і точки, куди хочемо прийти. Я б цей алгоритм назвав так – кидання променів, хоча насправді все ж це не промені, а відрізки, так як у них є макс довжина.
  1. Спочатку кидаємо промінь в точку, куди хочемо прийти.
  2. Знаходимо перетин з групою, об'єктом з групи, який найближче до нас.
  3. Проходимо по всіх об'єктах обраної групи і для кожного вважаємо обидві внутрішні дотичні.
  4. Знаходимо дотичні, які будуть давати максимальний кут відхилення від поточного променя – їх буде дві (одна вліво інша вправо).
  5. Далі по магічною логіці (див. нижче), вибираємо одну з двох.
  6. Точка дотику з урахуванням радіуса мага, буде нашою новою точкою, куди треба рухатися.
  7. Після чого знову кидаємо промінь, але в нову точку, попередньо видаливши ту групу, з якою ми вже перетиналися.
Щоб зрозуміти причину існування «магічної логіки», давайте розглянемо картинку:

Спочатку кут a1 менше кута a2, і логічніше піти в сторону кута a1, оскільки там повинен бути шлях коротше, але по мірі наближення до точки торкання, кут a1 починає підвищуватися, а кут a2, навпаки, знижуватися. З цієї причини вся магічна логіка полягала в тому, що враховувався не тільки кут, але і відстань. Після появи пошуку шляху ця проблема відпала, так як сам промінь вже був наближений до ідеального.

висновок
Якщо порівняти мій варіант рішення з варіантом рішення Commandos (друге місце у фіналі, але ми то знаємо, що насправді перше), то його рішення більш лаконічне і просте, але не дозволяє робити тактичні оцінки, зате дає майже ідеальне рішення у локальних боях. Всі мої алгоритми зав'язані на прийняття тактичних рішень і на гру по всій карті, ніж для локальних боїв. При цьому ті самі локальні бої у мене зроблені дуже складно і громіздко.
З цієї причини я вирішив описати своє рішення – у мене воно відрізняється своїм напрямком у порівнянні з рішеннями топ гравців.

Для тих, хто захоче писати олімпіаду в наступному році, а кількість людей з року в рік явно зростає, раджу спати ночами… Краще потрать дві години на код, але він буде хороший ніж написати вночі і потім протягом тижня шукати помилки в коді. Для себе я зробив такий висновок, коли переглядав свій код в «тверезому стані. Власне сам код можна подивитися тут: github.com/ivlevAstef/CodeCupAI2016MOBA. Там багато коментарів на російській, які можуть допомогти розібратися в коді. Правда для розуміння архітектури доведеться витратити час.
Основні файли, де знаходяться ті чи інші алгоритми
  • 2д математика – Common/C_Math
  • Пошук шляху — Algorithms/A_PathFinder

  • Обхід перешкод — Algorithms/A_Move
  • Побудова груп — Environment/E_World
  • Ухилення – Algorithms/A_Attack
  • Карта впливів – Environment/E_InfluenceMap
  • Пошук оптимальної позиції – вся папка Command і Strategy/S_CommandStrategy
  • Оцінка результату локальної битви – Algorithms/A_WinPredictor

Хочу також відзначити учасника з ніком firano (Лобанов Леонід) за непосильну допомогу з написанням цієї статті.
І велике спасибі Роману Удовиченко (Romka за організацію чату в телеграмі і всім активним учасникам цього чату. Без вас написання олімпіади було б набагато нудніше, хоч і продуктивніше.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.