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

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

image

Читати далі →

Реалізація хвильового алгоритму знаходження найкоротшого шляху до динамічно рухомим об'єктам в unity3d на C# в 2d гри

У цій статті я хочу показати як реалізувати хвильовий алгоритм і мою модифікацію його для роботи з динамічними об'єктами в unity3d.

Область застосування

Даний метод підходить для 2д ігор. А його модифікація для знаходження шляху до рухомих об'єктів. Область застосування дуже широка і зачіпає безліч ігрових жанрів і ситуацій, наприклад:
  1. Ігри жанру ТД. Де ігрові локації зручно представляти у вигляді матриці прохідності, приміром 0 — ділянка по якому можна переміщатися, -1 — область недоступна для переміщення, -2 — пастка і т. д.;
  2. Стратегічні ігри, особливо покрокові. Наприклад бої в серії ігор «Герої Меча і Магії»;
  3. Платформери;
  4. Шашки, шахи, змійка і інші.

Обґрунтування написання статті

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

Читати далі →

Використання потенціальних полів у сценарії стратегії реального часу

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

Цей урок описує метод планування перебігу гри і навігації юнітів, який використовує багатоагентні потенційні поля. Він заснований на роботах під номерами [1, 2, 3]. (Дивись в кінці статті посилання на використовувані матеріали)




Читати далі →

Алгоритми інтелектуальної автогенерации рівнів в iOS грі

Всі помилки по даній статті надсилайте, будь ласка, в особисті повідомлення.

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

Повернемось до нашого завдання, нам потрібно інтелектуально генерувати карти для IPhone/IPad ігри типу «Маріо», для початку ми розглянемо генерацію карти в межах поля 128х128 кубів.

Читати далі →

Мурашиний алгоритм MMAS

Вітаю всіх читачів. Сьогодні спробую продовжити серію досить рідкісних статей, присвячених природним алгоритмами. Зокрема, ця стаття буде присвячена модифікації мурашиного алгоритму, відомої як Max-Min Ant System (MMAS). Я розповім про відмінності від класичного мурашиного алгоритму і про причини внесення таких модифікацій. Подробиці під катом.

Читати далі →

Пишемо компонент руху для RTS в Unreal engine 4

Привіт, мене звати Дмитро, програміст з Snowforged Entertainment. Я тільки що закінчив рефакторинг компонента руху кораблів для проекту Starfall Tactics — тактичної гри в реальному часі, в якій гравці можуть зібрати свій власний космічний флот і повести її в бій. Компонент руху листувався вже три рази, від релізу до початку розробки альфа версії. Було зібрано безліч граблів, архітектурних і мережевих. Спробую підбити весь цей досвід і розповісти вам про: Navigation Volume, Movement component, AIController, Pawn.

Читати далі →

Алгоритми пошуку шляхів на JavaScript



Пошук оптимального маршруту юніта до невідомої мети на карті — одна з найскладніших завдань при розробці гри. На щастя, існує деяка кількість алгоритмів, які вирішують цю задачу. Є відмінна бібліотека PathFinding.js з підтримкою 11 таких алгоритмів.

Читати далі →