Форум программистов, компьютерный форум CyberForum.ru

Волновой алгоритм для двумерной матрицы - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.75
!Андрей!
6 / 6 / 0
Регистрация: 31.01.2012
Сообщений: 134
05.11.2012, 16:29     Волновой алгоритм для двумерной матрицы #1
Подскажите пожалуйста как реализовать правильно(и желательно быстро) потому что, нужно будет считать для 4х объектов. Вот код который я имею:

До вызова этой функции в матрице задается 'G' и 'S', S старт, G - Финиш, так же до вызова этой функции происходит считывание стенок (#).

По этому коду путь считается вот так(смотрите вложение)
Подскажите пожалуйста что не так? Вот код с++
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
    int find_path(int enPosY,int enPosX)
    {
        if (wayToPacMan[enPosX][enPosY] == 'G' ) return 1;
        if (wayToPacMan[enPosX][enPosY] != ' ' && wayToPacMan[enPosX][enPosY] != 'S' ) return 0;
 
        wayToPacMan[enPosX][enPosY] = '+';
        if ( find_path(enPosX, enPosY - 1) == 1 ) return 1;
        if ( find_path(enPosX + 1, enPosY) == 1 ) return 1;
        if ( find_path(enPosX, enPosY + 1) == 1 ) return 1;
        if ( find_path(enPosX - 1, enPosY) == 1 ) return 1;
        wayToPacMan[enPosX][enPosY] = '_';
        return 0;
    }
Миниатюры
Волновой алгоритм для двумерной матрицы  
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
05.11.2012, 16:31     Волновой алгоритм для двумерной матрицы #2
а что не так? Путь нашёлся!
!Андрей!
6 / 6 / 0
Регистрация: 31.01.2012
Сообщений: 134
05.11.2012, 16:33  [ТС]     Волновой алгоритм для двумерной матрицы #3
Kuzia domovenok, ну он как-то странно нашелся. Я когда тестировал при ручном вводе - искался по другому путь. Он как правило состоял из прямых линий и поворотов только в нужных местах
!Андрей!
6 / 6 / 0
Регистрация: 31.01.2012
Сообщений: 134
05.11.2012, 16:39  [ТС]     Волновой алгоритм для двумерной матрицы #4
Kuzia domovenok, вот пара примеров работы этого кода. Путь ищется крайне не адекватно, а иногда вообще не ищется
Миниатюры
Волновой алгоритм для двумерной матрицы   Волновой алгоритм для двумерной матрицы  
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,919
Записей в блоге: 2
Завершенные тесты: 1
05.11.2012, 16:40     Волновой алгоритм для двумерной матрицы #5
Цитата Сообщение от !Андрей! Посмотреть сообщение
Kuzia domovenok, вот пара примеров работы этого кода. Путь ищется крайне не адекватно, а иногда вообще не ищется
Значит, Вы не правильно написали код.
!Андрей!
6 / 6 / 0
Регистрация: 31.01.2012
Сообщений: 134
05.11.2012, 16:46  [ТС]     Волновой алгоритм для двумерной матрицы #6
Croessmah, логично) Я сюда и написал, потому что не могу найти ошибку и прошу помочь
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.11.2012, 16:57     Волновой алгоритм для двумерной матрицы #7
Цитата Сообщение от !Андрей! Посмотреть сообщение
Подскажите пожалуйста что не так? Вот код с++
У Вас не волновой алгоритм реализован, а поиск в глубину.

Цитата Сообщение от !Андрей! Посмотреть сообщение
Путь ищется крайне не адекватно, а иногда вообще не ищется
ищется всегда, но иногда очень долго будете ждать и чаще всего это будет не самый короткий путь.
!Андрей!
6 / 6 / 0
Регистрация: 31.01.2012
Сообщений: 134
05.11.2012, 17:03  [ТС]     Волновой алгоритм для двумерной матрицы #8
valeriikozlov, а моете пожалуйста подсказать как реализовать поиск правильно? Ступор вызвала просто эта задача.

По хорошему мне это всё нужно для передвижения приведений из игры Pac Man. Может есть какие-то другие выходы приемлемые? Игра готова, а приведения как дауны двигаются)
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
05.11.2012, 17:05     Волновой алгоритм для двумерной матрицы #9
Цитата Сообщение от valeriikozlov Посмотреть сообщение
ищется всегда, но иногда очень долго будете ждать и чаще всего это будет не самый короткий путь.
волновик как раз и рассчитан для поиска кратчайшего пути

Добавлено через 1 минуту
Цитата Сообщение от !Андрей! Посмотреть сообщение
моете пожалуйста подсказать как реализовать поиск правильно?
посмотри вот это
http://ru.wikipedia.org/wiki/Волновой_алгоритм
http://algolist.manual.ru/maths/grap...tpath/wave.php
!Андрей!
6 / 6 / 0
Регистрация: 31.01.2012
Сообщений: 134
05.11.2012, 17:07  [ТС]     Волновой алгоритм для двумерной матрицы #10
ValeryS, так и что мне в итоге подскажите делать?)

Добавлено через 19 секунд
ValeryS, спасибо(ответил просто не обновляя страницу)

Добавлено через 1 минуту
Как то давно писал волновой алгоритм:
Но мне кажется что это больно долго будет работать


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
void waveAlgorithm(int fromNode, int toNode ){
int **fronts; 
int i, j, k, step;
int *alreadyMarked; 
bool find;
 
fronts = new int*[razmer]; 
for ( i = 0; i < razmer; i++ )
fronts[i] = new int[razmer];
 
way = new int[razmer];
alreadyMarked = new int[razmer];
 
for ( i = 0; i < razmer; i ++ )
for ( j = 0; j < razmer; j ++ ) 
fronts[i][j] = -1;
for ( i = 0; i < razmer; i ++ )
alreadyMarked[i] = 0;
for ( i = 0; i <= razmer; i ++ )
way[i] = -1;
 
fronts[0][0] = fromNode;
step = 0; find = false; 
 
while ( step < razmer && !find ){
i = 0;
k = 0;
if ( fronts[step][0] == -1 ) break;
 
while ( fronts[step][i] > -1 ) { 
for ( j = 0; j < razmer; j++ ) {
if ( matr[fronts[step][i]][j] > 0 && alreadyMarked[j] == 0 ) { 
alreadyMarked[j] = 1;
fronts[step+1][k] = j;
k++;
}
}
i++;
}
 
i = 0; 
while ( fronts[step + 1][i] > -1 ) {
if ( fronts[step + 1][i] == toNode ) { 
find = true;
break;
}
i++;
}
step++;
}
 
if ( find ) { 
way[step] = toNode;
for ( i = step-1; i >= 0; i-- ) {
for ( k = 0; k < razmer; k ++ ){
if ( matr[fronts[i][k]][way[i+1]] > 0 ) {
way[i] = fronts[i][k];
break;
}
}
}
}
cout«"put' ot "«fromNode+1«" do "«toNode+1«": ";
if ( way[0] == -1 ) 
cout « "ne sushestvuet";
else {
i = 0;
while ( way[i] != -1 && i <= razmer ){
if ( i != 0 ) cout « " -> ";
cout « way[i] + 1;
i++;
}
}
return;
}
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
05.11.2012, 17:09     Волновой алгоритм для двумерной матрицы #11
Цитата Сообщение от !Андрей! Посмотреть сообщение
По хорошему мне это всё нужно для передвижения приведений из игры Pac Man. Может есть какие-то другие выходы приемлемые? Игра готова, а приведения как дауны двигаются)
насколько я помню они и двигались как дауны
искали не кратчайший путь а кратчайшее расстояние( плюс элемент случайности)
т.е если встал за стенкой то они прилипали к стенке с другой стороны
но периодически отходили а потом могли обратно вернутся
!Андрей!
6 / 6 / 0
Регистрация: 31.01.2012
Сообщений: 134
05.11.2012, 17:12  [ТС]     Волновой алгоритм для двумерной матрицы #12
ValeryS, у меня так и есть, я читал целую статью на хабре, и двигались они далеко не как дауны) У каждого приведения - свой алгоритм был передвижения. Вот просто если по моему коду передвижения, они застревают в углах. Map - карта(матрица указателей на объекты)

C++
1
2
3
4
5
6
7
8
/*void Enemy::move(Map* map, Puckman* Puckman, Enemy* en)
{
    if(Puckman -> posY < posY && map -> map[en -> posY - 1][en -> posX] -> iCanEatThat && (direction!='s')) {en -> posY--;direction = 'w';}
    else if(Puckman -> posX < posX && map -> map[en -> posY][en -> posX-1] -> iCanEatThat && (direction!='d')) {en -> posX--;direction = 'a';}
    else if(map -> map[en -> posY+1][en -> posX] -> iCanEatThat && (direction!='w')) {en -> posY++;direction = 's';}
    else if(map -> map[en -> posY][en -> posX + 1] -> iCanEatThat && (direction!='s')) {en -> posX++; direction = 'd';}
    return;
}*/
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.11.2012, 17:20     Волновой алгоритм для двумерной матрицы #13
Цитата Сообщение от !Андрей! Посмотреть сообщение
а моете пожалуйста подсказать как реализовать поиск правильно?
Пока напишу сам волновой алгоритм. Допустим дана матрица (карта):
#######
#_____#
#_G___#
#____S#
#######
Создаете такую же размерами типа int (все элементы равны 0):
0000000
0000000
0000000
0000000
0000000
Далее все изменения будут только в этой матрице.
Элементу который соответствует G ставите 1. И заносите его в очередь. Т.е. в очереди изначально будет элемент с координатами (2,2) (индексация элементов с нуля).
Теперь пока очередь не опустеет (или можно делать пока элемент матрицы соответствующий S во втором массиве равен 0) делаете так:
Берете очередной элемент из очереди. Если сверху элемент равен 0 и в первом массиве элемент с этими координатами не равен #, то заносите в очередь элемент сверху, во втором массиве ставите ему значение на 1 больше чем значение только что взятого элемента из очереди. Тоже самое для элементов слева, справа, снизу.
В общем если рассматривать волны, то второй массив будет меняться так:
1 волна.
0000000
0000000
0010000
0000000
0000000
2 волна.
0000000
0020000
0212000
0020000
0000000
3 волна.
0000000
0323000
0212300
0323000
0000000
4 волна.
0000000
0323400
0212340
0323400
0000000
5 волна.
0000000
0323450
0212340
0323450
0000000
здесь останавливаемся, т.к. элемент где стоит S уже не равен 0. Сам путь теперь вычисляем так. Берем значение во втором массиве где стоит S. Это значение 5.
Пока это значение не станет равнным 1, делаем так:
Ищем из всех рядом стоящих значений значение на 1 меньше и переходим туда (можно помечать путь в первом масиве), уменьшая наше значение на 1.
!Андрей!
6 / 6 / 0
Регистрация: 31.01.2012
Сообщений: 134
05.11.2012, 17:27  [ТС]     Волновой алгоритм для двумерной матрицы #14
valeriikozlov, спасибо. Чувствую не по мне это))

Добавлено через 1 минуту
valeriikozlov, а исходники думаете можно найти?
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
05.11.2012, 17:36     Волновой алгоритм для двумерной матрицы #15
Цитата Сообщение от !Андрей! Посмотреть сообщение
valeriikozlov, а исходники думаете можно найти?
http://www.youtube.com/watch?v=JFlSW3LQhFk
http://tehtv.ru/RANUX/urok-41-c-voln...m-pathfinding/
http://gamesmaker.ru/programming/alg...ska-puti-na-c/
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.11.2012, 18:02     Волновой алгоритм для двумерной матрицы #16
Цитата Сообщение от !Андрей! Посмотреть сообщение
valeriikozlov, спасибо. Чувствую не по мне это))
напишите максимально возможные размеры массива wayToPacMan[][] и я что-нибудь напишу.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,919
Записей в блоге: 2
Завершенные тесты: 1
05.11.2012, 18:07     Волновой алгоритм для двумерной матрицы #17
Цитата Сообщение от !Андрей! Посмотреть сообщение
valeriikozlov, спасибо. Чувствую не по мне это))
Когда самостоятельно изучал волновой алгоритм - тоже так подумал, но потом нашел в интернете пошаговое описание действий и алгоритм то оказался легким =)
!Андрей!
6 / 6 / 0
Регистрация: 31.01.2012
Сообщений: 134
05.11.2012, 20:20  [ТС]     Волновой алгоритм для двумерной матрицы #18
valeriikozlov, они определяются переменными iSize, jSize в классе другом. Можете писать любой размер, т.к. он считывается самостоятельно

Добавлено через 13 минут
valeriikozlov, ну а по логике больше 50x50 точно не зайдёт, ибо на экран тупо не влезет
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.11.2012, 20:41     Волновой алгоритм для двумерной матрицы #19
Вот функция:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
void find_path(int N,int M)
{
    struct t{
        int x, y;
    };
    t Q[10000], S, G;
    int i_st=0, i_end=1, t, i, j, a[100][100]={0};
    for(i=0; i<N; i++)
        for(j=0; j<M; j++)
        {
            if(wayToPacMan[i][j]=='G') {G.x=i; G.y=j;}
            if(wayToPacMan[i][j]=='S') {S.x=i; S.y=j;}
        }
    a[G.x][G.y]=1;
    Q[0].x=G.x; Q[0].y=G.y;
    while(i_st<i_end)
    {
        if(a[Q[i_st].x-1][Q[i_st].y]==0 && wayToPacMan[Q[i_st].x-1][Q[i_st].y]!='#')
        {
            Q[i_end].x=Q[i_st].x-1; Q[i_end++].y=Q[i_st].y;
            a[Q[i_st].x-1][Q[i_st].y]=a[Q[i_st].x][Q[i_st].y]+1;
        }
        if(a[Q[i_st].x+1][Q[i_st].y]==0 && wayToPacMan[Q[i_st].x+1][Q[i_st].y]!='#')
        {
            Q[i_end].x=Q[i_st].x+1; Q[i_end++].y=Q[i_st].y;
            a[Q[i_st].x+1][Q[i_st].y]=a[Q[i_st].x][Q[i_st].y]+1;
        }
        if(a[Q[i_st].x][Q[i_st].y-1]==0 && wayToPacMan[Q[i_st].x][Q[i_st].y-1]!='#')
        {
            Q[i_end].x=Q[i_st].x; Q[i_end++].y=Q[i_st].y-1;
            a[Q[i_st].x][Q[i_st].y-1]=a[Q[i_st].x][Q[i_st].y]+1;
        }
        if(a[Q[i_st].x][Q[i_st].y+1]==0 && wayToPacMan[Q[i_st].x][Q[i_st].y+1]!='#')
        {
            Q[i_end].x=Q[i_st].x; Q[i_end++].y=Q[i_st].y+1;
            a[Q[i_st].x][Q[i_st].y+1]=a[Q[i_st].x][Q[i_st].y]+1;
        }
        i_st++;
    }
    if(a[S.x][S.y]==0)
        cout<<"No way"<<endl;
    else
    {
        t=a[S.x][S.y];
        while(t>1)
        {
            if(a[S.x-1][S.y]==t-1)
            {
                wayToPacMan[S.x-1][S.y]='+';
                S.x--; t--;
            }
            else
            if(a[S.x+1][S.y]==t-1)
            {
                wayToPacMan[S.x+1][S.y]='+';
                S.x++; t--;
            }
            else
            if(a[S.x][S.y-1]==t-1)
            {
                wayToPacMan[S.x][S.y-1]='+';
                S.y--; t--;
            }
            else
            if(a[S.x][S.y+1]==t-1)
            {
                wayToPacMan[S.x][S.y+1]='+';
                S.y++; t--;
            }
        }
    }
}
Работает при размере карты каждая сторона не более 100. Ничего не возвращает. Выводит сообщение No way если пути нет или заполняет '+' один из самых коротких путей от S до G в массиве wayToPacMan[][]. При вызове этой функции в параметрах нужно передать количество строк и столбцов карты (массива wayToPacMan[][]), включая границы.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2012, 21:50     Волновой алгоритм для двумерной матрицы
Еще ссылки по теме:

Волновой алгоритм C++
C++ Волновой алгоритм
C++ Лабиринт - волновой алгоритм

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
!Андрей!
6 / 6 / 0
Регистрация: 31.01.2012
Сообщений: 134
05.11.2012, 21:50  [ТС]     Волновой алгоритм для двумерной матрицы #20
valeriikozlov, Спасибо большое! буду разбираться с вашим кодом

Добавлено через 52 минуты
valeriikozlov, Спасибо большое! Смог в прогу запихнуть, пока что всё работает отлично!) Половина курсача уже ваша)
Yandex
Объявления
05.11.2012, 21:50     Волновой алгоритм для двумерной матрицы
Ответ Создать тему
Опции темы

Текущее время: 04:58. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru