Морской бой

@agassh · Регистрация: 25.12.2020

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

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

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
#include <vector>
#include <iostream>
#include<string>
#include <algorithm>
using namespace std;
class ships
{
public:
    int trpd_boat = 1;
    int destroyers = 2;
    int cruisers = 3;
    int battleship = 4;
   
};
class water : public ships
{
public:
    
    void filling()
    {
        int s = 0;
        int Pole[10][10] = {{ 0,0,0,0,0,0,0,0,0,0 }, { 0,0,0,0,0,0,0,0,0,0 }};
        int random[2] = { 1,-1 };
        int r = random[rand() % 2];
        srand(time(NULL));
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 2; j++) 
            {
                Pole[rand() % 10][rand() % 10] = trpd_boat;                                        
            }
            cout << endl;
        }
        for (int i = 0; i < 2; i++) 
        {
            for (int j = 0; j < 3; j++)
            {
                Pole[rand() % 10][rand() % 10] = destroyers;                  
        } 
        
        for (int i = 0; i < 9; i++) 
        {
            for (int j = 0; j < 9; j++) 
            {
                if (Pole[i][j] == 2 && s<3)
                {
                    Pole[i][j+1] = destroyers;
                    s++;
                }
                else
                { 
                    s = 0;
                }
 
            }
            }
        }
        for (int i = 0; i < 1; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                Pole[rand() % 10][rand() % 10] = cruisers;
            }
        }
        for (int i = 0; i < 1; i++)
        {
            for (int j = 0; j < 1; j++)
            {
                Pole[rand() % 10][rand() % 10] = battleship;
            }
        }
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                cout << Pole[i][j] << " ";
            }
            cout << endl;
        }
    }
 
};
int main()
{
    
    water water;
    water.filling();
   
    
}

Croessmah · 10.03.2022, 17:00

Выдрал из старого кода, может разберетесь.

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
    static std::vector<Ship> placeRandomShips(Field& field)
    {
        std::vector<Ship> ships;
        for (int shipSize = 4; shipSize > 0; --shipSize)
        {
            const int shipsCount = (4 - shipSize) + 1;
            for (int i = 0; i < shipsCount; ++i)
            {
                bool isVertical = !!(rand() & 1);
                CellCoord coord;
 
                while (!(coord = placeRandomShip(field, shipSize, isVertical)).valid())
                    isVertical = !isVertical;
 
                ships.push_back({coord , shipSize, isVertical});
            }
        }
 
        return ships;
    }
 
    static CellCoord placeRandomShip(Field& field, int shipSize, bool vertical)
    {
        int fastAttempts = 0;
        while (++fastAttempts < 50)
        {
            const int x = rand() % (vertical ? field.width() : field.width() - shipSize);
            const int y = rand() % (vertical ? field.height() - shipSize : field.height());
            const CellCoord coord{ x, y };
 
            if (placeShip(field, coord, shipSize, vertical))
                return coord;
        }
 
        std::vector<CellCoord> freeCells;
        freeCells.reserve(field.width() * field.height());
        for (int i = 0; i < field.width(); ++i)
            for (int j = 0; j < field.height(); ++j)
                freeCells.push_back(CellCoord(i, j));
        std::shuffle(freeCells.begin(), freeCells.end(), std::mt19937());
 
        for (CellCoord cell : freeCells)
            if (placeShip(field, cell, shipSize, vertical))
                return cell;
 
        return InvalidCell();
    }
 
    static bool placeShip(Field& field, CellCoord coord, int shipSize, bool vertical)
    {
        if (!mayBePlaced(field, coord, shipSize, vertical))
            return false;
        
        for (int i = 0; i < shipSize; ++i)
        {
            CellCoord shipCoord = vertical 
                ? CellCoord(coord.x, coord.y + i) 
                : CellCoord(coord.x + i, coord.y);
            field.set(shipCoord, Field::Ship);
        }
 
        return true;
    }
 
    static bool mayBePlaced(const Field& field, CellCoord coord, int shipSize, bool vertical)
    {
        for (int i = 0; i < shipSize; ++i)
        {
            CellCoord shipCoord = vertical
                ? CellCoord(coord.x, coord.y + i)
                : CellCoord(coord.x + i, coord.y);
 
            if (field.pick(coord) != Field::None)
                return false;
        }
 
        for (int i = -1; i < shipSize + 1; ++i)
        {
            CellCoord centerCoord = vertical
                ? CellCoord(coord.x, coord.y + i)
                : CellCoord(coord.x + i, coord.y);
            if (field.valid(centerCoord) && field.pick(centerCoord) != Field::None)
                return false;
 
            CellCoord leftOrTopCoord = vertical
                ? CellCoord(coord.x - 1, coord.y + i)
                : CellCoord(coord.x + i, coord.y - 1);
 
            if (field.valid(leftOrTopCoord) && field.pick(leftOrTopCoord) != Field::None)
                return false;
 
            CellCoord rightOrBottomCoord = vertical
                ? CellCoord(coord.x + 1, coord.y + i)
                : CellCoord(coord.x + i, coord.y + 1);
            if (field.valid(rightOrBottomCoord) && field.pick(rightOrBottomCoord) != Field::None)
                return false;
        }
 
        return true;
    }

@SmallEvil · 10.03.2022, 17:32

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

Выдрал из старого кода

Выглядит прилично )

Никогда не писал морской бой, аж обидно как-то

Croessmah · 10.03.2022, 17:41

Не по теме:

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

Выглядит прилично

Ага, аж плакать хочется. :D

@SmallEvil · 10.03.2022, 17:44

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

int fastAttempts = 0;
while (++fastAttempts < 50)

а что это за магическое число ? 50 ?

Не по теме:

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

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

Не по теме:
Сообщение от SmallEvil
Выглядит прилично
Ага, аж плакать хочется. :D

По сравнению с тутошнимы попытками, еще приемлемо )

Croessmah · 10.03.2022, 17:53

Не по теме:

SmallEvil, это было какое-то экспериментально подобранное число. Не спрашивайте. Что-то вроде "срабатывание в 99.5% из миллиона расстановок".

@alexu_007 · 11.03.2022, 18:23

Иногда расстановка кораблей может зайти в тупик, если случайным образом выбирается 1-я клетка, а для продолжения корабля нет места - уже занято другими кораблями. Алгоритм пробует рэндомом продлить корабль вправо-влево-вверх-вниз, у него не получается, т.к. нет свободного пространства. И через 50 (например) безуспешных попыток меняется положение первой клетки - что-бы прога не висла.

Как вариант. Сам писал морской бой, но размером 15х15 и с "гнутыми" кораблями.

@SmallEvil · 11.03.2022, 18:41

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

Как вариант. Сам писал морской бой, но размером 15х15 и с "гнутыми" кораблями.

ИИ есть ?

Croessmah · 11.03.2022, 20:02

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

Иногда расстановка кораблей может зайти в тупик, если случайным образом выбирается 1-я клетка, а для продолжения корабля нет места - уже занято другими кораблями.

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

@SmallEvil · 11.03.2022, 20:16

Croessmah, вспомнился анекдот

Работал в одном банке программист, все было отлично, но в один прекрасный день пропал. День на работе нету, два... Директор банка узнал - велел сыскать. Поехали к программисту на дом. Дверь на звонки не открывают, но за дверью слышен плеск воды. Решили ломать дверь. Заходят в квартиру - программист в очень жалком виде сидит в ванной: синий, на голове почти нет волос, в руке сжимает бутылку от шампуня. Вырвали у него бутылку - на ней инструкция:
Инструкция по применению шампуня :
- Намочить голову,
- Выдавить небольшое количество шампуня на руку,
- Растереть шампунь по волосам,
- Смыть водой,
- Повторить.

@alexu_007 · 11.03.2022, 20:35

Искусственным интеллектом в основном занимаются те, у кого проблемы с естественным... шутка. Непрофессионал-самоучка не может написать ИИ. Вот так выглядит расстановка кораблей человеком. Правильность расстановки проверяется. При ошибке (касании кораблей углами или неправильном количестве палуб) вместо палуб рисуются красные крестики:

@alexu_007 · 11.03.2022, 20:42

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

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

В тупик заходит. Например, если расположить таким образом 4-х и 3-х палубный корабли, то второй трёхпалубный не получится начать в левом нижнем углу, хотя там есть две свободные клетки:

Croessmah · 11.03.2022, 20:51

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

то второй трёхпалубный не получится начать в левом нижнем углу

Туда горизонтально поместится двухпалубный.

И вообще не понятно, почему трехпалубный надо размещать именно там

@alexu_007 · 11.03.2022, 21:06

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

Туда горизонтально поместится двухпалубный.
И вообще не понятно, почему трехпалубный надо размещать именно там

Потому что компьютер выбирает случайную клетку и ставит туда 4-х палубный. Затем выбирает другую случайную клетку и ставит 3-х палубный. Затем третью случайную клетку и ставит второй 3-х палубный. Компьютер "не понимает", почему 3-х палубный нельзя разместить именно там. Нужно или усложнять алгоритм, вводя проверку наличия достаточного количества свободных клеток именно в этом месте. Или после 50-ти попыток вкрячить 3-х палубный именно туда - всё же бросить это дело и выбрать другую начальную клетку.

@John Prick · 11.03.2022, 21:29

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

Или после 50-ти попыток вкрячить 3-х палубный именно туда - всё же бросить это дело и выбрать другую начальную клетку.

Не очень понятно, зачем 50 раз пытаться вкорячить? Как будто после первой неудачной может возникнуть второй шанс?

@SmallEvil · 11.03.2022, 21:49

15*15. Это ж сколько в него играть то нужно, на бумаге если. Час наверное

Чего вы все накинулись на Croessmah ?
Ну накосячил когда то парниша ) подумаешь )

alexu_007, поделись своим алгоритмом расстановки, ТСу точно будет интересно, да и мне уже тоже )

Croessmah · 11.03.2022, 21:57

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

Чего вы все накинулись на Croessmah ?
Ну накосячил когда то парниша ) подумаешь )

Кто накинулся? Кто накосячил? Где?

@alexu_007 · 11.03.2022, 22:06

Сообщение от John Prick

Не очень понятно, зачем 50 раз пытаться вкорячить? Как будто после первой неудачной может возникнуть второй шанс?

Он 50 раз пытается не "вкорячить весь корабль", а вставить одну палубу. Рэндом есть рэндом, он может и 5 раз пытаться вставить туда, куда нельзя, хотя есть другие направления, куда можно. 50 для гарантии, что он постарался как следует, но не смог.

Но это только моё предположение. Для чего на самом деле у автора алгоритма число 50, я не знаю.

Croessmah · 11.03.2022, 22:26

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

Он 50 раз пытается не "вкорячить весь корабль", а вставить одну палубу.

Кто пытается вкорячить одну палубу?

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

Но это только моё предположение. Для чего на самом деле у автора алгоритма число 50, я не знаю.

Понаписал:

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
    static std::vector<Ship> placeRandomShips(Field& field)
    {
        std::vector<Ship> ships;//<-- сюда запишутся все корабли
        for (int shipSize = 4; shipSize > 0; --shipSize) //Идем по кораблям, начиная с самого большого
        {
            const int shipsCount = (4 - shipSize) + 1;//количество кораблей (1 4-ех палубный, 2 3-ех палубных и т.д.)
            for (int i = 0; i < shipsCount; ++i)
            {
                bool isVertical = !!(rand() & 1);//Рандомно выбираем направление
                CellCoord coord;
 
                while (!(coord = placeRandomShip(field, shipSize, isVertical)).valid())//Вкорячиваем с заданным направлением
                    isVertical = !isVertical;//Если не получилось, меняем ориентацию
 
                ships.push_back({coord , shipSize, isVertical});
            }
        }
 
        return ships;
    }
 
    static CellCoord placeRandomShip(Field& field, int shipSize, bool vertical)
    {
        int fastAttempts = 0;
        while (++fastAttempts < 50)//50 попыток поставить корабль в рандомной точке
        {
            //генерируем верхнюю левую палубу корабля
            const int x = rand() % (vertical ? field.width() : field.width() - shipSize);
            const int y = rand() % (vertical ? field.height() - shipSize : field.height());
            const CellCoord coord{ x, y };
 
            if (placeShip(field, coord, shipSize, vertical))//Пытаемся вкорячить
                return coord;//Возвращаем верхнюю левую палубу корабля
        }
 
        //Если все 50 попыток провалились, то генерируем массив из всех клеток (надо бы отсеять занятые)
        std::vector<CellCoord> freeCells;
        freeCells.reserve(field.width() * field.height());
        for (int i = 0; i < field.width(); ++i)
            for (int j = 0; j < field.height(); ++j)
                freeCells.push_back(CellCoord(i, j));
        //перемешиваем его
        std::shuffle(freeCells.begin(), freeCells.end(), std::mt19937());
 
        //и пытаемся вкорячить хоть куда-то
        for (CellCoord cell : freeCells)
            if (placeShip(field, cell, shipSize, vertical))
                return cell;
 
        return InvalidCell();
    }
 
    static bool placeShip(Field& field, CellCoord coord, int shipSize, bool vertical)
    {
        //Если нельзя вкорячить, возвращаемся
        if (!mayBePlaced(field, coord, shipSize, vertical))
            return false;
        
        //Иначе размещаем корабль на поле
        for (int i = 0; i < shipSize; ++i)
        {
            CellCoord shipCoord = vertical 
                ? CellCoord(coord.x, coord.y + i) 
                : CellCoord(coord.x + i, coord.y);
            field.set(shipCoord, Field::Ship);
        }
 
        return true;
    }
 
    static bool mayBePlaced(const Field& field, CellCoord coord, int shipSize, bool vertical)//сделано максимально тупо
    {
        //проходим по всем клеткам корабля и смотрим, что все они свободны
        for (int i = 0; i < shipSize; ++i)
        {
            CellCoord shipCoord = vertical
                ? CellCoord(coord.x, coord.y + i)
                : CellCoord(coord.x + i, coord.y);
 
            if (field.pick(coord) != Field::None)
                return false;
        }
 
        //проходим по всем клеткам корабля и соседним с ним и смотрим, что все они свободны
        for (int i = -1; i < shipSize + 1; ++i)
        {
            CellCoord centerCoord = vertical
                ? CellCoord(coord.x, coord.y + i)
                : CellCoord(coord.x + i, coord.y);
            if (field.valid(centerCoord) && field.pick(centerCoord) != Field::None)
                return false;
 
            CellCoord leftOrTopCoord = vertical
                ? CellCoord(coord.x - 1, coord.y + i)
                : CellCoord(coord.x + i, coord.y - 1);
 
            if (field.valid(leftOrTopCoord) && field.pick(leftOrTopCoord) != Field::None)
                return false;
 
            CellCoord rightOrBottomCoord = vertical
                ? CellCoord(coord.x + 1, coord.y + i)
                : CellCoord(coord.x + i, coord.y + 1);
            if (field.valid(rightOrBottomCoord) && field.pick(rightOrBottomCoord) != Field::None)
                return false;
        }
 
        return true;
    }

@SmallEvil · 11.03.2022, 22:37

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

while (++fastAttempts < 50)//50 попыток поставить корабль в рандомной точке

Это уже все давно поняли.
Как то недавно, я по генерации морского поля боя, предлагал, сделать массив из пустых клеток, перемешать их, и оттуда брать их для попытки расстановок кораблей, при удаче, использованные, зянятые и непригодные, удялять. С таким подходом не нужно никаких 50-100 попыток на расстановку, и не будет попыток в те же самые клетки пытаться поставить корабль.

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

Кто накинулся? Кто накосячил? Где?

Вот про этот косяк и и написал )

Добавлено через 2 минуты
А вообще, в широком смысле задача довольно интересная.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

Croessmah
	10.03.2022, 17:53
	Не по теме: SmallEvil, это было какое-то экспериментально подобранное число. Не спрашивайте. Что-то вроде "срабатывание в 99.5% из миллиона расстановок". 0

@alexu_007 736 / 700 / 110 Регистрация: 29.05.2015 Сообщений: 4,268
	11.03.2022, 18:23
	Иногда расстановка кораблей может зайти в тупик, если случайным образом выбирается 1-я клетка, а для продолжения корабля нет места - уже занято другими кораблями. Алгоритм пробует рэндомом продлить корабль вправо-влево-вверх-вниз, у него не получается, т.к. нет свободного пространства. И через 50 (например) безуспешных попыток меняется положение первой клетки - что-бы прога не висла. Как вариант. Сам писал морской бой, но размером 15х15 и с "гнутыми" кораблями. 0

@alexu_007 736 / 700 / 110 Регистрация: 29.05.2015 Сообщений: 4,268
	11.03.2022, 20:35
	Искусственным интеллектом в основном занимаются те, у кого проблемы с естественным... шутка. Непрофессионал-самоучка не может написать ИИ. Вот так выглядит расстановка кораблей человеком. Правильность расстановки проверяется. При ошибке (касании кораблей углами или неправильном количестве палуб) вместо палуб рисуются красные крестики: Миниатюры 0

@SmallEvil 4086 / 2975 / 813 Регистрация: 29.06.2020 Сообщений: 11,000
	11.03.2022, 21:49
	1515. Это ж сколько в него играть то нужно, на бумаге если. Час наверное Чего вы все накинулись на Croessmah* ? Ну накосячил когда то парниша ) подумаешь ) alexu_007, поделись своим алгоритмом расстановки, ТСу точно будет интересно, да и мне уже тоже ) 0