Предыдущие части: Какую память выделить, Структура программы, Пишем Сапёра на С + SDL
Код для этой части находится в ветке field на github. Вы можете смотреть там все файлы онлайн и также скачать зип-архив всей ветки.
Здесь мы обсудим: представление данных, адресацию в поле, генератор случайных чисел и заполнение поля.
Представление данных
Это уже было:
Но появляются дополнительные мысли.
На поле нужно отображать, сколько мин находится вокруг открытой клетки. Чтобы получить это число, для каждой клетки нужно проверить 8 окружающих клеток. И делать так при каждой перерисовке? Почему бы и нет, быстродействия нам хватит.
Но всё же, раз мины на поле неподвижны, можно всё рассчитать только один раз при генерации поля, и просто хранить эти числа для каждой клетки. Только вот где хранить?
Можно создать ещё один массив, и записывать числа туда.
А можно вспомнить, что в нашем представлении данных свободны три бита. Попробовать использовать их?
Увы, в три бита влезет максимум число 7, а нам нужно 8. Тогда нельзя ли освободить один бит?
Например, бит "неправильный флажок" это когда флажок поставлен там, где нет мины. Значит, бит "неправильный флажок" можно заменить на сочетание двух битов: "флажок = 1" + "мина = 0".
Проблема решена. Только, чтобы было удобнее работать с числами, количество мин мы разместим в младших битах, а состояния в старших:
Для работы с битовыми масками зададим с помощью #define соответствующие константы, для наглядности в двоичном виде. Заодно добавим константу MAX_FIELD_SIZE для максимального размера игрового поля:
Допустим, в переменной "f" хранится содержимое одной клетки поля.
- Сколько мин (уже посчитанных) вокруг этой клетки? f & F_NUMBER
- В клетке есть мина? f & F_MINE
- Клетка закрыта или открыта? f & F_CLOSED
- На клетке стоит флажок? f & F_FLAG
- На клетке стоит знак вопроса? f & F_QUESTION
- Флажок в клетке был поставлен неправильно? f & (F_FLAG | F_MINE) == F_FLAG, или: f & F_FLAG && !(f & F_MINE)
Как будем менять значения в клетке:
- Записать количество мин (count): f &= ~F_NUMBER; f |= count. На деле номера будут заполняться только один раз, так что достаточно f |= count.
- Поставить мину: f |= F_MINE
- Закрыть клетку: f |= F_CLOSED
- Открыть клетку: f &= ~F_CLOSED
- Поставить/убрать другие биты: аналогично
(Принципы бинарных операций и их синтаксис описаны в сборнике Битовые операции.)
Адресация в поле
У нас есть одномерный массив field, на который нужно отображать матрицу размером W*H. Как это сделать? Внутри массива каждые W байт это одна строка матрицы. Значит, если у клетки координаты (x, y), то адрес этой клетки внутри массива вычисляется так:
int addr = y * width + x;
где width это ширина матрицы. Такую адресацию мы уже применяли в играх Robots, 5K Tetris и Питон на Питоне.
Генератор случайных чисел
Для расстановки мин на поле нужны случайные координаты "x" и "y". В языке C есть функции rand() и srand(), которые находятся в библиотеке stdlib.
#include <stdlib.h>
Функция rand() возвращает случайное целое число в пределах от 0 до предопределённой константы RAND_MAX. Значение константы зависит от каких-то внешних условий, но не меньше чем 32767.
При каждом запуске программы функция rand() будет генерировать одну и ту же последовательность чисел, что нам не подходит.
Функция srand() служит для того, чтобы начать новую последовательность случайных чисел. Для этого в неё нужно передать параметр – любое целое число, который порождает новую последовательность. Мы можем, допустим, передать 100, но так проблема не решится. Передавая один и тот же параметр в srand(), мы всё равно порождаем одну и ту же последовательность. Передаваемый параметр должен быть случайным, то есть можно получить его от rand()... ой постойте, но ведь rand() пока тоже выдаёт одно и то же.
В общем, в качестве именно случайного параметра чаще всего (потому что проще) берут текущее время. Для этого нам понадобится функция time(), а описана она в
#include <time.h>
time(0) возвращает нам количество секунд, прошедших с начала эпохи Unix (1 января 1970 года). Значит, при каждом новом запуске программы, если успела пройти хотя бы одна секунда, это число будет другим.
srand(time(0));
Это надо сделать только один раз в программе.
Теперь у нас проблема: координата "x" должна находиться в диапазоне 0..width, координата "y" в диапазоне 0..height. Но rand() возвращает числа в своём диапазоне. Что делать? Неидеальный, но самый простой способ: взять остаток от деления rand() на width или height.
Если диапазон задан как 0..width, то rand() % width будет давать случайное число 0..width-1. Но нам это и надо, потому что координата "x" в массиве меняется от 0 до width-1. Аналогично с координатой "y".
Для сокращения кода и на случай, если захочется доработать алгоритм, сделаем свою функцию rnd() с аргументом:
Заполнение поля
Сделаем функцию init_field() для заполнения поля минами. Функция принимает на вход: указатель на поле, ширину и высоту поля, количество мин. Пока не будем проверять, какие есть размеры и сколько мин в классическом Сапёре. Эмпирически количество мин это 1/6 от площади поля.
Заполнение проходит в три этапа:
- Заполнить все элементы поля битовой маской F_CLOSED, то есть "пустая закрытая клетка".
- Случайно выбирая координаты, создать на поле мины в количестве mine_count, объединяя содержимое поля с маской F_MINE.
3. Теперь посчитаем количество мин по клеткам.
Первоначально планировался тупой алгоритм: перебрать каждую клетку и вокруг неё перебрать 8 соседних клеток.
Но через некоторое время пришло осознание, что когда мы ставим мину на поле, мы уже знаем, в какой клетке она стоит. Мину окружают 8 клеток, и очевидно, что данная мина увеличивает на 1 общее количество соседних мин в этих клетках.
Так что теперь не надо перебирать все клетки. Ставим мину, а потом в соседних 8 клетках от мины увеличиваем значение на 1.
Немного поясню код. mine_addr это уже вычисленное смещение в массиве для мины. Вставка do ... while(field[mine_addr] & F_MINE) нужна для того, чтобы мины не ставились на одно и то же место. Если по вычисленному адресу уже есть мина, то случайные координаты вычисляются заново.
Затем, поставив мину в адрес, мы занимаемся соседними клетками. Чтобы получить клетку на 1 строку выше или ниже, мы от адреса отнимаем или прибавляем width. Чтобы получить клетку левее или правее, отнимаем или добавляем 1. Итого 8 соседних клеток это комбинации смещений:
- field[mine_addr - width - 1], field[mine_addr - width], field[mine_addr - width + 1]
- field[mine_addr - 1], field[mine_addr + 1]
- field[mine_addr + width - 1], field[mine_addr + width], field[mine_addr + width + 1]
Вот в этих клетках счетчик соседних мин увеличивается на 1, так как все они соседствуют с этой миной.
Все эти присвоения обёрнуты в условия, которые проверяют корректность координат. Т.е. если клетка стоит на краю поля, у нее может не быть соседа сверху, снизу, слева или справа.
До графики не добрались. На самом деле графическая отрисовка поля уже сделана в файле minesweeper.c, но разбор кода будем делать в следующей части, так как его слишком много. Также написана функция print_field() для текстового отображения поля:
На этом пока всё. В следующем выпуске подробно разберём работу с указателями и графические функции.
Читайте дальше: Указатели и графика
