Єдина Країна!

Головне меню

Наша кнопка

Українські уроки про ІТ

Друзі

Підтримка української армії


Головна Програмування - C++ Пересування ворогів (алгоритми пошуку шляху)

Пересування ворогів (алгоритми пошуку шляху)
Написав farsh   
Субота, 27 липня 2013 21:04
Переглядів: 2870

Переслідування та відступ

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

bool pmg::Hunter::aim(pmg::Game *game, int evade) {
	if (position() = game->position()){
		return false;
	}
	moveX = sign(position()->x() - game->position()->x());
	if (evadde) {
		moveX *=-1;
	}
	return true;
}

int pmg::Hunter::sign(int difference) {
	return ((difference < 0 ? -1 : 1);
}

// решта коду

/* Монстр полює на гравця, якщо останній параметр дорівнює нулю
* передавайте 1, якщо хочете, щоб монтр
* втікав.
*/
hunter->aim(game, 0);

 

Патрулювання

У деяких іграх монстри здатні патрулювати місцевість (рух з точки А в точку В, потім до точки С і так далі , при цьому остання точка з’єднується з першою). Це не набагато складніше за попередній алгоритм. Єдина різниця у тому, що монстри «переслідують» точки шляху (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, які обчислюються відносно монстра. Правила для знаходження цих значень дуже прості:

  1. Припустимо, що монстр вільно переміщується по ігровому полю, наприклад, з верхньої лівої до нижньої правої його частини. Якщо він натрапив на лівий бік перешкоди, тоді нехай рухається вниз.
  2. Якщо ж зіткнення відбулося у напрямку якої-небудь осі, тоді повернемо протилежний напрямок за тією ж віссю. Якщо перешкода має ІО = (-1, 1) і отримує удар від чогось, що рухається по осі Х, слід повернути 1.

Очевидний недолік цього прийому полягає у необхідності збереження додаткової інформації для кожного об’єкту. Можливий варіант оптимізації: ви можете відвести для цих даних усього лишень 4 біта.

(Примітка: можна сформувати набір точок шляху для обходу кожної перепони, тоді монстр, який наштовхнеться на перешкоду, виконає запит про те, як її обійти.)

 

Пересування, реалізоване в Zelda

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

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

 

Хитрість – вистежування гравця

Одним дуже ефективним способом дістати гравця є використання «собак»: агресивних і слабких створінь, які будуть слідувати за гравцем (якщо вони не будуть достатньо слабкими, то гра вийде погано збалансованою). Ви можете зберегти напрямок переміщення гравця як список його позицій на полі. Це дає можливість "собаці" ефективно переслідувати гравця (такий прийом можна з успіхом застосовувати у іграх типу Pac-Man).

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

 

2003 (с) Сергій Анісімов, Сергій Іванов, Lennart Steinke

Узято звідси - http://pmg.org.ru/galaxy2d/ai.htm

 

Якщо ви знаєте цікаві і ефективні алгоритми пошуку шляху пишіть сюди farsh


( 6 Проголосувало )

Схожі статті:
Новіші матеріали:
Старіші матеріали:

Коментарі
Добавити новий
Залишити коментар
Ім`я:
e-mail:
 
Тема:
 
:angry::0:confused::cheer:B):evil::silly::dry::lol::kiss::D:pinch:
:(:shock::X:side::):P:unsure::woohoo::huh::whistle:;):s
:!::?::idea::arrow:
 
Введіть цей настирливий код
Русская редакция: www.freedom-ru.net & www.joobb.ru

3.26 Copyright (C) 2008 Compojoom.com / Copyright (C) 2007 Alain Georgette / Copyright (C) 2006 Frantisek Hliva. All rights reserved."

 

Підписка

Хто онлайн?

Немає
На даний момент 29 гостей на сайті

Український рейтинг
TOP.TOPUA.NET