Пересування ворогів (алгоритми пошуку шляху) |
Написав farsh | |||||
Субота, 27 липня 2013 21:04 Переглядів: 2870
|
|||||
Переслідування та відступНайпростіший спосіб змусити монстра переслідувати персонажа гри - це рухатись безпосередньо до нього, а найпростіший спосіб втекти від нього – рухатись у протилежному напрямку. Нижче наведено простий алгоритм такої поведінки, але він функціонує лише за умови відсутності перешкод. Алгоритм порівнює дві позиції (монстра та гравця, наприклад), і повертає напрямок руху. Але якщо між ними стане стіна, монстр банально упреться в неї.
ПатрулюванняУ деяких іграх монстри здатні патрулювати місцевість (рух з точки А в точку В, потім до точки С і так далі , при цьому остання точка з’єднується з першою). Це не набагато складніше за попередній алгоритм. Єдина різниця у тому, що монстри «переслідують» точки шляху (waypoints), а не гравця. У тій частині нашої програми, яка відповідає за пересування необхідно перевірити чи досягнув монстр потрібної точки, і якщо це дійсно так, то спрямувати його до наступної точки. Про це ще буде сказано нижче, при обговоренні системи руху, яка реалізована у грі Zelda. namespace pmg { class position { private: int abscissa, ordinate; public: void setX(int x); void setY(int y); int x(); int y(); }; } // десь у програмі... // ... // Ставимо ціллю наступну точку у циклі destination = waypoints->next(); // Поки ціль не досягнута while (monster->aim(destination, 0)) { // Рухаємось до неї monster->step(); } // ...
Подолання перешкодВороги, скеровані вищезгаданими алгоритмами, рухаються або безпосередньо до гравця, або ж у протилежному напрямку. Їх не хвилює тип місцевості, стіни, дерева і так далі. Найпростіший спосіб обійти цю проблему полягає в тому, щоб зберегти певну інформацію про огинання (IО) у кожному об’єкті. Якщо монстр натрапить на твердий об’єкт, то він зможе «спитати» його про те, у якому напрямку рухатись для того, щоб обійти перешкоду. В залежності від сторони, з якої відбулося зіткнення, кожна перешкода повертає пари dx/dy, які обчислюються відносно монстра. Правила для знаходження цих значень дуже прості:
span>Очевидний недолік цього прийому полягає у необхідності збереження додаткової інформації для кожного об’єкту. Можливий варіант оптимізації: ви можете відвести для цих даних усього лишень 4 біта. (Примітка: можна сформувати набір точок шляху для обходу кожної перепони, тоді монстр, який наштовхнеться на перешкоду, виконає запит про те, як її обійти.)
Пересування, реалізоване в ZeldaМонстри у Zelda переміщуються, як правило, використовуючи попередньо задані точки шляху (це стосується простих монстрів, а не босів). У кожній такій точці вони озираються навколо себе і ,якщо персонаж гравця потрапив до зони, яка контролюється одним із монстрів, він стає ціллю останнього. Такого ефекту можна досягти, якщо ви перевіряєте у кожній точці щляху, чи знаходиться гравець позаду чи попереду монстра (якщо монстр озирається по сторонам, то у першому випадку гравець вважається поміченим). Якщо монстр натрапляє на перешкоду, то він навіть не намагається оминути її, а лише методично тикається туди. До речі, у грі Diablo, здається, використовується подібний метод, але монстри там здатні рухатись вздовж перешкоди в різні боки з метою найти прохід до гравця. (Примітка: У Doom реалізовано трохи інший підхід: коли гравець потрапляє до сектору, тоді всі монстри спрямовуються до нього, навіть якщо вони його не бачать, те ж саме відбувається і при пострілі. )
Хитрість – вистежування гравцяОдним дуже ефективним способом дістати гравця є використання «собак»: агресивних і слабких створінь, які будуть слідувати за гравцем (якщо вони не будуть достатньо слабкими, то гра вийде погано збалансованою). Ви можете зберегти напрямок переміщення гравця як список його позицій на полі. Це дає можливість "собаці" ефективно переслідувати гравця (такий прийом можна з успіхом застосовувати у іграх типу Pac-Man). Якщо переслідувачі будуть швидшими за гравця, тоді це буде справжнє пекло для нашого героя. Уявіть також, що ми надамо їм здібність кликати інших. І тут уже не врятує навіть невидимість – нюх їх не підведе .
2003 (с) Сергій Анісімов, Сергій Іванов, Lennart Steinke Узято звідси - http://pmg.org.ru/galaxy2d/ai.htm
Якщо ви знаєте цікаві і ефективні алгоритми пошуку шляху пишіть сюди farsh ( 6 Проголосувало ) Новіші матеріали:
Старіші матеріали:
3.26 Copyright (C) 2008 Compojoom.com / Copyright (C) 2007 Alain Georgette / Copyright (C) 2006 Frantisek Hliva. All rights reserved." |