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

@lexatorgas · Регистрация: 25.06.2017

Студворк — интернет-сервис помощи студентам

Дорогие форумчане, прошу вашей помощи.

Пытаюсь написать алгоритм для монстра в игре. Алгоритм высчитывает самый короткий путь до игрока.
Алгоритм нашел (называется волновой Алгоритм более подробно тут 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;
        }
}

@lexatorgas · 30.11.2018, 06:41 **[ТС]**

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
public static int[,] SortArray (int [,] array )
        {
            var maxElement = 0;
            for (var i = 0; i < array.GetLength(0); i++)
                for(var j=0; j<array.GetLength(1); j++)
                {
                    if (array[i, j] > maxElement)
                        maxElement = array[i, j];
                }
 
            var newArr = new int[array.GetLength(0), array.GetLength(1)];
            for (var i = 0; i < array.GetLength(0); i++)
                for (var j = 0; j < array.GetLength(1); j++)
                {
                    if (array[i, j] == maxElement)
                    {
                        newArr[i, j] = maxElement;
                        maxElement = maxElement - 1;
                    }
                    
 
 
                    
                }
            return newArr;

Получилось то, что и хотел, как же все оказалось просто, всем спасибо!

@lexatorgas · 30.11.2018, 06:45 **[ТС]**

Получилось даже так, что если есть 2 одинаковых пути, оставляет один

Эх. всегда бы сидеть в 2+ мозга и писать код. А то одному уж сильно долго доходит..

@belalugoci · 30.11.2018, 06:46

Сообщение от lexatorgas

Получилось то, что и хотел, как же все оказалось просто, всем спасибо!

я наверное так и не понял что вы хотите, но каждую итерацию дважды бегать по массиву это ужасть.
вам нужно только проверить 4 точки, причем 4 проверки будут максимальным числом, часто будет всё заканчиваться на 1-2-3, то есть в среднем у вас будет не более 2-х проверок. Вместо двух if у вас будет дважды бегать массив i, j.

@Fulcrum_013 · 30.11.2018, 12:31

Сообщение от lexatorgas

Эх. всегда бы сидеть в 2+ мозга и писать код.

Ну если че стучись. у нас тут есть небольшое сообщество хобби геймдеверов. Шарп правда не любит никто, но как бы алгоритмы они на чем угодно реализуемы вопрос только сколько головняка на эти реализации надо.

Добавлено через 7 минут

Сообщение от lexatorgas

Затем цикл повторяется, массив обновляется и все происходит заново. Но это в теории

В теории пересчитывать массив на второй итерации очень не комильфо причем чем больше карта тем не комильфо в квадрате.
На второй ход существуют 3 варианта:
1) игрок не двигался - массив валидный.
2) игрок двинулся по рассчитанному пути - от конца пути нужно отрезать ход игрока.
3) игрок двинулся не по пути - тоже разные вариации ускоренного пересчета, но в простейшем случае просто дописываем в путь ход игрока. Хотя и нет гарантии что результат будет кратчайшим, но зато монстр не будет туда-сюда мотыляться, а будет за игроком бежать по выбранному в начале пути.

Новые блоги и статьи Все статьи Все блоги /
Был праздник вчера, а я и не знал. kumehtar 28.07.2026 27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Новости компьютерного мира и их обсуждение (4) Салют, шампанское, овации! :drink:	Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему Hrethgir 27.07.2026 То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .	тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .	мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .
Очистка реквизитов и табличных частей документа при копировании (вариант 2) Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .	сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.	сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил anaschu 25.07.2026 две стороны одной монеты

@lexatorgas 0 / 0 / 0 Регистрация: 25.06.2017 Сообщений: 60
	30.11.2018, 06:45 [ТС]
	Получилось даже так, что если есть 2 одинаковых пути, оставляет один Эх. всегда бы сидеть в 2+ мозга и писать код. А то одному уж сильно долго доходит.. Миниатюры 0