Алгоритм поиска пути в больших подземельях.
Модераторы: Sanja, Максим Кич
Алгоритм поиска пути в больших подземельях.
Интересует алгоритм поиска пути для больших подземелий. Подземелья достаточно сложные, с тупиками и большие, карта сейчас 128х80.
Волновой алгоритм - работает медленно, если искать из конца в конец лабиринта - более 15 тыс итераций цикла для проверки клеток, помечена на или нет. Соответственно по времени занимает до 100 мс. В среднем 30 мс, правда на слабом процессоре.
Вот думаю, может хранить отдельно комнаты и пути между ними? Тогда количество вершин графа, через которые надо будет найти путь, сокращается на несколько порядков, да и есть готовые оптимизированные алгоритмы для этих целей.
Волновой алгоритм - работает медленно, если искать из конца в конец лабиринта - более 15 тыс итераций цикла для проверки клеток, помечена на или нет. Соответственно по времени занимает до 100 мс. В среднем 30 мс, правда на слабом процессоре.
Вот думаю, может хранить отдельно комнаты и пути между ними? Тогда количество вершин графа, через которые надо будет найти путь, сокращается на несколько порядков, да и есть готовые оптимизированные алгоритмы для этих целей.
Re: Алгоритм поиска пути в больших подземельях.
Я другого алгоритма не знаю, но вопрос - а зачем обрабатывать всю карту? Это для монстров которые точно знают куда и как идти? Я у себя ограничивал зону поиска не очень большим квадратом и было достаточно. Но, наверное, у тебя что-то другое.altmax писал(а): ↑24 мар 2017, 11:18Интересует алгоритм поиска пути для больших подземелий. Подземелья достаточно сложные, с тупиками и большие, карта сейчас 128х80.
Волновой алгоритм - работает медленно, если искать из конца в конец лабиринта - более 15 тыс итераций цикла для проверки клеток, помечена на или нет. Соответственно по времени занимает до 100 мс. В среднем 30 мс, правда на слабом процессоре.
Вот думаю, может хранить отдельно комнаты и пути между ними? Тогда количество вершин графа, через которые надо будет найти путь, сокращается на несколько порядков, да и есть готовые оптимизированные алгоритмы для этих целей.
Re: Алгоритм поиска пути в больших подземельях.
Это пока абстрактный алгоритм, просто он есть в моей игре. Куда применить - пока не придумал, но вдруг пригодится ))) А так да - искать через всю карту вряд ли придется, может правда будет какой-нибудь монстр, который чувствует, где находится игрок.
Re: Алгоритм поиска пути в больших подземельях.
Если у тебя нет клеток с разной стоимостью проходимости, то есть jump point search - оптимизация A* для клеточной карты без весов. Прям на порядок шустрее.
Re: Алгоритм поиска пути в больших подземельях.
А нормального описания алгоритма не найдется? Чтобы не только русскими словами, но и на русском языке. А то на хабре какой-то странный перевод, слова вроде знакомые, но смысла не улавливаю.
Re: Алгоритм поиска пути в больших подземельях.
Про А* просто и доходчиво тут есть, правда без оптимизации.
поперёк борозды
- Jolly Roger
- Сообщения: 2973
- Зарегистрирован: 27 ноя 2009, 09:10
- Откуда: Minsk, Belarus
Re: Алгоритм поиска пути в больших подземельях.
Пять копеек.
Для адекватной работы важно не сколько найти путь, сколько понять, что пора прекратить искать. Имхо, для большинства случаев проще ограничивать временем в мс.
Для адекватной работы важно не сколько найти путь, сколько понять, что пора прекратить искать. Имхо, для большинства случаев проще ограничивать временем в мс.
Писать диздок спустя несколько лет разработки и множества изменений концепции - исконная русская девелоперская традиция.
Re: Алгоритм поиска пути в больших подземельях.
Как интересно в Dwarf Fortress ищут путь? Там же это приходится делать постоянно для нескольких сотен гномов и мобов. И мир там реально очень больших размеров.
- Jesus05
- Сообщения: 1840
- Зарегистрирован: 02 дек 2009, 07:50
- Откуда: Норильск, сейчас Санкт-петербург.
- Контактная информация:
Re: Алгоритм поиска пути в больших подземельях.
Пишут что там A*
Re: Алгоритм поиска пути в больших подземельях.
В Kobold Quest, насколько я помню, в исходнике пометка что поиск пути из DF взят. Ну, выглядит как A* без изысков и оптимизаций - даже бинарной кучи нет.
-
- Сообщения: 68
- Зарегистрирован: 10 май 2013, 16:30
Re: Алгоритм поиска пути в больших подземельях.
А что за бинарная куча?
Re: Алгоритм поиска пути в больших подземельях.
Меня только сейчас посетила мысль, как ускорить волновой алгоритм. Можно при генерации карты в каждую её клетку записывать сразу и её соседей, а не вычислять их каждый раз при запуске алгоритма. Реально должно ускориться раза в 3-4. Вроде очевидная вещь, а сразу и не дошло...
Re: Алгоритм поиска пути в больших подземельях.
Все же пересчитывать придется, т.к. есть монстры, они двигаются и блокируют путь друг у друга
Re: Алгоритм поиска пути в больших подземельях.
У меня такая реализация 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 гостей