Движение по клеткам, волновой алгоритм

Наша задача, организовать движение юнитов по клеткам, как в пошаговых стратегиях, наподобие King's Bounty и похожих. То есть, речь идет о небольшом поле, типа шахматной доски, где собственно и происходит бой юнитов. Существуют различные алгоритмы поиска пути в двумерном массиве, у каждого из них есть свои достоинства и недостатки. В нашем же случаи, мы будем использовать волновой алгоритм (Алгоритм Ли), он отлично подходит под наши задачи, понятен и прост в освоении. Реализация проекта, состоит из двух частей. Первая, это сам алгоритм и подготовка поля боя (массива) для него. Вторая часть, управление юнитами, создание маршрута движения и вектора вращения.


Тем кто играл в игры с пошаговыми боями, хорошо известно, что в процессе боя, на поле могут появляться временные объекты. Исходя из этого, нам нужно учитывать, что состояние клеток поля может меняться не только после хода, но и до него. Поэтому, для обновления состояния поля, мы будем использовать рейкаст, чтобы проверить занята-ли клетка и какой объект ее занимает.

Пара слов о модели юнита:

Движение по клеткам, волновой алгоритм

Модель нужно создавать так, чтобы "лицо" юнита было по направлению оси Z. Так же, у юнита должен быть коллайдер и установлен стандартный тег Player, данный тег означает, что объектом можно управлять. Для 2D спрайта "лицо" модельки, это ось Х.

Шаблон клетки, это квадрат, мы рекомендуем стандартный Quad, так как его начальный размер равен единице. На шаблоне так же должен быть коллайдер, в режиме триггера, плюс, нужно установить для него отдельный слой, который потом указывается в настройках скрипта, это нужно, чтобы луч поиска клетки не "цеплялся" за другие объекты.

На шаблон клетки вешаем скрипт PathfindingNode.
Здесь у нас несколько переменных для хранения данных массива и состояния поля.

Волновой алгоритм с поиском пути Pathfinding.
Конечный результат выдается в виде массива клеток, которые ведут от юнита и до цели.

Далее, на сцену вешаем PathfindingField.
Это скрипт управления, здесь обрабатывается массив волнового алгоритма и на его основе создается маршрут и вектора направления для юнита. Движение юнита также делается тут, плюс, мы добавили комментарии, где можно сделать переключение анимации юнита (движение, разворот, ожидание, атака).


Стоит отметить, что игровое поле нужно делать только через данный метод в редакторе.

Если на игровом поле был удален объект или добавлен новый:

PathfindingField.UpdateNodeState();

Нужно сделать вызов данного метода, чтобы обновить состояние клеток.

Скачать все скрипты и демо проект:
https://www.patreon.com/posts/dvizhenie-po-23168944
Тестировалось на: Unity 2017.1.0

Комментариев 31

Офлайн
neveryes 29 декабря 2017
Это гениально!!!!!!!!!!
Офлайн
Reven 18 января 2018
Большой минус что конкретного объяснения нету.
Офлайн
Light 18 января 2018
Reven, конкретно что? В алгоритме есть уточняющее комментарии, сам код по сути состоит из простых условий. Если этого недостаточно для понимания, значит нужно еще раз всё посмотреть и разобрать по частям.
Офлайн
Reven 19 января 2018
Light,не мне более понятно, просто есть новечки которые не поймут это без коментариев
Офлайн
Light 19 января 2018
Reven, там они есть, а если кому-то что-то непонятно будет, есть возможность задать здесь свои вопросы. Не вижу проблемы вообще.
Офлайн
Reven 21 января 2018
я хотел спросить вы пишите: if(map[x-1, y-1].cost >= 0) // если клетка проходимаю. Но cost ведь везде -1 кроме занятых клеток. Почему так ? И как определяется step ?
Офлайн
Light 21 января 2018
Reven, поиск начинается с того, что всё поле -1, а препятствия -2. Та клетка куда игрок кликает становится = 0 и с этой клетки начинается поиск, потому что step тоже = 0. Если клетки рядом (лево/право и верх/низ) равны -1 то тогда они переходят в значение step+1 сам step тоже +1. После идет следующий цикл...


Если клетка, где находится юнит получит число больше -1, то поиск прекратится, значит цель достигнута.

Второй этап это прокладка маршрута. Начинается это с клетки юнита, на картинке выше показано что клетка = 4, это ее цена. Затем, проверяются клетки рядом с ней (горизонталь/вертикаль/диагональ) ищется та клетка, которая больше или равна нулю, но дешевле (меньше) базовой. Опять же, смотрим картинку, получается что с начала ищется клетка под номером 3, потом 2 и т.п. Так и получается маршрут 4-3-2-1-0.
Офлайн
Reven 21 января 2018
Спасибо большое
Офлайн
Reven 28 января 2018
Хотел еще спросить bowtie вы пишите if(map[start.x, start.y].cost != -1) break; // если путь найден, выходим из цикла но map[start.x,start.y]. cost == 0 следовательно он выйдет из цикла сразу . обясните пожалуйста может я что то неправельно понял .
Офлайн
Light 28 января 2018
Reven, в начале поиска нулю равен map[end.x, end.y].cost, все остальные позиции, включая map[start.x, start.y].cost, в значении -1, а непроходимые места = -2.
Офлайн
Reven 28 января 2018
Light,
просто вы написали "Та клетка куда игрок кликает становится = 0"
Офлайн
Light 28 января 2018
Reven, всё верно, просто на картинке слово start обозначает лишь стартовую позицию поиска и не относится к переменным алгоритма.
Офлайн
ARTyouMAS 24 марта 2018
Ребят, очень нужна ваша помощь. Как сделать так что б наискось нельзя было ходить?Только прямо. Help fearful
Офлайн
Light 24 марта 2018
ARTyouMAS, нужно изменить алгоритм поиска, убрав проверку по диагонали. Конкретно, меняется скрипт Pathfinding, следующим образом:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public static class Pathfinding {

	public static List<PathfindingNode> Find(PathfindingNode start, PathfindingNode end, PathfindingNode[,] map, int width, int height)
	{
		int x, y, cost = 0, step = 0;

		map[end.x, end.y].cost = 0; // начало поиска с точки назначения

		if(start.x - 1 >= 0)
		{
			if(map[start.x-1, start.y].cost == -2) step++;
		}
		else step++;

		if(start.y-1 >= 0)
		{
			if(map[start.x, start.y-1].cost == -2) step++;
		}
		else step++;

		if(start.x+1 < width)
		{
			if(map[start.x+1, start.y].cost == -2) step++;
		}
		else step++;

		if(start.y+1 < height)
		{
			if(map[start.x, start.y+1].cost == -2) step++;
		}
		else step++;

		// проверка на доступность (например, юнит окружен)
		if(step == 4) return null; else step = 0;

		while(true) // цикл поиска
		{
			for(y = 0; y < height; y++)
			{
				for(x = 0; x < width; x++)
				{
					if(map[x, y].cost == step) // находим клетку, соответствующую текущему шагу
					{
						if(x-1 >= 0) // если не выходим за границы массива
						if(map[x-1, y].cost == -1) // если клетка еще не проверялась
						{
							cost = step + 1; // сохраняем стоимость клетки
							map[x-1, y].cost = cost; // назначаем стоимость
						}

						if(y-1 >= 0)
						if(map[x, y-1].cost == -1)
						{
							cost = step + 1;
							map[x, y-1].cost = cost;
						}

						if(x+1 < width)
						if(map[x+1, y].cost == -1)
						{
							cost = step + 1;
							map[x+1, y].cost = cost;
						}

						if(y+1 < height)
						if(map[x, y+1].cost == -1)
						{
							cost = step + 1;
							map[x, y+1].cost = cost;
						}
					}
				}
			}

			step++; // следующий шаг/волна

			if(map[start.x, start.y].cost != -1) break; // если путь найден, выходим из цикла
			if(step != cost || step > width * height) return null; // если путь найти невозможно, возврат
		}

		List<PathfindingNode> result = new List<PathfindingNode>(); // массив пути

		// начало поиска со старта
		x = start.x;
		y = start.y;

		step = map[x, y].cost; // определяем базовую стоимость

		while(x != end.x || y != end.y) // прокладка пути
		{
			if(x-1 >= 0)
			if(map[x-1, y].cost >= 0)
			if(map[x-1, y].cost < step)
			{
				step = map[x-1, y].cost;
				result.Add(map[x-1, y]);
				x--;
				continue;
			}

			if(y-1 >= 0)
			if(map[x, y-1].cost >= 0)
			if(map[x, y-1].cost < step)
			{
				step = map[x, y-1].cost;
				result.Add(map[x, y-1]);
				y--;
				continue;
			}

			if(x+1 < width)
			if(map[x+1, y].cost >= 0)
			if(map[x+1, y].cost < step)
			{
				step = map[x+1, y].cost;
				result.Add(map[x+1, y]);
				x++;
				continue;
			}

			if(y+1 < height)
			if(map[x, y+1].cost >= 0)
			if(map[x, y+1].cost < step)
			{
				step = map[x, y+1].cost;
				result.Add(map[x, y+1]);
				y++;
				continue;
			}

			return null; // текущая клетка не прошла проверку, ошибка пути, возврат
		}

		return result; // возвращаем найденный маршрут
	}
}
Офлайн
ARTyouMAS 24 марта 2018
Light,
Точно, что-то я не сообразил сразу) Спасибо большое!
Офлайн
StefanVanhazen 24 марта 2018
Хочу использовать это скрипт для 2D и чтоб персонаж ходил, только влево и вправо и я так понял просто убрать ось Y из скрипта не поможет
Офлайн
ARTyouMAS 24 марта 2018
Цитата: StefanVanhazen
Хочу использовать это скрипт для 2D и чтоб персонаж ходил, только влево и вправо и я так понял просто убрать ось Y из скрипта не поможет

А зачем тогда этот скрипт вообще использовать?) Он был создан для поиска пути. В Вашем варианте игрок ходит только прямо\назад. Получается что путь всегда один и выбирать не приходится.
Офлайн
StefanVanhazen 24 марта 2018
ARTyouMAS,В статье ,как я понял , есть не только поиск пути , а разбивание поля на клетки, чтоб персонажи ходили именно по ним и я хотел бы это использовать , но только в 2D
Офлайн
ARTyouMAS 31 марта 2018
Снова я... Вообщем нужно сделать чтоб в скрипте было отдельное поле для конца пути - public PathfindingNode Ends; И функция которая при нажатии кнопки (onclickMoveBttn), строит путь к Ends. При это нажатие на сам объект и самопроизвольный выбор конца пути был запрещен. Так же нужно удалить динамическое выделение клеток поля при наведении. Можешь помочь?
Офлайн
Light 31 марта 2018
ARTyouMAS, по индивидуальным скриптам, можно обсудить в ЛС.
Офлайн
Aiseiriki 2 июня 2018
Light, здравствуйте, я ходил по этому сайту и наткнулся на такую тему: "https://null-code.ru/project/187-dvizhenie-po-kletkam-volnovoy-algoritm.html", и появилась пара вопросов. Если можете - ответьте, пожалуйста.
Как добавить сюда деление игроков на команды? Как дать им возможность ходить в одно и то же время, а после система покажет, кто и что совершил.
Прошу прощения за вторжение.
Офлайн
Light 2 июня 2018
Aiseiriki, это уже вопросы о том, "как создать игру". Здесь показан пример реализации алгоритма и как его использовать с конкретными игровыми объектами. Если нужна помощь в реализации чего-то, то мы можем обсудить это в личке.
Офлайн
Somewhere 17 июля 2018
На что вешается Pathfinding?
Офлайн
Light 18 июля 2018
Somewhere, его не нужно добавлять на сцену.
Офлайн
ingego Demin 19 августа 2018
Хэй, народ, всем привет, вопрос возник, а как делать ограничение по ходьбе ?
Офлайн
Light 19 августа 2018
ingego Demin, а если конкретнее.
Офлайн
Retr0 6 октября 2018
А все-таки как сделать ограничение(количество клеток на которые ходит персонаж) по ходьбе и прикрутить к разным юнитам?(+ как сделать стенки между клетками ,чтобы через них нельзя было проходить?).
Офлайн
Light 7 октября 2018
Retr0, для ограничения по количеству клеток, надо в скрипте Pathfinding найти:

return result;
и заменить на:

return (result.Count < 10) ? result : null;
Где 10 это количество клеток.
Офлайн
ugenT 14 декабря 2018
Привет! Использовал этот туториал для своей игры. Внедрил для главного героя, как нужно. Дошло дело до ботов и тут загвоздка. Как лучше это реализовать? Для них мне не нужна подсветка пути, клик по ним и прочее, бот просто должен ходить в рандомные точки по карте туда-сюда. Немого преобразовав код путь просто перестал генерироваться. Как не пытался исправить, ничего не вышло. Не подскажете в какую сторону думать?)
Офлайн
Light 14 декабря 2018
ugenT, если речь идет о больших картах, то надо другой алгоритм, адаптированный для тайловых карт. В этом случае для ботов, надо создать отдельный класс управления, который будет определять зону перемещения в рамках тайловой карты и соответственно рандомно будет ботов перемещать по своей зоне.

Заказать скрипты по данному вопросу можно мне в ЛС.
Информация
Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.
  • Яндекс.Метрика