Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.73/15: Рейтинг темы: голосов - 15, средняя оценка - 4.73
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
1

Отсортировать массив, который ищет самый короткий путь до точки

30.11.2018, 04:37. Показов 2858. Ответов 23
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Дорогие форумчане, прошу вашей помощи.

Пытаюсь написать алгоритм для монстра в игре. Алгоритм высчитывает самый короткий путь до игрока.
Алгоритм нашел (называется волновой Алгоритм более подробно тут http://pestantium.blogspot.com... -post.html), подстроил под себя, написал, но столкнулся с проблемой.

На выходе Алгоритм выдает мне двумерный массив интов, в котором кратчайший путь от одной точки до другой представлен последовательностью цифр от 0 до n, где n это максимальное кол-во ходов которое сделает точка (монстр в последствии), что бы добраться до конечной точки (игрока в последствии).

Проблема такая, алгоритм высчитывает все возможные ходы, и "пачкает" этот двумерный массив ненужными ходами.

Более наглядно, на скрине.

Мне нужно вместо мусора поставить те же значения как и у стен (-2), но никак не могу сообразить как же мне это сделать.
Может кол-во тем, которые я прошел не позволяют догадаться, может сам не могу догнать, хз)

Прошу наведите на мысль.


приложу так же код:
Кликните здесь для просмотра всего текста
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
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace ConsoleApp7
{
    class Program
    {
 
        static void Main(string[] args)
        {
 
            var a = new int[,]{ { 0, 1, 1, 1, 1 ,1 ,1 ,1, 1, 1 }, // 0-положение игрока. 1- пустые ячейки. 6- стена. 3-положение монстра
                                { 6, 1, 6, 6, 6 ,6 ,6 ,6, 6, 1 },
                                { 1, 1, 1, 6, 6 ,1 ,1 ,1, 6, 1 },
                                { 1, 6, 1, 1, 1 ,1 ,6 ,1, 1, 1 },
                                { 1, 6, 6, 6, 6 ,6 ,6 ,1, 6, 1 },
                                { 1, 6, 6, 6, 6 ,6 ,6 ,1, 1, 1 },
                                { 1, 1, 1, 1, 1 ,1 ,1 ,1, 1, 3 },};
 
            var b = FindWave(a, 9, 6, 0, 0);                                  
            Console.ReadLine();
        }
 
 
        public static int[,] FindWave(int[,] Map, int startX, int startY, int targetX, int targetY)
        {
 
            bool add = true;
            int[,] cMap = new int[Map.GetLength(0), Map.GetLength(1)]; // создали новый массив cMap чтоб по нему искать путь
            int step = 0;
            for (var y = 0; y < Map.GetLength(0); y++)
                for (var x = 0; x < Map.GetLength(1); x++)
                {
                    if (Map[y, x] == 6) // если в искомом массиве стена то
                        cMap[y, x] = -2;//ставим стену в новом массиве по этому же элементу                   
                    else
                        cMap[y, x] = -1; //-1 это пустое место
                }
            cMap[startY, startX] = 0;
            while (add == true)
            {
                var MapHeight = cMap.GetLength(0);
                var MapWidht = cMap.GetLength(1);
                for (var y = 0; y < cMap.GetLength(0); y++)
                    for (var x = 0; x < cMap.GetLength(1); x++)
                    {
                        if (cMap[y, x] == step)
                        {
                            //Ставим значение шага+1 в соседние ячейки (если они проходимы)
                            if (y - 1 >= 0)
                            {
                                if (cMap[y - 1, x] != -2 && cMap[y - 1, x] == -1)
                                    cMap[y - 1, x] = step + 1;
                            }
                            if (x - 1 >= 0)
                            {
                                if (cMap[y, x - 1] != -2 && cMap[y, x - 1] == -1)
                                    cMap[y, x - 1] = step + 1;
                            }
                            if (y + 1 < MapHeight)
                            {
                                if (cMap[y + 1, x] != -2 && cMap[y + 1, x] == -1)
                                    cMap[y + 1, x] = step + 1;
                            }
                            if (x + 1 < MapWidht)
                            {
                                if (cMap[y, x + 1] != -2 && cMap[y, x + 1] == -1)
                                    cMap[y, x + 1] = step + 1;
                            }
                        }
 
                    }
                step++;
                add = true;
                if (cMap[targetY, targetX] == step)
                {
                    add = false;
                    Console.WriteLine("Решение найдено");
 
                }
                if (step > cMap.GetLength(0) * cMap.GetLength(1))
                {
                    add = false;
                    Console.WriteLine("Решение не найдено");
                }
            }
 
            return cMap;
        }
}
Миниатюры
Отсортировать массив, который ищет самый короткий путь до точки  
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.11.2018, 04:37
Ответы с готовыми решениями:

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

Найти самый длинный и самый короткий отрезок
Данная множество точек координатной плоскости в виде двух одномерных массивов Х и У. Найти самый...

Найти самый короткий путь от точки до точки в матрице
Народ, помогите... Такая задача, имеется массив символов(char arr) в котором в рандомных местах...

Самый короткий путь алгоритм Флойда
Не все тесты проходит, где ошибка? Дан ориентированный взвешенный полный граф, рёбрам которого...

23
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
30.11.2018, 05:00 2
а как вы узнаете, что элементы массива синего цвета являются кратчайшим путём?
судя по массиву - у вас просто отработанный алгоритм, который дал вам расчеты, а вот выбор кратчайшего (и возможность достижения игрока) это уже ваша задача.
как вариант - отталкиваться от положения игрока, там вы имеете самое короткое значение, то есть 15, берём вокруг и ищем 14 и так до конца, везде, где встречаем еще одно (или несколько) совпадающее значение (например 14 будет снизу и справа) - все кроме одного из значений заменяем на -2. Еще можно расширить заполнение числом -2 так - ставить его везде где значение вокруг рассматриваемой позиции больше или равно, исключая путь маршрута, который вы ежу прошли. Но в таком случае есть ограничение - обязательно должны быть стены вокруг, то есть маршрут не должен делать петли соприкасаясь с ранее пройденным участком (в целом этого не должно происходить, так как точка соприкосновения даст априори более короткий маршрут).
Если написал сумбурно и задавайте вопросы, я постараюсь написать что-то конкретное.
1
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
30.11.2018, 05:08 3
Если я правильно вас понял, то мой вариант выдаст такой результат.
Миниатюры
Отсортировать массив, который ищет самый короткий путь до точки  
1
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
30.11.2018, 05:25  [ТС] 4
Цитата Сообщение от belalugoci Посмотреть сообщение
а как вы узнаете, что элементы массива синего цвета являются кратчайшим путём?
Последовательность, которая идет от 0 до n(15 в этом случае) и будет являться самым коротким путем.В этом и есть суть Алгоритма
Цитата Сообщение от belalugoci Посмотреть сообщение
судя по массиву - у вас просто отработанный алгоритм, который дал вам расчеты, а вот выбор кратчайшего (и возможность достижения игрока) это уже ваша задача.
Да, это именно так, он дал мне расчеты, про возможность достижения, это уже потом, сейчас мне нужно привести этот массив в вид, который у вас снизу на скрине, что бы в дальшейшем я уже отталкивался от массива в котором просто проложен самый короткий путь.
Цитата Сообщение от belalugoci Посмотреть сообщение
все кроме одного из значений заменяем на -2
Тоже про это думал, но как именно выбрать именно ТО значение. В голову приходила мысль о том чтобы проверить, допустим 2 последующие клетки, так чтобы было в нижней/верхней/правой/левой 14, и если в следующей нвпл 13 то тогда уже удалять, но уверен есть решение проще, да и если стоит игрок у края, то там выход за границы пойдет при проверке, придется условий много писать...

Добавлено через 5 минут
UPD: В теории я хочу реализовать это так.
У меня есть массив с самым коротким путем. Я подсовываю этот массив монстру, там он будет стоять в координатах со значением 0.
Затем идет проверка, какая координата является значением 1, туда и идет монстр.
Затем цикл повторяется, массив обновляется и все происходит заново. Но это в теории
0
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
30.11.2018, 05:29 5
Цитата Сообщение от lexatorgas Посмотреть сообщение
Последовательность, которая идет от 0 до n(15 в этом случае) и будет являться самым коротким путем.В этом и есть суть Алгоритма
это как раз понятно, я говорю о вашей программе, смотреть глазами человека и обводить синим - компьютер ещё нужно научить.

Цитата Сообщение от lexatorgas Посмотреть сообщение
Тоже про это думал, но как именно выбрать именно ТО значение. В голову приходила мысль о том чтобы проверить, допустим 2 последующие клетки, так чтобы было в нижней/верхней/правой/левой 14, и если в следующей нвпл 13 то тогда уже удалять, но уверен есть решение проще, да и если стоит игрок у края, то там выход за границы пойдет при проверке, придется условий много писать...
после такого просто теряется интерес к теме.

я вам дал всю информацию для реализации, код напишите самостоятельно с аж кучей условий (вам бы на ассемблере попрограммировать немножко, чтобы понять как всё работает и почему у вас там почти постоянно будет CMP, JZ и т.п.)
0
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
30.11.2018, 05:42  [ТС] 6
Цитата Сообщение от belalugoci Посмотреть сообщение
после такого просто теряется интерес к теме.
После такого, как я понял, это написанное мной "придется условий много писать..."
Вы подумали как это будет выглядеть в коде? Сколько это займет строк? 50? 100? Я сейчас имею ввиду кол-во всех проверок, ведь там 4 возможных направления, а за каждым еще как максимум 3, т.е в худшем случае 12. 12 проверок, не считая условий выхода за границы массива.

Такое решение я написать смогу. Но тему я создал для того, что бы мой код не был похож на один большой костыль,
посмотрев на который через неделю я едва пойму что там происходит(в коде).

В общем
Цитата Сообщение от lexatorgas Посмотреть сообщение
но уверен есть решение проще
.
0
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
30.11.2018, 05:57 7
Цитата Сообщение от belalugoci Посмотреть сообщение
а как вы узнаете, что элементы массива синего цвета являются кратчайшим путём?
именно поэтому я первым задал этот вопрос. Если у вас голый массив и нет НИКАКОЙ информации об этом оптимальном маршруте, то вам всё равно придётся идти по массиву и проверять.

Цитата Сообщение от lexatorgas Посмотреть сообщение
Вы подумали как это будет выглядеть в коде? Сколько это займет строк?
Сначала пишется код, проверяется его работа, а потом вы его оптимизируете, вплоть до полной переделки. Позавчера я написал вот такое:
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
                                        if (DimBits[dimPos, 4] == DimBits[y, 4])
                                           if (DimBits[dimPos, 5] == DimBits[y, 5])
                                              if (DimBits[dimPos, 6] == DimBits[y, 6])
                                                 if (DimBits[dimPos, 7] == DimBits[y, 7])
                                                    if (DimBits[dimPos, 8] == DimBits[y, 8])
                                                       if (DimBits[dimPos, 9] == DimBits[y, 9])
                                                          if (DimBits[dimPos, 14] == DimBits[y, 14])
                                                             if (DimBits[dimPos, 15] == DimBits[y, 15])
                                                                if (DimBits[dimPos, 16] == DimBits[y, 16])
                                                                   if (DimBits[dimPos, 17] == DimBits[y, 17])
                                                                      if (DimBits[dimPos, 18] == DimBits[y, 18])
                                                                         if (DimBits[dimPos, 23] == DimBits[y, 23])
                                                                            if (DimBits[dimPos, 24] == DimBits[y, 24])
                                                                               if (DimBits[dimPos, 25] == DimBits[y, 25])
                                                                                  if (DimBits[dimPos, 26] == DimBits[y, 26])
                                                                                     if (DimBits[dimPos, 27] == DimBits[y, 27])
                                                                                        if (DimBits[dimPos, 3] == DimBits[y, 3])
                                                                                           if (DimBits[dimPos, 13] == DimBits[y, 13])
                                                                                              if (DimBits[dimPos, 22] == DimBits[y, 22])
                                                                                                 if (DimBits[dimPos, 2] == DimBits[y, 2])
                                                                                                    if (DimBits[dimPos, 12] == DimBits[y, 12])
                                                                                                       if (DimBits[dimPos, 21] == DimBits[y, 21])
                                                                                                          if (DimBits[dimPos, 1] == DimBits[y, 1])
                                                                                                             if (DimBits[dimPos, 11] == DimBits[y, 11])
                                                                                                                if (DimBits[dimPos, 20] == DimBits[y, 20])
                                                                                                                   if (DimBits[dimPos, 0] == DimBits[y, 0])
                                                                                                                      if (DimBits[dimPos, 10] == DimBits[y, 10])
                                                                                                                         if (DimBits[dimPos, 19] == DimBits[y, 19])
и как-то никто не умер.
Через пару часов буду посвободнее - напишу вашу реализацию, а вы потом напишете свою или кто-то еще напишет, может узнаю что-то новое.
0
2063 / 1542 / 168
Регистрация: 14.12.2014
Сообщений: 13,402
30.11.2018, 06:11 8
Цитата Сообщение от lexatorgas Посмотреть сообщение
В общем
В общем насколько понимаю волны надо пускать одновременно из стартового положения и из конечного и двигать их синхронно отслеживая факт встречи. Тот маршрут при котором n в точке встречи будет наименьшим и будет кратчайшим. т.е. трассируется обратно от наименьшего n.
Добавлено через 1 минуту
Цитата Сообщение от belalugoci Посмотреть сообщение
и как-то никто не умер.
кроме здраваго смысла.

Добавлено через 6 минут
lexatorgas,
В принципе и по вашему массиву можно пройти по кратчайшему пути от конечного положения в начальное выбирая на каждом шаге клетку с минимальным неотрицательным значением. Но и таких путей в принципе может оказаться несколько .
0
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
30.11.2018, 06:12 9
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
В общем насколько понимаю волны надо пускать одновременно из стартового положения и из конечного и двигать их синхронно отслеживая факт встречи. Тот маршрут при котором n в точке встречи будет наименьшим и будет кратчайшим. т.е. трассируется обратно от наименьшего n.
зачем если кратчайший путь уже построен?

Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
кроме здраваго смысла.
предложите ваш здравомыслящий вариант.
0
2063 / 1542 / 168
Регистрация: 14.12.2014
Сообщений: 13,402
30.11.2018, 06:15 10
Цитата Сообщение от belalugoci Посмотреть сообщение
зачем если кратчайший путь уже построен?
ТАк его еще найти надо какой из них кратчайший.

Добавлено через 1 минуту
Цитата Сообщение от belalugoci Посмотреть сообщение
предложите ваш здравомыслящий вариант.
От конечного назад выбирая наименьшего соседа. Ну при этом как бы гнать исходную волну в двух направлениях оптимальней чем в одном.
0
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
30.11.2018, 06:17 11
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
ТАк его еще найти надо какой из них кратчайший.
тот, что оканчивается в точке игрока, массив - это и есть УЖЕ найденное решение. Топикстартер не просит нас искать кратчайший путь, он просит лаконично избавиться от ошибочных веток прохода алгоритма поиска.

Как я сразу и написал - путь от игрока к монстру однозначно проводит нас по кратчайшему маршруту (если маршрутов несколько, то выбираем любой).
0
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
30.11.2018, 06:19  [ТС] 12
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
В общем насколько понимаю волны надо пускать одновременно из стартового положения и из конечного и двигать их синхронно отслеживая факт встречи. Тот маршрут при котором n в точке встречи будет наименьшим и будет кратчайшим.
Но ведь в этом случаем волны будут так-же как и в моем алгоритме пускаться во все стороны, и "подтирать" за ними никто не будет (удалять ненужные маршруты, которые не оказались самыми короткими).

Моя задача на данный момент и есть "подтереть" массив, оставив в нем только самый короткий путь. А остальное уставить условными стенками.
Нужно как то обьяснить компу, что вот этот путь и есть самый короткий, и все другие бессмысленны, поэтому поставь там везде стены.
0
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
30.11.2018, 06:19 13
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
От конечного назад выбирая наименьшего соседа. Ну при этом как бы гнать исходную волну в двух направлениях оптимальней чем в одном.
Вы сейчас о чем? Вам не понравились мои if, причем тут какие-то волны?

Гнать волну от монстра не имеет смысла, так как от него расходятся ложные маршруты - вы будете выполнять лишний код.
0
2063 / 1542 / 168
Регистрация: 14.12.2014
Сообщений: 13,402
30.11.2018, 06:25 14
Лучший ответ Сообщение было отмечено lexatorgas как решение

Решение

Цитата Сообщение от lexatorgas Посмотреть сообщение
Моя задача на данный момент и есть "подтереть" массив, оставив в нем только самый короткий путь.
Нинада ниче подтирать. мы проставили количество шагов которое нужно пройти от старта до финиша. теперь от финиша идем обратно к старту выбирая клетку из которой до финиша количество шагов минимальное (в ней записанное) и так приходим на старт кратчайшим путем. А при встречной трассировке выбирая точку встречи с минимальным n мы опять же получаем точку на кратчайшем пути откуда трассируем маршрут обратно в обе стороны.
Суть алгоритма - прямой ход (волна) определяет возможные пути и их длины. Обратный ход находит кратчайший из возможных.
1
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
30.11.2018, 06:34 15
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
Нинада ниче подтирать
кстати да, автор, а какая цель то у вас? наличие расставленных -2 ровным счётом ничего не даст.
0
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
30.11.2018, 06:34  [ТС] 16
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
Обратный ход находит кратчайший из возможных.
Попробую сейчас так:
Создать новый такой же массив из столько условных стенок.
Вывести максимальное значение в первом массиве (оно и будет положением игрока) и присвоить этим же коодинатам нового массива максимальное значение.
Затем в первом массиве проверять 4 стороны на значение (макс-1 и макс=макс-1) и т.д
Так же поэтапно присваивать новому массиву все значения.
0
2063 / 1542 / 168
Регистрация: 14.12.2014
Сообщений: 13,402
30.11.2018, 06:34 17
т.е. на обратном ходу пишем цепочку найденных координат в обычный одномерный массивчик, потом реверсим. Ну а можно сам алгоритм развернуть - т.е. пускать волну из конечной точки а не из начальной, чтобы массив лишний раз не разворачивать.
0
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
30.11.2018, 06:35  [ТС] 18
Цитата Сообщение от belalugoci Посмотреть сообщение
кстати да, автор, а какая цель то у вас? наличие расставленных -2 ровным счётом ничего не даст.
Цитата Сообщение от lexatorgas Посмотреть сообщение
UPD: В теории я хочу реализовать это так.
У меня есть массив с самым коротким путем. Я подсовываю этот массив монстру, там он будет стоять в координатах со значением 0.
Затем идет проверка, какая координата является значением 1, туда и идет монстр.
Затем цикл повторяется, массив обновляется и все происходит заново. Но это в теории
Как то так
0
2063 / 1542 / 168
Регистрация: 14.12.2014
Сообщений: 13,402
30.11.2018, 06:39 19
Цитата Сообщение от lexatorgas Посмотреть сообщение
Так же поэтапно присваивать новому массиву все значения.
Задача получить не 2D массив с пометками а цепочку координат (ну или смещений, хотя координат для автопилота пропорциональной навигации удобнее), последовательно пройдя по которым окажемся в заданной точке.
0
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
30.11.2018, 06:40 20
Цитата Сообщение от lexatorgas Посмотреть сообщение
Как то так
Fulcrum_013 дал отличный совет по поводу запуска волны от игрока, тогда монстр всегда ходит на клетку где шаг меньше на 1. Имхо это проще и быстрее чем считать в массив координаты маршрута, которые живут только одну итерацию.
0
30.11.2018, 06:40
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.11.2018, 06:40
Помогаю со студенческими работами здесь

Лабиринт, найти самый короткий путь
Лабиринт задан квадратной матрицей случайных чисел. Непроходимые клетки - 1, проходимые - 0....

Лабиринт. Найти самый короткий путь от входа в выходу
Я написал программу для обработки таблицы. Я представляю таблицу в качестве лабиринта. Ячейка...

Найти самый короткий путь от левого столбца массива к правому
Дан двумерный числовой массив размером N1xN2. Найти такой путь от левого столбца массива к...

Определить самый короткий путь между точками на поле с препятствиями
Приложение должно позволять определять самый короткий путь между двумя произвольно вводимыми с...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru