Comments 22
Когда я был студентом, у нас это была лабораторка на первом семестре второго курса, которую делал каждый студент, и почти все - успешно. А вы целую статью написали...
Диагональные ребра в граф не включать - это несколько ускорит работу алгоритма. Полученную ломаную линию сгладить при необходимости диагональными линиями.
Вместо MaxSlope использовать весовые коэффициенты, учитывающие не только расстояние, но и угол наклона.
У данного алгоритма есть недостаток. При нахождения пути на непрерывных пространствах алгоритм не дает оптимальный путь. Например, на изображении зеленый путь явно короче.
Необходимо учитывать все возможные траектории: https://en.wikipedia.org/wiki/Any-angle_path_planning
Занудства ради, утверждение, что "алгоритм Дейкстры при нахождении пути на непрерывных пространствах не даёт оптимальный путь" означает примерно то же, что и "топор плохо подходит для рисования акварелью". Алгоритм Дейкстры и непрерывные пространства находятся в разных областях математики и в разных, практически не пересекающихся, сферах задач.
А вот это уже — правильная реализация алгоритма Дейкстры. Спасибо, что исправили вашу статью.
Есть несколько предложений по коду:
GetAllAdjacentVertices можно сократить раз в 10, если завести константый массив на 8 позиций со сдвигами +-1 для координат соседей. Или просто пустить два цикла от -1 до 1.
Что-то вроде этого (я попытался в C#, но не гарантирую, что код ниже компилируется. Но идея должна быть понятна):
for(dx = -1; dx <= 1; ++dx) {
for (dy = -1; dy <= 1; ++dy) {
int nx = v.Coordinate.i + dx;
int ny = v.Coordinate.j + dy;
if ((dx == 0 && dy == 0) || nx < 0 || ny < 0 || nx == N || ny == M) continue;
list.Add(Vertices[nx, ny]);
}
}
return list;ConcurrentPriorityQueue вам не нужен, хватит и PriorityQueue, у вас же нет никакой многопоточности.
Я бы сказал, почти правильная реализация. Всё же условием останова следовало бы предпочесть вариант "целевая вершина достигнута И ни один кандидат в очереди не лучше уже найденного пути". Достаточно легко представить граф, где целевая вершина может быть сначала достигнута по менее оптимальному маршруту, чем это возможно, и этот маршрут нашёлся бы уже буквально на следующей итерации (хотя это и не обязательно, зависит от структуры графа), если бы мы опрометчиво не прервали поиск. Кажется, на графе, представленном обычной регулярной сеткой "без сюрпризов", такого случиться не должно, но в случае с графами произвольного вида или когда в игру вступают веса (как в данном случае: "регулярная сетка + высоты"), такие ситуации вполне возможны.
Да не, все правильно с остановом. isVisited выставляется, когда вершина вынимается из очереди, т.е. она является минимальной из пока не посещенных. В тот момент никаких более коротких путей в нее быть не может.
Да, действительно, моя ошибка. Видимо, перепутал с А* (мне в основном приходится с ним сталкиваться), там из-за эвристики такая ситуация возможна. А в Дейкстре, в силу его жадности, извлечение целевой вершины из очереди эквивалентно нахождению оптимального пути до неё.
Вы что-то путаете. Если евристика удовлетворяет необходимым в A* условиям, то даже с ней, если вершина выбирается из очереди, то до нее известен кратчайший путь.
Если же у вас могут кучу раз улучшаться одни и те же вершины, уже ранее рассмотренные, то это не A*, а форд-беллман или волновой алгоритм получается. И работает эта вся радость на порядок хуже дейкстры.
В моём случае строгая математичность A* (вернее, его требований к эвристике, на чём и основана гарантия его оптимальности), к сожалению, разбивается о суровую реальность.
Если мы оптимизируем не тот же параметр, в контексте которого можем точно посчитать эвристику (например, эвристику мы считаем как расстояние, а оптимизируем время проезда, и, значит, эвристическое расстояние также нужно перевести во время), наступает момент компромиссов между оптимистичностью эвристики и количеством перебираемых вершин, что напрямую влияет на производительность.
Под "точно посчитать эвристику" я имею ввиду "с минимальным возможным оптимизмом, но не хуже", т.е. так, чтобы не рассматривать ни одной лишней вершины, но рассмотреть все необходимые для гарантии оптимальности. То есть h(x) = 0 -- максимально оптимистичная эвристика, но с ней A* вырождается в Дейкстру и перебирает огромное количество "лишних" вершин, чего мы как раз пытаемся избежать.
Поэтому приходится как-то выкручиваться, чтобы и рыбку съесть, и в рамках накалываемых на время расчёта ограничений остаться.
Но это всё, конечно, не имеет отношения к чистому строго математическому A* или Дейкстре (и к данной статье в частности), это скорее уже сложности, вызванные особенностями предметной области. Моё профессиональное искажение подсунуло эти сложности туда, где их исходно нет)
Достаточно, чтобы эвристика не переоценивала реальную метрику (вермя у вас). Можете сначала оценить расстояние снизу и поделить на максимальную скорость передвижения, например. Если у вас эвристика переоценивает метрику, то вы можете не только больше вершин рассмотреть, чем надо — вы вообще можете эти вершины рассматривать очень много лишних раз. И тупая дейкстра будет быстрее. Но это, правда, для специфичных графов. Может, в вашем случае этот странный алгоритм действительно работает быстрее дейкстры. Хотя, я уверн, что подкрутив эвристику вы его еще ускорите.
Идея с оптимизацией поиска смежных вершин отличная. Добавил изменения в проект.
из возможного напрашивается только 1 ситуация, возможно в вершины графа кидать маску от террейна, тоесть выборку, есть карта уровня, и обозначение где точка может ходить, на этом уровне - пределы для точки - минимальный где она будет патрулировать, максимальный при пороге которого она вернется к патрулю, не по всему же террейну можно ходить, ходить можно по террейну либо по выбранным елементам, или по градиентам при условии, что стартовали с разрешенной точки, полёты не рассматриваются покачто)
Как обычно, ваши комментарии вообще не в тему, непонятно как связанны с тем, на что вы отвечаете, непонятно, что вообще хотели сказать.
а вы работали когда-нибудь с картой высот? не в контексте алгоритм и выполнение, а применяли хоть раз? высота в 3д еще есть не только 0 ++
запустите кароче свой алгоритм в 3д и карту расположите 0 пределы [-256,+256], а потом тоже самое ([-256,-256, -256] до [+256,-256, +256] - плоскость уровня)
флоат в С++ Приблизительно от 3.4e-38 до 3.4e+38 для x y z карта может быть в этих пределах
флоат в Сшарп Тип float может хранить числа в диапазоне от приблизительно ±1.5 × 10⁻⁴⁵ до ±3.4 × 10³⁸
соотв картинка[index]уровня будет где-то, и в том числе ниже 0, в том числе если уровень ниже 0, то картинка для пещеры будет значительно ниже уходить от уровня[index]
тоесть придётся еще делать штуки по локализации координат в индексы уровня, а потом 0 0 картинки перемещать в мировые координаты, и еще стабилизировать высоту по итогу - ту которая на выходе для обьекта
Скрытый текст
попробуйте, вон красная точка это кубик
по моей логике он должен выйти по 1 из градиентов из центра, вон возвышенность по обе стороны него градиенты
тоесть придётся такие действия делать, при расчете соседей, при выводе(корректировать учитывая сдвиг), задании начала и конца учитывать сдвиг
учитывать сдвиг по всем осям
так что маску от террейна можно кидать наверно всё таки
соотв сдвиг на террейне будет свой, можно либо в структуру выделить либо в класс
а что вы не поняли, у террейна есть обьем ограничивающий, у группы нпц есть обьем ограничивающий, как вы столкновения будете фиксировать с границами, чтобы точка вернулась обратно на патруль? там очень много вызовов sqrt будет, а так только ААББ везде сравнения(на моём пк вышло дешевле чем в блендере)
задача поиска пути реализовывается по сдвигу (кртинка->world pos)(world pos->картинка), и вся геометрия какая бы не была, для простоты фиксации в своих обьёмах как в кармашках, а тут пока sqrt можно оставить для расчета дистанции действительно нужная вещ вроде и работает
тогда вопрос если вы не поняли, есть пещера и есть мир, игрок зашел в пещеру, пещера в мире, игрок сагрил моба, и побежал из пещеры, как вы собираетесь вернуть моба обратно в пещеру, прям на его место респауна ?) эта задача уже сложнее тут предпологается world composition - но его же понятно как реализовать, я надеюсь
Скрытый текст
void createPathsMap(std::vector<float> &heightmap){
nodes.clear();
// Создание узлов
for (int z = 0; z < terrainSize; ++z) {
for (int x = 0; x < terrainSize; ++x) {
NodeP node;
node.x = x;
node.z = z;
node.height = getHeightAt(x-256,z-256)-239.0f;
nodes.push_back(node);
}
}
// Построение связей с 8 соседями
for (int z = 0; z < terrainSize; ++z) {
for (int x = 0; x < terrainSize; ++x) {
int index = z * terrainSize + x;
if (x > 0) nodes[index].neighbors.push_back(index - 1);
if (x < terrainSize - 1) nodes[index].neighbors.push_back(index + 1);
if (z > 0) nodes[index].neighbors.push_back(index - terrainSize);
if (z < terrainSize - 1) nodes[index].neighbors.push_back(index + terrainSize);
if (x > 0 && z > 0) nodes[index].neighbors.push_back(index - terrainSize - 1);
if (x > 0 && z < terrainSize - 1) nodes[index].neighbors.push_back(index + terrainSize - 1);
if (x < terrainSize - 1 && z > 0) nodes[index].neighbors.push_back(index - terrainSize + 1);
if (x < terrainSize - 1 && z < terrainSize - 1) nodes[index].neighbors.push_back(index + terrainSize + 1);
}
}
}
......
выделим 2 пути под 2 точки
int startX = 256, startZ = 256;
int goalX = 40, goalZ = 440;
int startIdx = startZ * terrainSize + startX;
int goalIdx = goalZ * terrainSize + goalX;
float totalPathCost = 0.0f;
std::vector<int> path = dijkstra(nodes, startIdx, goalIdx, totalPathCost);
int startX1 = 440, startZ1 = 40;
int goalX1 = 44, goalZ1 = 440;
int startIdx1 = startZ1 * terrainSize + startX1;
int goalIdx1 = goalZ1 * terrainSize + goalX1;
float totalPathCost1 = 0.0f;
std::vector<int> path1 = dijkstra(nodes, startIdx1, goalIdx1, totalPathCost1);
....
где-то до цикла создание делегатов
....
делегаты делают движение обьекта по выбранному пути из точки а в б
updateObject(obj,0.01f);
updateObject(obj1,0.01f);
фиксаторы
objects[0].position=glm::vec3(obj.position.x-256.0f,getHeightAt(obj.position.x-256.0f,obj.position.z-256.0f)-239.0f,obj.position.z-256.0f);
objects[1].position=glm::vec3(obj1.position.x-256.0f,getHeightAt(obj1.position.x-256.0f,obj1.position.z-256.0f)-239.0f,obj1.position.z-256.0f);обьекты находятся в локальном узле и ограничены статичными стенами этого узла или того узла в котором они находятся по иерархии, но суть не в этом, суть в том, что уровень может быть выше 0 ниже, левее, правее
testcolBB1.cpp вот можете глянуть если поймёте
может еще что-то можно посмотреть в Альфа-бета-отсечение
О том, как алгоритм Дейкстры реализовывал и некоторых его применениях