Способи пересування комп’ютерних персонажів (частина 3)

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

Анімація плиткових переміщень

Плиткові рухи здаються дуже «рваними», і якщо для покрокової стратегії це допустимо, то в режимі реального часу виглядає відверто убого. Щоб залишитися в рамках плиткових переміщень, але надати трохи лиску, вигадали один цікавий підхід: переходи між клітинами здійснюється поступово (попіксельно) з певною швидкістю, але перервати такий рух не можна. Тобто, якщо наш моб пішов уперед – то увімкнулася «анімація» його руху, і він плавно перейшов у потрібну нам клітинку. Це добре ще для того, щоб була можливість задавати швидкість пересування, причому не лише штучному інтелекту, а й керованим нами персонажем. Я зіткнувся з таким способом у грі "Final Fantasy II" (на мобільному), але думаю це використовується у всіх плиткових RPG такого типу. Реалізація такого руху мало чим відрізняється від звичайного переміщення у плитковому світі. Буде два типи координат – у пікселях (для малювання персонажа – float x, y) та у клітинах (для розрахунків – int PosX, PosY). Нам потрібно додати прапор ходьби (bool Walk) – який вказує перебувати наш об'єкт зараз у русі чи ні. Ще лічильник зроблених мобом кроків (int Steps). І трохи доопрацювати функцію переміщення. Покажу на прикладі руху вліво – змінюватиметься лише змінна X:

Поєднання векторних та піксельних переміщень

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

Сітка прохідності

Найчастіше перешкоди можна окреслити якимось примітивом, котрий іноді прямокутником. У такому разі немає необхідності прораховувати зіткнення з усіма опуклостями та нерівностями перешкоди. Але все одно, якщо таких об'єктів багато, доводиться вважати зіткнення з усіма потенційними об'єктами, що може бути витратним. Тоді застосовують сітку прохідності. На всю карту світу накладається невидима сітка, що є двовимірним масивом змінних типу bool. Якщо в якійсь клітці знаходиться перешкода, то значення стає true, відповідно і навпаки. Сітка дублює перешкоди, але прорахунки зіткнень стають значно простішими, і навіть якщо наш об'єкт рухається по вектору – він легко може звернутися до цієї сітки із запитом: чи немає там перешкоди? Розмір комірки потрібно підбирати так, щоб оптимізувати точність і кількість прорахунків: занадто велика призведе до грубих незграбних перешкод, занадто дрібна – до більшого числа прорахунків. Щоб визначити, чи можна рухатися в наступну точку, потрібно вирахувати в яку клітинку сітки прохідності ми потрапимо і дізнатися про її стан. Для цього потрібно розділити координати нарозмір клітини та відкинути дробову частину.

Оптимізація векторних переміщень

Якщо у нас досить багато об'єктів (більше 200), то прорахунки зіткнень «усі з усіма» можуть бути витратними. Саме для цього можна застосувати чергову комбінацію векторних та плиткових світів. Як і в попередньому прикладі, всі об'єкти, особливо динамічні, дублюються в сітці, але цього разу замість прапора «вільно/зайнято» буде id моба або навіть вказівник на нього, щоб можна було швидко до нього звернутися. Правда доведеться зіткнутися з трудом – якщо об'єкт виходитиме за межі осередку (що цілком можливо), доведеться вказувати його положення в кількох суміжних осередках. Також можливий варіант одночасного знаходження кількох об'єктів у одній клітині, отже краще використовуватиме цього динамічні масиви. Ось приклад класу «клітина», у тому числі потім складається масив всіх клітин карти.

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

Доступ до конкретного мобу, що знаходиться в конкретній клітині, можна отримати так:

Порівняння методів переміщення

Виділимо ряд критеріїв та порівняємо всі, розглянуті вище методи переміщень. Наголошу, що існують способи оптимізації, здатні усунути ті чи інші недоліки методів, оцінимо їх, так би мовити, «у чистому вигляді».

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