Алгоритм поиска пути в больших подземельях.

Темы, связанные с проектированием и программированием roguelike-игр

Модераторы: Sanja, Максим Кич

altmax
Сообщения: 173
Зарегистрирован: 15 сен 2012, 11:59

Алгоритм поиска пути в больших подземельях.

Сообщение altmax » 24 мар 2017, 11:18

Интересует алгоритм поиска пути для больших подземелий. Подземелья достаточно сложные, с тупиками и большие, карта сейчас 128х80.
Волновой алгоритм - работает медленно, если искать из конца в конец лабиринта - более 15 тыс итераций цикла для проверки клеток, помечена на или нет. Соответственно по времени занимает до 100 мс. В среднем 30 мс, правда на слабом процессоре.
Вот думаю, может хранить отдельно комнаты и пути между ними? Тогда количество вершин графа, через которые надо будет найти путь, сокращается на несколько порядков, да и есть готовые оптимизированные алгоритмы для этих целей.

Аватара пользователя
BreakMT
WANDER Team
Сообщения: 933
Зарегистрирован: 27 ноя 2006, 12:16

Re: Алгоритм поиска пути в больших подземельях.

Сообщение BreakMT » 24 мар 2017, 12:29

altmax писал(а):
24 мар 2017, 11:18
Интересует алгоритм поиска пути для больших подземелий. Подземелья достаточно сложные, с тупиками и большие, карта сейчас 128х80.
Волновой алгоритм - работает медленно, если искать из конца в конец лабиринта - более 15 тыс итераций цикла для проверки клеток, помечена на или нет. Соответственно по времени занимает до 100 мс. В среднем 30 мс, правда на слабом процессоре.
Вот думаю, может хранить отдельно комнаты и пути между ними? Тогда количество вершин графа, через которые надо будет найти путь, сокращается на несколько порядков, да и есть готовые оптимизированные алгоритмы для этих целей.
Я другого алгоритма не знаю, но вопрос - а зачем обрабатывать всю карту? Это для монстров которые точно знают куда и как идти? Я у себя ограничивал зону поиска не очень большим квадратом и было достаточно. Но, наверное, у тебя что-то другое.

altmax
Сообщения: 173
Зарегистрирован: 15 сен 2012, 11:59

Re: Алгоритм поиска пути в больших подземельях.

Сообщение altmax » 24 мар 2017, 12:48

Это пока абстрактный алгоритм, просто он есть в моей игре. Куда применить - пока не придумал, но вдруг пригодится ))) А так да - искать через всю карту вряд ли придется, может правда будет какой-нибудь монстр, который чувствует, где находится игрок.

Аватара пользователя
Xecutor
Мастер
Сообщения: 758
Зарегистрирован: 25 мар 2008, 08:32

Re: Алгоритм поиска пути в больших подземельях.

Сообщение Xecutor » 26 мар 2017, 03:43

Если у тебя нет клеток с разной стоимостью проходимости, то есть jump point search - оптимизация A* для клеточной карты без весов. Прям на порядок шустрее.

altmax
Сообщения: 173
Зарегистрирован: 15 сен 2012, 11:59

Re: Алгоритм поиска пути в больших подземельях.

Сообщение altmax » 26 мар 2017, 16:49

А нормального описания алгоритма не найдется? Чтобы не только русскими словами, но и на русском языке. А то на хабре какой-то странный перевод, слова вроде знакомые, но смысла не улавливаю.

Аватара пользователя
aspid
Сообщения: 192
Зарегистрирован: 28 мар 2016, 23:44

Re: Алгоритм поиска пути в больших подземельях.

Сообщение aspid » 27 мар 2017, 07:31

altmax писал(а):
26 мар 2017, 16:49
А нормального описания алгоритма не найдется?
Про А* просто и доходчиво тут есть, правда без оптимизации.
поперёк борозды

Аватара пользователя
Jolly Roger
Сообщения: 2973
Зарегистрирован: 27 ноя 2009, 09:10
Откуда: Minsk, Belarus

Re: Алгоритм поиска пути в больших подземельях.

Сообщение Jolly Roger » 14 апр 2017, 13:27

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

altmax
Сообщения: 173
Зарегистрирован: 15 сен 2012, 11:59

Re: Алгоритм поиска пути в больших подземельях.

Сообщение altmax » 19 апр 2017, 08:00

Как интересно в Dwarf Fortress ищут путь? Там же это приходится делать постоянно для нескольких сотен гномов и мобов. И мир там реально очень больших размеров.

Аватара пользователя
Jesus05
Сообщения: 1840
Зарегистрирован: 02 дек 2009, 07:50
Откуда: Норильск, сейчас Санкт-петербург.
Контактная информация:

Re: Алгоритм поиска пути в больших подземельях.

Сообщение Jesus05 » 19 апр 2017, 08:55

Пишут что там A*

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

Re: Алгоритм поиска пути в больших подземельях.

Сообщение kipar » 20 апр 2017, 13:07

В Kobold Quest, насколько я помню, в исходнике пометка что поиск пути из DF взят. Ну, выглядит как A* без изысков и оптимизаций - даже бинарной кучи нет.

gwathlobal
Сообщения: 68
Зарегистрирован: 10 май 2013, 16:30

Re: Алгоритм поиска пути в больших подземельях.

Сообщение gwathlobal » 20 апр 2017, 19:01

А что за бинарная куча?

altmax
Сообщения: 173
Зарегистрирован: 15 сен 2012, 11:59

Re: Алгоритм поиска пути в больших подземельях.

Сообщение altmax » 19 июл 2017, 07:06

Меня только сейчас посетила мысль, как ускорить волновой алгоритм. Можно при генерации карты в каждую её клетку записывать сразу и её соседей, а не вычислять их каждый раз при запуске алгоритма. Реально должно ускориться раза в 3-4. Вроде очевидная вещь, а сразу и не дошло...

Аватара пользователя
BreakMT
WANDER Team
Сообщения: 933
Зарегистрирован: 27 ноя 2006, 12:16

Re: Алгоритм поиска пути в больших подземельях.

Сообщение BreakMT » 19 июл 2017, 10:07

Все же пересчитывать придется, т.к. есть монстры, они двигаются и блокируют путь друг у друга

altmax
Сообщения: 173
Зарегистрирован: 15 сен 2012, 11:59

Re: Алгоритм поиска пути в больших подземельях.

Сообщение altmax » 19 июл 2017, 12:14

BreakMT писал(а):
19 июл 2017, 10:07
Все же пересчитывать придется, т.к. есть монстры, они двигаются и блокируют путь друг у друга
Ну хотя бы сами соседние клетки высчитывать не придется, а это как минимум 8 арифметических действий.

Аватара пользователя
Anfeir
Сообщения: 876
Зарегистрирован: 14 дек 2007, 09:29
Контактная информация:

Re: Алгоритм поиска пути в больших подземельях.

Сообщение Anfeir » 20 июл 2017, 09:56

У меня такая реализация A* в подземелье. Никаких бинарных куч, для ускорения процесса все "ноды" уже созданы для каждой клетки - тупо массив размером с карту... Для простоты все карты одного размера. Для исключения ресурсоемкости для тупых монстров (которых большинство) вводится ограничение на длину поиска. GetConsiderPassable() - метод у монстра, теоретически каждый монстр сам может решать, проходима для него заданная клетка или нет.

Код: Выделить всё

struct PathNode
{
	PathNode *nextNode;
	PathNode *prevNode;
	PathNode *cameFrom;
	
	int pathLengthFromStart;
	int heuristicEstimatePathLength;
	int estimateFullPathLength; // pathLengthFromStart + heuristicEstimatePathLength
	Pos position;
	signed char usage; 

	enum {UNUSED = 0, OPEN = 1, CLOSED = -1};
	void Init(Pos pos, int index)
	{
		this->position = pos;
		prevNode = nextNode = cameFrom = NULL;
		usage = UNUSED;

	}
	bool IsOpen() {return usage > 0;}
	bool IsClosed() {return usage < 0;}
	bool IsUnused() {return !usage;}
	bool IsUsed() {return !!usage;}
	int GetIndex() {return MAP_INDEX(position.x, position.y);}
	void SetEstimateFullPathLength()
	{
		estimateFullPathLength = pathLengthFromStart + heuristicEstimatePathLength;
	}

	void Detach(PathNode **heap)
	{
		if (prevNode) 
		{
			prevNode->nextNode = nextNode;
			if (nextNode) nextNode->prevNode = prevNode;
		}
		else 
		{
			if (nextNode) {nextNode->prevNode = NULL; *heap = nextNode;}
			else *heap = NULL;
		}
	}
	void Attach(PathNode **heap)
	{
		prevNode = NULL;
		nextNode = NULL;
		if (!(*heap))
		{
			*heap = this;
		}
		else
		{
			(*heap)->prevNode = this;
			nextNode = *heap;
			(*heap) = this;
		}
	}

};

struct Astar
{
	static PathNode allNodes[MAP_SIZE];
	static StorageVector<int> closedNodes;
	static PathNode *openSet;
	static Pos posTo;
	static int indexTo;

	static void InitStatic()
	{
		for (int y = 0; y < MAP_YSIZE; y++)
		{
			for (int x = 0; x < MAP_XSIZE; x++)
			{
				int index = MAP_INDEX(x, y);
				allNodes[index].Init(Pos(x, y), index);
			}
		}
		openSet = NULL;
	}

	static int GetHeuristicPathLength(Pos from, Pos to)
	{
		return util.Abs(from.x - to.x) + util.Abs(from.y - to.y);
	}

	static PathNode *NewNode(int index, PathNode *cameFrom, int pathLengthFromStart)
	{
		DBG( if (index < 0 || index >= MAP_SIZE) FAIL("index out of bounds in astar"));
		PathNode *node = &allNodes[index];
		DBG( if (node->IsUsed()) FAIL("node is already used!"));
		node->cameFrom = cameFrom;
		node->pathLengthFromStart = pathLengthFromStart;
		node->heuristicEstimatePathLength = GetHeuristicPathLength(node->position, posTo);
		node->SetEstimateFullPathLength();
		node->prevNode = node->nextNode = NULL;
		return node;
	}

	static void AddOpenNode(PathNode *node)
	{
		DBG( if (node->IsUsed()) FAIL("node is already used!"));
		node->usage = PathNode::OPEN;
		node->Attach(&openSet);
	}

	static void CloseOpenNode(PathNode *node)
	{
		DBG( if (!node->IsOpen()) FAIL("node is not open!"));
		node->usage = PathNode::CLOSED;
		node->Detach(&openSet);
		closedNodes.Add(node->GetIndex());
	}

	static PathNode *PickCurrentNode()
	{
		PathNode *n = openSet;
		PathNode *result = NULL;
		int minLength = 9999999;
		while (n)
		{
			if (n->estimateFullPathLength < minLength)
			{
				minLength = n->estimateFullPathLength;
				result = n;
			}
			n = n->nextNode;
		}
		return result;
	}


	static inline void ProcessNeighbor(Monster *ob, Area *area, PathNode *pathNode, int x, int y)
	{
		Surface *surface = area->GetCell(x, y)->GetSurface();
		int index = MAP_INDEX(x, y);
		PathNode *node = &allNodes[index];
		if (node->IsClosed()) return;
		if (!ob->GetConsiderPassable(surface) && index != indexTo) return;
		int neighborPathLengthFromStart = pathNode->pathLengthFromStart + 1;
		if (node->IsOpen())
		{                                                   
			if (node->pathLengthFromStart > neighborPathLengthFromStart)
			{
				node->cameFrom = pathNode;
				node->pathLengthFromStart = neighborPathLengthFromStart;
				node->SetEstimateFullPathLength();
			}
		}
		else
		{
			PathNode *neighborNode = NewNode(index, pathNode, neighborPathLengthFromStart);
			AddOpenNode(neighborNode);
		}

	}

	static void CleanAfter()
	{
		for (int i = 0; i < closedNodes.GetSize(); i++)
		{
			int index = closedNodes[i];
			DBG( if (index < 0 || index >= MAP_SIZE) FAIL("index out of bounds in astar"));
			DBG( if (allNodes[index].usage != PathNode::CLOSED) FAIL("closed expected"));
			allNodes[index].usage = 0;
		}
		closedNodes.Reset();
		PathNode *n = openSet;
		while (n)
		{
			PathNode *nextNode = n->nextNode;
			DBG( if (n->usage != PathNode::OPEN) FAIL("open expected") );
			n->usage = 0;
			n = nextNode;
		}
		openSet = NULL;
		DBG(int ttl=0; for (int i = 0; i < MAP_SIZE; i++) if (allNodes[i].usage) ttl++; if (ttl > 0) FAIL("incorrect clean!"));
	}

	
	static Surface *FindPath(Monster *ob, Pos posFrom, Pos posTo, StorageVector<int> *path = NULL)
	{

		//TODO: introduce more neat logic with lenghBound than below:
		int lengthBound = 20;	    
		if (ob->i_PlayerMind) lengthBound = 200;
		//if (ob->f_Intelligence >= 25) lengthBound = 500;

		DBG( if (openSet) FAIL("should be null"));
		Area *area = ob->GetArea();
		int indexFrom = MAP_INDEX(posFrom.x, posFrom.y);
		Astar::posTo = posTo;
		Astar::indexTo = MAP_INDEX(posTo.x, posTo.y);
		PathNode *startNode = NewNode(indexFrom, NULL, 0);
		AddOpenNode(startNode);

		while (true)
		{
			if (!openSet) break;
			PathNode *currentNode = PickCurrentNode();
			if (currentNode->position == posTo)
			{
				return ProvideResult(area, true, path);
			}
			CloseOpenNode(currentNode);
			int x = currentNode->position.x;
			int y = currentNode->position.y;
			if (currentNode->estimateFullPathLength <= lengthBound)
			{
				ProcessNeighbor(ob, area, currentNode, x + 1, y);
				ProcessNeighbor(ob, area, currentNode, x - 1, y);
				ProcessNeighbor(ob, area, currentNode, x, y + 1);
				ProcessNeighbor(ob, area, currentNode, x, y - 1);
				ProcessNeighbor(ob, area, currentNode, x + 1, y + 1);
				ProcessNeighbor(ob, area, currentNode, x + 1, y - 1);
				ProcessNeighbor(ob, area, currentNode, x - 1, y - 1);
				ProcessNeighbor(ob, area, currentNode, x - 1, y + 1);
			}
		}
		return ProvideResult(area, false, path);
	}

	static Surface *ProvideResult(Area *area, bool successful, StorageVector<int> *path)
	{
		Surface *result = NULL;
		if (successful) 
		{
			PathNode *currentNode = &allNodes[indexTo];
			while (currentNode)
			{
				if (path) path->Add(MAP_INDEX(currentNode->position.x, currentNode->position.y));
				PathNode *prevNode = currentNode->cameFrom;
				if (!prevNode->cameFrom)
				{
					result = area->GetCell(currentNode->position)->GetSurface();
					break;
				}
				currentNode = prevNode;
			}
		}
		CleanAfter();
		return result;
	}

};

PathNode Astar::allNodes[MAP_SIZE];
StorageVector<int> Astar::closedNodes;
PathNode *Astar::openSet = NULL;
Pos Astar::posTo = Pos(0, 0);
int Astar::indexTo = 0;



Ответить

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 29 гостей