Войти
ПрограммированиеФорумИгровая логика и ИИ

Поиск пути наименьшей стоимости в двумерном массиве. C++.

#0
15:35, 10 сен. 2012

Довольно долго искал разные алгоритмы для этого, но в графах не разбираюсь и видимо неправильно ставлю условие задачи.
Решил спросить здесь.

У меня есть готовый отлично работающий волновой алгоритм в функции ниже,  который заполняет переменную путь. (могу весть код выложить)
static bool поиск_кратчайшего_пути_в_матрице(int старт_ряд, int старт_столбец, int ряд_куда, int столбец_куда , bool ** матрица_двумерная ,int рядов ,int столбцов , std::vector<pair<int, int>> & путь);

НО эта реализация алгоритма
1) не учитывает стоимость прохода. То есть клетка имеет значение либо 0 либо 1. Проход возможен или невозможен. А нужно чтобы какие то клетки были "быстрее" других. То есть на них как бы есть дорога.
2) Проход визуально нелогичный. здесь вот при проходе из 3-0 в 3-4 будет найден такой путь.(выделено жирным)
  00 01 02 03 04
  10 11 12 13 14
  20 21 22 23 24
  30 31 32 33 34
таким образом по идее движение по диагонали должно стоить немного дороже чем напрямую.


С разных сайтов скачивал алгоритмы Дейкстры и еще один Волновой .
Но там очень непонятно реализовано, а где то просто не работает.
1) В одной реализации волнового алгоритма, (http://algolist.manual.ru/games/wavealg.php) непонятно что подразумевается под стоимостью пути, там путь ищется если стоимость 2-2000 если большее 2000 то ищется другой путь.
2) Правильно ли искать Дейкстру и волновой для данной ситуации?
3) Есть ли где нибудь ГОТОВОЕ решение которое точно работает?


#1
17:08, 10 сен. 2012

1. Стоимость переходов задавай в клетке. тут собственно 2 простых варианта - итоговая стоимость берется как среднее между клетками назначения и источника или только значение клетки назначения. для диагоналей можно использовать модификатор, х1.4 например или х3 для диагоналей х2 для ортогональных.
дейкстру обычно упрощают если не учитываются вес перехода. общий алгоритм выглядит так:
есть два списка - 1й помеченные клетки для которых уже есть путь, 2й - перспективные клетки - до которых можно добраться 1м шагом.
в начале в первом списке клетка старта, во втором её соседи.
1. выбираем из 2-го списка клетку с наименьшей стоимостью пути к ней.
2. если это клетка финиша - закончили, раскручиваем путь
3. добавляем её в первый список сохраняя информацию о длине пути к ней и клетке из которой выполняется переход.
4. проверяем соседей, если они в первом списке - пропускаем, если во втором - проверяем длину пути, если меньше корректируем. если нет в списках - добавляем
5. если перспективных клеток нет - пути нет
6. к шагу 1.
ПРИМЕЧАНИЕ: собственно упрощение заключается в том, что на первом шаге все перспективные клетки имеют наименьшую стоимость пути и их все добавляют в пройденные получая волновой алгоритм

2. Стены
тут 2 варианта
а) непроходимые клетки - задаешь им стоимость -1 или 0, на 4м шаге их не добавляем в перспективные
б) стены между клетками - нужен хранить отдельно информацию об этих стенах, в остальном как в пункте а)

#2
18:03, 10 сен. 2012

Нашел почти готовый алгоритм здесь
http://scr1pter.blogspot.com/2011/05/blog-post_13.html
Имеет классы
CWayMap::CWayMap() - карта
CPathfinding::CPathfinding() - поиск

Работает правильно. Хотя наверное очень медленно.
Там нужно несколько моментов добавить чтобы можно было работать по координатам:
Сделал на скорую руку.

// матрица[][] где <=0  клетка не проходима  ,  >= клетка проходима и сколько стоит.
int ** матрица;


// Вот в этой строке в конце добавляем
Chunk.G = iDiag*WeightDiag + iDirect*WeightLine + m_aOpenList[iChunkNum].G + WayMap->m_Grid[ Chunk.ID].стоимость;


Изменить конструктор

CWayMap::CWayMap(int iWidth, int iHeight, int ** матрица , int iSize)
{
   // запоминаем размер ячейки
   m_iChunkSize = iSize;
   // вычисляем кол-во ячеек в ширину
   m_iGridWidth = iWidth/iSize;
   // вычисляем кол-во ячеек в высоту
   m_iGridHeight = iHeight/iSize;
 
   m_Grid = NULL;
   // создаем нашу сетку с нужным кол-ом ячеек
   m_Grid = new CMapChunk[m_iGridWidth*m_iGridHeight];
   // проходимся по всем ячейкам и выставляем им одну зону
  
int счётчик_ряда=0;
int счётчик_столбца=-1;
for (int x = 0; x < m_iGridWidth*m_iGridHeight; x++)
{
счётчик_столбца++;
if(счётчик_столбца >= iHeight){if(счётчик_ряда >= iWidth){счётчик_ряда=0;}счётчик_ряда++; счётчик_столбца=0;}

m_Grid[x].ряд = счётчик_ряда;
m_Grid[x].столбец = счётчик_столбца;
m_Grid[x].Passability = NO_INIT;

int проходимость = NO_INIT;
if(матрица[счётчик_ряда][счётчик_столбца] <= 0){проходимость=0;}
m_Grid[x].Passability = проходимость;
m_Grid[x].стоимость = матрица[счётчик_ряда][счётчик_столбца];
}

   // у нас пока 0 зон, указываем это
   int m_iCountZone = 0;
   // делим нашу сетку на зоны, если они есть
   SplitZones(NO_INIT);
}

И структуру

struct CMapChunk
{
// проходимость
int Passability; // 0 непроходима

int стоимость;
int ряд;
int столбец;
};


Работает это так

CPathfinding карта(рядов,столбцов , матрица , 1);

MapPoint точка_старта;
точка_старта.x = 0;
точка_старта.z = 0;


MapPoint точка_финиша;
точка_финиша.x = 3;
точка_финиша.z = 3;

std::vector<MapPoint> путь;
карта.GetWay(точка_старта,точка_финиша , &путь);


if(!путь.empty())
{
for(int i = 0; i <= путь.size()-1; i++)
{
std::cout << "\n\nряд=" << путь[i].z;
std::cout << "\nстолбец=" << путь[i].x;
}
}
else{std::cout << "\nпуть не найден=";}

#3
18:08, 10 сен. 2012

Как просто модифицироть просто твою прогу:
1) измени тип карты с логического на вещественный
2) при движении по диагонали умножай вес на корень из двух
3) собственно измени все веса согласно желаниям :)

#4
0:14, 13 ноя. 2012

Здравствуйте, manking.
Могу прислать готовый алгоритм(+добавлена passability местности), либо выложить здесь его код в течение 2-х дней, если вопрос ещё актуален.

Т.е. да, у меня есть готовое решение.
Время работы, правда :( 0,5 с для карты 140x140 клеточек.

#5
3:29, 13 ноя. 2012

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

ПрограммированиеФорумИгровая логика и ИИ

Тема в архиве.