Морской бой

@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 минуты
А вообще, в широком смысле задача довольно интересная.

Новые блоги и статьи Все статьи Все блоги /
Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .

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

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

@alexu_007 736 / 700 / 110 Регистрация: 29.05.2015 Сообщений: 4,274
	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