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

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

Войти
Регистрация
Восстановить пароль
 
Xtir
12 / 12 / 0
Регистрация: 10.07.2010
Сообщений: 130
#1

Волновой алгоритм, неправильная работа при втором запуске - C++

03.11.2010, 01:53. Просмотров 798. Ответов 0
Метки нет (Все метки)

Вероятно многие из вас видели видео по волновому алгоритму. Так вот, я завёл этот код в функцию, и у меня появилась такая проблема, что если эту функцию вызвать второй раз, то линия рисуется совсем не так как хотелось бы...

вот сама функция:
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
bool CGame::addWaypoint(int x1, int y1, int x2, int y2)
{
    wp = 1;
 
    if(map[x1][y1] == WALL || map[x2][y2] == WALL)
    {
        Show();
        MessageBox(0,"wall","wall",MB_OK | MB_SYSTEMMODAL);
        return false;
    }
 
    vector<pair<int, int> > oldWave;
 
    oldWave.push_back(pair<int,int>(x1,y1));    //start point
    int nstep = 0;
    map[x1][y1] = nstep;                        //start point
    const int dx[] = {0,1,0,-1};
    const int dy[] = {-1,0,1,0};
 
    while(oldWave.size() > 0)
    {
        ++nstep;
        wave.clear();
        for(vector<pair<int,int> >::iterator i = oldWave.begin(); i != oldWave.end(); ++i)
        {
            for(int d = 0; d < 4; ++d)
            {
                int nx = i -> first + dx[d];
                int ny = i -> second + dy[d];
                if(map[nx][ny] == -1)
                {
                    wave.push_back(pair<int,int>(nx,ny));
                    map[nx][ny] = nstep;
                    if(nx == x2 && ny == y2) //end point
                        goto done;
                }
            }
        }
        oldWave = wave;
    }
done:;
    int x = x2; //end point
    int y = y2; //end point
    wave.clear();
    wave.push_back(pair<int, int>(x,y));
    while(map[x][y] != 0)
    {
        for(int d = 0; d < 4; ++d)
        {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if(map[x][y] - 1 == map[nx][ny])
            {
                x = nx;
                y = ny;
                wave.push_back(pair<int, int>(x,y));
                break;
            }
        }
    }
    return true;
}
и вот, если эту функцию вызвать 2 раза подряд

addWaypoint(1,1,N-2,N-2); //(левый,верхний,правый,нижний)
addWaypoint(1,58,58,1); //(левый,нижний,правый,верхний)

если сделать вот таким вот способом, то линия рисуется от левого верхнего к правому верхнему углу(), хотя последняя функция должна направить её от правого нижнего к левому верхнему.
Пробовал между ними ставить wave.erase(), однако безуспешно, вот думаю где что нужно подкрутить. Думаю что проблема кроется где-то в массиве, вот прошу помощи. а то всё перепробовал, уже не знаю что и делать...

Добавлено через 2 часа 20 минут
вроде разобрался, в массив записывались числа, которые в дальнейшем мешали новому построению пути
map[nx][ny] = nstep;
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2010, 01:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Волновой алгоритм, неправильная работа при втором запуске (C++):

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

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

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

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

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

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

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.11.2010, 01:53
Привет! Вот еще темы с ответами:

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

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

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

Tiled Map и волновой алгоритм - C++
Делаю игру пакман. Нашла, что для привидений хорошо подходит волновой алгоритм. Нашла примеры реализации -все они завязаны на двумерных...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

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