Почему мой алгоритм поиска пути по путевым точкам не работает?

Я написал следующие две функции, чтобы найти путь от одной путевой точки к другой, однако я получаю ошибку сегментации, я предполагаю, что она зацикливается бесконечно, но я не понимаю, почему, поскольку она должна остановиться, когда найдена путевая точка назначения.

std::vector<waypoint> Area::getPath(waypoint currentWP, waypoint destWP)
{
if(currentWP == destWP)
return returnPath;

for(unsigned int i=0; i<currentWP.links.size(); i++)
{
if(checkDest(*currentWP.links[i], destWP))
{
returnPath.push_back(*currentWP.links[i]);
getPath(*currentWP.links[i], destWP);
}
}
return returnPath;
}

bool Area::checkDest(waypoint currentWP, waypoint destWP)
{
if(currentWP == destWP)
return true;

for(unsigned int i=0; i<currentWP.links.size(); i++)
{

if(checkDest(*currentWP.links[i], destWP))
return true;
}
return false;
}

Путевая точка — это структура с членами x, y и массивом ссылок (типа * waypoint), которые определяют, куда вы можете идти от путевой точки.

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

Может кто-нибудь сказать мне, если этот алгоритм совершенно бесполезен, и если да, то предложить лучший способ сделать это, или я просто сделал небольшую вещь неправильно.

Заранее большое спасибо.

#0  0x00007ffff6bd29a5 in _int_malloc () from /usr/lib/libc.so.6
#1  0x00007ffff6bd4c50 in malloc () from /usr/lib/libc.so.6
#2  0x00007ffff747c35d in operator new(unsigned long) () from /usr/lib/libstdc++.so.6
#3  0x000000000040579a in __gnu_cxx::new_allocator<waypoint*>::allocate     (this=0x7fffff7ff1e0, __n=1) at /usr/include/c++/4.8.2/ext/new_allocator.h:104
#4  0x00000000004052cf in std::_Vector_base<waypoint*, std::allocator<waypoint*>     >::_M_allocate (this=0x7fffff7ff1e0, __n=1) at /usr/include/c++/4.8.2/bits/stl_vector.h:168
#5  0x0000000000404b1b in std::_Vector_base<waypoint*, std::allocator<waypoint*> >::_M_create_storage (this=0x7fffff7ff1e0, __n=1) at /usr/include/c++/4.8.2/bits/stl_vector.h:181
#6  0x0000000000403ccf in std::_Vector_base<waypoint*, std::allocator<waypoint*> >::_Vector_base (this=0x7fffff7ff1e0, __n=1, __a=...) at /usr/include/c++/4.8.2/bits/stl_vector.h:136
#7  0x0000000000402c33 in std::vector<waypoint*, std::allocator<waypoint*> >::vector (this=0x7fffff7ff1e0, __x=std::vector of length 1, capacity 1 = {...}) at /usr/include/c++/4.8.2/bits/stl_vector.h:312
#8  0x0000000000402771 in waypoint::waypoint (this=0x7fffff7ff1d0) at Waypoint.h:6
#9  0x0000000000409c3e in Area::checkDest (this=0x6ba3b0, currentWP=..., destWP=...) at Area.cpp:166
#10 0x0000000000409cdd in Area::checkDest (this=0x6ba3b0, currentWP=..., destWP=...) at Area.cpp:172
#11 0x0000000000409cdd in Area::checkDest (this=0x6ba3b0, currentWP=..., destWP=...) at Area.cpp:172

0

Решение

Похоже, вы взрываетесь в конструкторе, который вызывает malloc (). Что может быть связано с циклом в узлах вашего графа. Это приведет к бесконечной рекурсии, и вам не хватит памяти.

С этим типом алгоритма навигации по графику вы должны убедиться, что вы НЕ повторно посещаете один и тот же узел. Это лучше всего сделать, добавив хеш-таблицу посещенных узлов и проверив наличие дубликатов.
запись.

Поместите блоки try / catch вокруг обнаружения дубликатов, чтобы при посещении узла, который вы посетили, прежде чем вы смогли распечатать узлы и определить топологию графа.

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]