Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.54/26: Рейтинг темы: голосов - 26, средняя оценка - 4.54
0 / 0 / 0
Регистрация: 14.08.2020
Сообщений: 6

Генерация точек и пути между ними

14.08.2020, 15:14. Показов 4937. Ответов 13

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

Стоит задача: Сгенерировать игровое поле 4Х4. На данном поле случайно задать две точки на расстоянии минимум две клетки друг от друга. Между точками должна быть возможность проложить путь без диагоналей (пример: на рисунке весь путь включая точки выделил желтым). За пределами пути в других клетках необходимо случайно генерировать бомбы.

С генерацией поля я справился:
C#
1
2
3
4
5
6
7
8
//Matrix values:
    //0 - Empty cell
    //1 - Bomb
    //2 - Pont (Start and Finish)
    //3 - Way
 
const int SIZE = 4;
int[,] mapData = new int[SIZE , SIZE];
Далее случайным образом задаю первую точку:
C#
1
2
3
4
5
6
7
8
9
10
(int, int) GetFirstPoint(int sizeRows)
    {
        Random random = new Random(DateTime.Now.Second);
 
        //Generate first random point
        return (random.Next(SIZE), random.Next(SIZE));
    }
 
(int, int) point = GetFirstPoint(sizeRows);
        mapData[point.Item1, point.Item2] = 2;
Не могу продумать алгоритм генерации второй точки с условиями описанными в задаче (между точками нужно сгенерировать путь). Т.е. значение элемента массива присваеваем 3.

C#
1
mapData[nextPoint.Item1, nextPoint.Item2] = 3;
Подскажите, пожалуйста, что делать дальше? Каким образом пролождить путь по клеткам и задать вторую точку?
Миниатюры
Генерация точек и пути между ними  
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
14.08.2020, 15:14
Ответы с готовыми решениями:

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

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

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

13
 Аватар для Enifan
1849 / 1191 / 501
Регистрация: 14.10.2018
Сообщений: 3,214
14.08.2020, 15:54
Лучший ответ Сообщение было отмечено NeonWeber как решение

Решение

NeonWeber,
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
using System;
 
class Program
{
    static void Main()
    {
        int[,] arr;        // поле
        (int, int) point1; // 1-ая точка
        (int, int) point2; // 2-ая точка (также сгенерировано рандомно)
    }
 
    static bool Check(int[,] arr, (int, int) point1, (int, int) point2)
    {
        bool check = true;
        const int DISTANCE = 2; // минимальное допустимое растояние между точками
 
        Foo(point1.Item1, point1.Item2); // запуск рекурсии от 1-ой точки
 
        // level - уровень спуска по рекурсии
        void Foo(int x, int y, int level = 0)
        {
            if (!check) return;
 
            if (x == point2.Item1 && y == point2.Item2)
            {
                check = false;
                return;
            }
 
            if (level == DISTANCE) return;
 
            if (y > 0)                    Foo(x, y - 1, level + 1); // вверх
            if (x < arr.GetLength(0) - 1) Foo(x + 1, y, level + 1); // вправо
            if (y < arr.GetLength(1) - 1) Foo(x, y + 1, level + 1); // вниз
            if (x > 0)                    Foo(x - 1, y, level + 1); // влево
        }
 
        return check;
    }
}
1
0 / 0 / 0
Регистрация: 14.08.2020
Сообщений: 6
14.08.2020, 17:06  [ТС]
Не совсем понял, где необходимо присваивать элементам массива значение 3 (это клетки пути).
0
 Аватар для Enifan
1849 / 1191 / 501
Регистрация: 14.10.2018
Сообщений: 3,214
14.08.2020, 18:39
Цитата Сообщение от NeonWeber Посмотреть сообщение
На данном поле случайно задать две точки на расстоянии минимум две клетки друг от друга.
Вышеуказанный код выдает true если рандомная генерация 2-ой точки была сделана верно.
Цитата Сообщение от NeonWeber Посмотреть сообщение
где необходимо присваивать элементам массива значение 3 (это клетки пути).
А вот путей может быть много, эдак около 1000. Каким образом будем искать пути? Ближайший ? 1-ый попавшийся ? Все подряд ?
1
 Аватар для QuakerRUS
1469 / 1010 / 456
Регистрация: 30.10.2017
Сообщений: 2,799
14.08.2020, 23:01
Лучший ответ Сообщение было отмечено NeonWeber как решение

Решение

Так, если сильно не заморачиваться. Можно выбрать произвольный размер поля, количество бомб, минимально допустимый полученный путь.

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
using System;
using System.Collections.Generic;
 
class Demo
{
    public void Start()
    {
        Console.Write("Field size: ");
        size = int.Parse(Console.ReadLine());
        Console.Write("Bombs: ");
        int bombs = int.Parse(Console.ReadLine());
        Console.Write("Minimal path (0 for unlimited): ");
        int minimalPath = int.Parse(Console.ReadLine());
        Console.WriteLine("Generator attempts: {0}", Generate(bombs, minimalPath));
        Paint();
    }
 
    Random rnd = new Random();
    int size;
    char[] symbols = new char[] { '.', 'O', '*', 'S', 'F', '#' };
    int[] mx = new int[] { 0, 1, 0, -1 };
    int[] my = new int[] { -1, 0, 1, 0 };
 
    (int x, int y) start, finish;
    int[,] field;
 
    bool CoordsIsValid((int x, int y) coords) => coords.x >= 0 && coords.y >= 0 && coords.x < size && coords.y < size;
    (int x, int y) NewCoords() => (rnd.Next(size), rnd.Next(size));
 
    int Generate(int bombs, int minimalPath)
    {
        int count = 0;
        int path;
 
        do
        {
            count++;
            field = new int[size, size];
            start = NewCoords();
            field[start.x, start.y] = 3;
 
            do
                finish = NewCoords();
            while (Math.Max(Math.Abs(start.x - finish.x), Math.Abs(start.y - finish.y)) < 2);
 
            field[finish.x, finish.y] = 4;
 
            (int x, int y) bomb;
 
            for (int i = 0; i < bombs; i++)
            {
                do
                    bomb = NewCoords();
                while (field[bomb.x, bomb.y] != 0);
 
                field[bomb.x, bomb.y] = 1;
            }
 
            path = SearchPath();
        }
        while (path == -1 || (minimalPath != 0 && path < minimalPath));
 
        return count;
    }
 
    int SearchPath()
    {
        int[,] map = new int[size, size];
        bool success = false;
        var active = new List<(int x, int y)>() { finish };
        (int x, int y) newCoords;
 
        for (int dist = 1; !success && active.Count != 0; dist++)
        {
            var newActive = new List<(int x, int y)>();
 
            foreach (var coords in active)
            {
                for (int i = 0; !success && i < 4; i++)
                {
                    newCoords = (coords.x + mx[i], coords.y + my[i]);
 
                    if (!CoordsIsValid(newCoords))
                        continue;
 
                    if (field[newCoords.x, newCoords.y] == 3)
                    {
                        success = true;
                        map[newCoords.x, newCoords.y] = dist;
                        break;
                    }
 
                    if (field[newCoords.x, newCoords.y] == 1 || map[newCoords.x, newCoords.y] != 0 && map[newCoords.x, newCoords.y] <= dist)
                        continue;
 
                    map[newCoords.x, newCoords.y] = dist;
                    newActive.Add(newCoords);
                }
 
                if (success)
                    break;
            }
 
            active = newActive;
        }
 
        if (!success)
            return -1;
 
        (int x, int y) currentCoords = start;
        
        while (true)
        {
            (int x, int y) coords;
            newCoords = currentCoords;
 
            for (int i = 0; i < 4; i++)
            {
                coords = (currentCoords.x + mx[i], currentCoords.y + my[i]);
 
                if (!CoordsIsValid(coords))
                    continue;
 
                if (field[coords.x, coords.y] == 4)
                    return map[start.x, start.y];
 
                if (map[coords.x, coords.y] != 0 && map[coords.x, coords.y] < map[newCoords.x, newCoords.y])
                    newCoords = coords;
            }
 
            currentCoords = newCoords;
            field[currentCoords.x, currentCoords.y] = 5;
        }
    }
 
    void Paint()
    {
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
                Console.Write($"{symbols[field[i, j]]} ");
 
            Console.WriteLine();
        }
    }
}
 
class Program
{
    static void Main()
    {
        Demo demo = new Demo();
        demo.Start();
        Console.ReadKey();
    }
}
2
0 / 0 / 0
Регистрация: 14.08.2020
Сообщений: 6
19.08.2020, 12:32  [ТС]
Enifan, 1-ый попавшийся или случайный путь был бы более подходящим.

Добавлено через 16 минут
Enifan, то есть на текущий момент я получаю вот такого вида массивы:
0020 0200
0000 0000
0200 0000
0000 0002

Как сделать так, чтобы построить случайный путь между точками со значением 2?
т.е., например (значение 3 - это путь):
0023 0200
0003 0330
0233 0030
0000 0032
0
0 / 0 / 0
Регистрация: 14.08.2020
Сообщений: 6
20.08.2020, 14:43  [ТС]
Нашел решение - рандромно двигаться по доступным соседям клетки.
Соседей инициализируем так:
C#
1
2
3
4
5
(int, int)[] neighbours = new (int, int)[4];
        neighbours[0] = (point.Item1, point.Item2 + 1); //RIGHT
        neighbours[1] = (point.Item1, point.Item2 - 1); //LEFT
        neighbours[2] = (point.Item1 + 1, point.Item2); //DOWN
        neighbours[3] = (point.Item1 - 1, point.Item2); //UP
А проверяем так:
C#
1
2
3
4
5
6
7
8
9
10
11
foreach(var neighbour in neighbours)
{
            //Check bounds
            if (neighbour.Item2 < 0 || neighbour.Item2 >= field.GetLength(0))
                continue;
            if (neighbour.Item1 < 0 || neighbour.Item1 >= field.GetLength(1))
                continue;
            //Check visit
            if (field[neighbour.Item1, neighbour.Item2] != 0)
                continue;
}
После этого выбираем случаного соседа из доступных и передвигаемся туда, пока не достигнем финишной клетки.
0
 Аватар для QuakerRUS
1469 / 1010 / 456
Регистрация: 30.10.2017
Сообщений: 2,799
20.08.2020, 15:21
NeonWeber, чем вам мой вариант не нравится? Там уже все решено.
0
1524 / 515 / 126
Регистрация: 09.01.2018
Сообщений: 1,620
20.08.2020, 15:39
Цитата Сообщение от NeonWeber Посмотреть сообщение
После этого выбираем случаного соседа из доступных и передвигаемся туда, пока не достигнем финишной клетки.
Т.е., когда вы окажетесь по соседству с финишной клеткой, вероятность ее достижения равна 1/3, т.к. генератор пути может выбрать движение в другом направлении.

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

Code
1
2
3
4
[ ] [ ] [ ] [x]
[s] [ ] [ ] [ ]
[-] [-] [-] [-]
[ ] [ ] [-] [-]
Куда "пойдет" генератор путей в этом случае?
Как видите, не все так просто.
0
0 / 0 / 0
Регистрация: 14.08.2020
Сообщений: 6
20.08.2020, 15:48  [ТС]
escoult, Когда окажемся по соседству с финишной клеткой, строить путь уже нет необходимости. Он выстроен. Ну по крайней мере в моей задаче.

Добавлено через 2 минуты
QuakerRUS, решение хорошее, просто не совсем мне подошло.
0
 Аватар для QuakerRUS
1469 / 1010 / 456
Регистрация: 30.10.2017
Сообщений: 2,799
20.08.2020, 16:12
Цитата Сообщение от NeonWeber Посмотреть сообщение
просто не совсем мне подошло
Чем именно не подошло? Размер поля 4 можно выбрать или в константу забить.
0
 Аватар для Enifan
1849 / 1191 / 501
Регистрация: 14.10.2018
Сообщений: 3,214
20.08.2020, 16:38
Цитата Сообщение от NeonWeber Посмотреть сообщение
случайный путь
Если еще актуально:
1) создается список, который будет записывать путь
2) рандомно выбирается путь от 1-ой точки или последнего значения списка (при 1-ом ходе от точки, далее от списка)
3) проверяется граница массива, если выход за пределы - возвращаемся к пункту 2
4) проверяем, чтобы найденный путь не совпадал с 1-ой точкой и значениями списка
5) если проблем нет - записываем новое значение в список
6) дошли до 2-ой точки - по значениям из списка заполняем массив
Проблема когда придется начинать алгоритм сначала: может получить так, что до 2-ой точки мы не дошли, а ходить нам некуда (либо границы массива, либо попадаем на 1-ую точку, либо на значения из списка)
---2
----
1x--
xx--
В данной таблице:
1 и 2 - точки
- - пустые значения
x - сгенерированные значения
Порядок генерации значений: x x x: красный, зеленый, оранжевый
По данному алгоритму можно войти в бесконечный цикл, и чтобы этого избежать, модифицирует код:
перед генерацией пункта 2 должны быть 4 пустые значения (вверх, право, вниз, влево) - при неудачной попытке в любом направлении заполняется одно из этих направлений. Если все направления заполнены - ходить некуда - возвращаемся к пункту 1
0
1524 / 515 / 126
Регистрация: 09.01.2018
Сообщений: 1,620
20.08.2020, 19:51
Цитата Сообщение от NeonWeber Посмотреть сообщение
Когда окажемся по соседству с финишной клеткой, строить путь уже нет необходимости. Он выстроен. Ну по крайней мере в моей задаче.
Из вашего кода этого не видно. Впрочем, задача ваша и вам ее решать.

Цитата Сообщение от Enifan Посмотреть сообщение
Если еще актуально:
Слишком много возни будет с таким алгоритмом.
По идее надо составлять граф и пересчитывать все вершины перед каждым новым ходом, чтобы знать "попадаем ли мы в конечную вершину, если сделаем ход А".
Тоже много возни для задачи на 16 клеток.

Я бы использовал самый простой вариант - сгенерировать любой рандомный путь без учета посещенных клеток, а пересечения затем удалить.
1
0 / 0 / 0
Регистрация: 14.08.2020
Сообщений: 6
27.08.2020, 11:37  [ТС]
QuakerRUS, Ваш вариант в итоге подошёл идеально! Спасибо!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
27.08.2020, 11:37
Помогаю со студенческими работами здесь

Структура, координаты точек, расстояние между ними.
Доброе время суток. Если можете, помогите найти ошибку. Заранее благодарю. Задача. Найти такую точку пространства, сумма...

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

Вывести номера точек с наибольшим расстоянием между ними
2.2 Даны три точки на плоскости с координатами (x1,y1), (x2,y2), (x3,y3). Вывести номера точек с наибольшим расстоянием между ними.

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

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


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Новые блоги и статьи
Уведомление о неверно выбранном значении справочника
Maks 06.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt
8Observer8 05.04.2026
Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .
AkelPad-скрипты, структуры, и немного лирики..
testuser2 05.04.2026
Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
Отображение реквизитов в документе по условию и контроль их заполнения
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II
kumehtar 04.04.2026
Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .
Программный контроль заполнения реквизитов табличной части документа
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .
wmic не является внутренней или внешней командой
Maks 02.04.2026
Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru