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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.75
!Андрей!
6 / 6 / 0
Регистрация: 31.01.2012
Сообщений: 134
#1

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

05.11.2012, 16:29. Просмотров 2122. Ответов 19
Метки нет (Все метки)

Подскажите пожалуйста как реализовать правильно(и желательно быстро) потому что, нужно будет считать для 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;
    }
0
Миниатюры
Волновой алгоритм для двумерной матрицы  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2012, 16:29
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Волновой алгоритм для двумерной матрицы (C++):

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; void lab () { int s1 = 0; int s2 =...

Как написать волновой алгоритм для трехмерного лабиринта? - C++
Трехмерный лабиринт выглядит следующим образом На примере 3*3*3 Числа 0,1,2... секторы лабиринта -1 проходимые участки -2 стенки ...

Составить прогу для подсчета непарных элементов двумерной матрицы - C++
Динамический массив В розмера m×n из целых чисел. Составить прогу для подсчета непарных(??????) элементов двумерной матрицы В, используя...

Волновой алгоритм - C++
Доброго времени суток, дорогие форумчане. Никак не додумаю волновой алгоритм, помогите, кто чем может: файл - матрица целых чисел, где...

Волновой алгоритм - C++
Нужно найти кратчайший путь в лабиринте размерностью 10х10 , и выводить ответ. Помогите

Волновой алгоритм - C++
Нужно реализовать волновой алгоритм поиска кратчайшего пути на поле 20*20, причем координаты начала и конца вводятся пользователем,...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
05.11.2012, 16:31 #2
а что не так? Путь нашёлся!
0
!Андрей!
6 / 6 / 0
Регистрация: 31.01.2012
Сообщений: 134
05.11.2012, 16:33  [ТС] #3
Kuzia domovenok, ну он как-то странно нашелся. Я когда тестировал при ручном вводе - искался по другому путь. Он как правило состоял из прямых линий и поворотов только в нужных местах
0
!Андрей!
6 / 6 / 0
Регистрация: 31.01.2012
Сообщений: 134
05.11.2012, 16:39  [ТС] #4
Kuzia domovenok, вот пара примеров работы этого кода. Путь ищется крайне не адекватно, а иногда вообще не ищется
0
Миниатюры
Волновой алгоритм для двумерной матрицы   Волновой алгоритм для двумерной матрицы  
Croessmah
Эксперт CЭксперт С++
13203 / 7474 / 839
Регистрация: 27.09.2012
Сообщений: 18,372
Записей в блоге: 3
Завершенные тесты: 1
05.11.2012, 16:40 #5
Цитата Сообщение от !Андрей! Посмотреть сообщение
Kuzia domovenok, вот пара примеров работы этого кода. Путь ищется крайне не адекватно, а иногда вообще не ищется
Значит, Вы не правильно написали код.
0
!Андрей!
6 / 6 / 0
Регистрация: 31.01.2012
Сообщений: 134
05.11.2012, 16:46  [ТС] #6
Croessmah, логично) Я сюда и написал, потому что не могу найти ошибку и прошу помочь
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.11.2012, 16:57 #7
Цитата Сообщение от !Андрей! Посмотреть сообщение
Подскажите пожалуйста что не так? Вот код с++
У Вас не волновой алгоритм реализован, а поиск в глубину.

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

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

Добавлено через 1 минуту
Цитата Сообщение от !Андрей! Посмотреть сообщение
моете пожалуйста подсказать как реализовать поиск правильно?
посмотри вот это
http://ru.wikipedia.org/wiki/Волновой_алгоритм
http://algolist.manual.ru/maths/grap...tpath/wave.php
0
!Андрей!
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;
}
0
ValeryS
Модератор
6631 / 5039 / 466
Регистрация: 14.02.2011
Сообщений: 16,844
05.11.2012, 17:09 #11
Цитата Сообщение от !Андрей! Посмотреть сообщение
По хорошему мне это всё нужно для передвижения приведений из игры Pac Man. Может есть какие-то другие выходы приемлемые? Игра готова, а приведения как дауны двигаются)
насколько я помню они и двигались как дауны
искали не кратчайший путь а кратчайшее расстояние( плюс элемент случайности)
т.е если встал за стенкой то они прилипали к стенке с другой стороны
но периодически отходили а потом могли обратно вернутся
0
!Андрей!
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;
}*/
0
valeriikozlov
Эксперт C++
4670 / 2496 / 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.
1
!Андрей!
6 / 6 / 0
Регистрация: 31.01.2012
Сообщений: 134
05.11.2012, 17:27  [ТС] #14
valeriikozlov, спасибо. Чувствую не по мне это))

Добавлено через 1 минуту
valeriikozlov, а исходники думаете можно найти?
0
ValeryS
Модератор
6631 / 5039 / 466
Регистрация: 14.02.2011
Сообщений: 16,844
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/
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2012, 17:36
Привет! Вот еще темы с ответами:

Волновой алгоритм - C++
Здравствуйте, очень прошу помочь с реализацией волнового алгоритма только лишь с помощью матрицы весов неориентированного графа. Объясните...

Волновой алгоритм - C++
Подскажите пожалуйста, на сколько сложно изготовить из матрицы 0000 0000 0000 напр.4345 3234 2123 3234 Только при помощи обычных...

Лабиринт - волновой алгоритм - C++
Помогите пожалуйста. Я написал код, который мне выведет на экран кратчайший путь... Но чего-то не хватает.... Может создать цикл с...

Волновой алгоритм поиска пути - C++
Добрый день. Реализую всем известный алгоритм поиска кратчайшего пути. Но не могу понять одну вещь. Пройдя волновым методам по...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
05.11.2012, 17:36
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru