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

Поиск пути в лабиринте - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 47, средняя оценка - 4.89
xproger
0 / 0 / 0
Регистрация: 10.01.2010
Сообщений: 16
14.05.2010, 14:29     Поиск пути в лабиринте #1
Есть двухмерный массив [22][17]: 1 - препятствие, 0 - проход.
Нужно найти кратчайший путь от одной точки до другой. У меня есть волновой алгоритм, он всё прекрасно находит ,но он не ищет пути по диагонали, а мне это нужно позарез. Если у кого есть такой алгоритм поделитесь плз..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.05.2010, 14:29     Поиск пути в лабиринте
Посмотрите здесь:

C++ Поиск пути
C++ Поиск пути
C++ Поиск в лабиринте
Поиск пути C++
C++ поиск длины пути
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Manjak
 Аватар для Manjak
269 / 175 / 7
Регистрация: 12.03.2010
Сообщений: 494
14.05.2010, 14:44     Поиск пути в лабиринте #2
A* алгоритм, по моему, лучший из простых алгоритмов
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
14.05.2010, 14:47     Поиск пути в лабиринте #3
что значит не ищет пути по диагонали? волновой ищет наикратчайшие пути, вам нужен какой-то определенный из путей?
xproger
0 / 0 / 0
Регистрация: 10.01.2010
Сообщений: 16
14.05.2010, 16:32  [ТС]     Поиск пути в лабиринте #4
1 1 0 1 0 0 0
1 1 1 3 1 1 0
1 1 0 1 0 2 0
1 1 0 1 1 0 0

Вот такая ситуация. попасть из точки 2 в точку 3. Путь должен быть такой: влево и по диагонали(т.е. вверх и влево).

Добавлено через 26 минут
вот алгоритм, которым я пользуюсь. уже не помню где взял.
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
int map[50][50];
 
// тут ваш код где заполняем мап, где 1- клетка занята, 0 - свободна
 
SearchWay(int x, int y, int x_to, int y_to)
{
    const int size =50;
    int matrix[size][size][3];
 
    int step;
    bool added=true,result=true;
    for(int i=0;i<size;i++)
    {
        for(int j=0;j<size;j++)
        {
            if(map[i][j]!=0)
            {
                matrix[i][j][0] = -2;// занято
            }
            else
            {
                matrix[i][j][0] = -1;// Мы еще нигде не были
            }
        }
    }
    matrix[x_to][y_to][0]= 0;// До финиша ноль шагов - от него будем разбегаться
    step = 0; // Изначально мы сделали ноль шагов
    
    // Пока вершины добаляются и мы не дошли до старта
 
    while(added && matrix[x][y][0]==-1)
    {
        added = false;// Пока что ничего не добавили
        step++;// Увеличиваем число шагов
 
        for(int i=0;i<size;i++)// Пробегаем по всей карте
        {
            for(int j=0;j<size;j++)
            {
                // Если (i, j) была добавлена на предыдущем шаге
                // Пробегаем по всем четырем сторонам
                if(matrix[i][j][0]== step-1)
                {
                    int _i,_j;
 
                    _i=i+1;_j=j;
                    // Если не вышли за пределы карты -  обрабатываем
                    if(_i>=0 && _j>=0 && _i<size && _j<size)
                    {
                        // Если (_i, _j) уже добавлено или непроходимо, то не обрабатываем 
                         if(matrix[_i][_j][0]==-1 && matrix[_i][_j][0]!=-2)
                         {
                             matrix[_i][_j][0]= step; // Добав-
                             matrix[_i][_j][1]= i; // ля-
                             matrix[_i][_j][2]= j; // ем
                             added = true; // Что-то добавили
                         }
                    }
                    _i=i-1;_j=j;
                    // Если не вышли за пределы карты -  обрабатываем
                    if(_i>=0 && _j>=0 && _i<size && _j<size)
                    {
                        // Если (_i, _j) уже добавлено или непроходимо, то не обрабатываем 
                        if(matrix[_i][_j][0]==-1 && matrix[_i][_j][0]!=-2)
                        {
                            matrix[_i][_j][0]= step; // Добав-
                            matrix[_i][_j][1]= i; // ля-
                            matrix[_i][_j][2]= j; // ем
                            added = true; // Что-то добавили
                        }
                    }
                    _i=i;_j=j+1;
                    // Если не вышли за пределы карты -  обрабатываем
                    if(_i>=0 && _j>=0 && _i<size && _j<size)
                    {
                        // Если (_i, _j) уже добавлено или непроходимо, то не обрабатываем 
                        if(matrix[_i][_j][0]==-1 && matrix[_i][_j][0]!=-2)
                        {
                            matrix[_i][_j][0]= step; // Добав-
                            matrix[_i][_j][1]= i; // ля-
                            matrix[_i][_j][2]= j; // ем
                            added = true; // Что-то добавили
                        }
                    }
                    _i=i;_j=j-1;
                    // Если не вышли за пределы карты -  обрабатываем
                    if(_i>=0 && _j>=0 && _i<size && _j<size)
                    {
                        // Если (_i, _j) уже добавлено или непроходимо, то не обрабатываем 
                        if(matrix[_i][_j][0]==-1 && matrix[_i][_j][0]!=-2)
                        {
                            matrix[_i][_j][0]= step; // Добав-
                            matrix[_i][_j][1]= i; // ля-
                            matrix[_i][_j][2]= j; // ем
                            added = true; // Что-то добавили
                        }
                    }
                }
            }
        }
    }
 
    if(matrix[x][y][0]== -1)
    {
        result = false; // то пути не существует
    }
 
 
    if(result)
    {
        int _i=x,_j=y;
 
        while(matrix[_i][_j][0]!=0)
        {   
                        // тут ваш код где  записываем значение клеток и шагаем дальше к началу
            // записывать надо _i _J    
            int li = matrix[_i][_j][1];
            int lj = matrix[_i][_j][2];
            _i=li;_j=lj;
        }
    }
}
Вот он диагонали не обрабатывает(( Уже весь инет облазил и нигде не нашёл то что нужно.
Есть только пример на delphi с классами, но его надо переводить и от класса избавляться
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
14.05.2010, 17:03     Поиск пути в лабиринте #5
ну как бы в обычном смысле это стена..
xproger
0 / 0 / 0
Регистрация: 10.01.2010
Сообщений: 16
14.05.2010, 19:55  [ТС]     Поиск пути в лабиринте #6
Но ведь дельфийский алгоритм работает по диагонали, неужели на сях нет ни одного. Я по описанию реализовать алгоритм не смогу. Вот когда писал на дельфе то не надо было, а как сел за си, то вот понадобилось. (((

Добавлено через 1 час 29 минут
Всем спасибо. Вопрос снимается. Я решил эту задачу, модернизировав выложенный выше мною код. Алгоритм работает отлично и на компе и на моей мобилке.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.04.2016, 09:36     Поиск пути в лабиринте
Еще ссылки по теме:

C++ Поиск пути
C++ Рекурсия (не могу из нее выйти) поиска пути в лабиринте
C++ Алгоритм поиска пути в лабиринте, заданном связным графом

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

Или воспользуйтесь поиском по форуму:
NEW_ID
0 / 0 / 0
Регистрация: 08.01.2015
Сообщений: 54
09.04.2016, 09:36     Поиск пути в лабиринте #7
xproger,можешь показать как модернизировал код?
Yandex
Объявления
09.04.2016, 09:36     Поиск пути в лабиринте
Ответ Создать тему
Опции темы

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