Я работаю над созданием простой версии Connect 4. игра.
Вот мой первый черновик кода. Я хотел бы получить отзывы по этому поводу, а также требовать изменения для следующих вопросов:
- Добавьте немного интеллекта в игроков, чтобы оптимально подобрать колонну.
- Как вы сделаете игру универсальной, чтобы в ней можно было проверять 16 точек в строке / столбце / диагонали
- Как вы справитесь с огромной сеткой?
Что касается item3, я думаю, что, поскольку я не храню всю сетку, мой подход является масштабируемым. Буду признателен за любые рекомендации или отзывы.
class Connect4 {
vector <pair<int, map< pair<int,int>,int > > > rows;
vector <pair<int, map< pair<int,int>,int > > > cols;
vector <pair<int, map< pair<int,int>,int > > > diag;
int r;
int c;
int player;
public:
Connect4 (int rr, int cc):r(rr), c(cc){
rows = vector <pair<int, map< pair<int,int>,int > > > (rr);
cols = vector <pair<int, map< pair<int,int>,int > > > (cc);
diag = vector <pair<int, map< pair<int,int>,int > > > (min (rr,cc));
}
int move(int row, int col, int player){
int score = (player ==1)?1:-1; // count player-1 socres with positive and player-2 with negative numbers
rows[row].first +=score;
rows[row].second[{row,col}]=score;
if (abs(rows[row].first) ==4 && isValid(rows[row].second) )
return player;
cols[col].first += score;
cols[col].second[{row,col}]=score;
if (abs(cols[col].first) ==4 && isValid(cols[col].second) )
return player;
if(row ==col+2){
diag[0].first +=score;
if (abs(diag[0].first) ==4 ) //if the score is 4 no extra checking is needed
return player;
} else if (row ==col+1) {
diag[1].first += score;
if (abs(diag[1].first) ==4 && isValid(diag[1].second) )
return player;
} else if (row ==col) {
diag[2].first += score;
if (abs(diag[2].first) ==4 && isValid(diag[2].second) )
return player;
} else if (row+1 ==col) {
diag[3].first += score;
if (abs(diag[3].first) ==4 && isValid(diag[3].second) )
return player;
} else if (row+2 ==col) {
diag[4].first += score;
if (abs(diag[4].first) ==4 && isValid(diag[4].second) )
return player;
} else if (row+3 ==col) {
diag[5].first += score;
if (abs(diag[5].first) ==4 )
return player;
}
}
bool isValid(map<pair<int,int>, int> verify) {
int cnt=1;
map<pair<int,int>, int>::iterator itr = verify.begin();
int prev= itr->second;
itr++;
for (;itr!= verify.end(); ++itr){
int score = itr->second ;
if(prev == score){
cnt++;
if(cnt ==4)
return true;
} else {
cnt=0;
}
prev = score;
}
return (cnt>=4);
}
};
Здесь обсуждается логика вычисления диагонали: в сетке 6×7 мы можем получить диагональный балл> = 4 только в следующих матричных индексах:
Если у нас одинаковые оценки в следующих (X, Y):
- (2,0), (3,1), (4,2), (5,3) -> диаг[0]
- (1,0), (2,1), (3,2), (4,3), (5,4)
- (0,0), (1,1), (2,2), (3,3), (4,4), (5,5)
- (0,1), (1,2), (2,3), (3,4), (4,5), (5,6)
- (0,2), (1,3), (2,4), (3,5), (4,6)
- (0,3), (1,4), (2,5), (3,6) -> диаг[6]
1 ответ
Именование вещей
Избегайте использования односимвольных имен переменных, если только они не используются очень часто, например i
для индекса цикла. Учитывать r
и c
, даже если вы думаете, что это как-то связано с координатами, это положение или размер? Я бы лично использовал width
и height
вот как однозначные названия размеров сетки.
Обратите внимание, что в списке инициализаторов конструктора для параметра можно использовать то же имя, что и для переменной-члена, например:
int width;
int height;
public:
Connect4(int width, int height): width(width), height(height) {...}
Не всем нравится такой стиль; некоторые люди хотят устранить неоднозначность между параметром и переменной-членом, написав:
Connect4(int width_, int height_): width(width_), height(height_) {...}
И вы также видите проекты, в которых все переменные-члены имеют префикс m_
, так это будет выглядеть так:
int m_width;
int m_height;
public:
Connect4(int width, int height): m_width(width), m_height(height) {...}
Другие имена переменных, которые можно улучшить:
cnt
->count
itr
->it
(последнее более идиоматично)diag
->diagonal
verify
->line
Создать enum class
для возможного содержимого ячейки сетки
An enum
, а еще лучше enum class
, позволяют заранее указать возможные значения ячейки сетки с именами вместо целых значений. Предлагаю вам написать следующее:
class Connect4 {
enum class Cell: char {
EMPTY,
PLAYER1,
PLAYER2,
};
};
Вышеупомянутое также явно устанавливает тип в char
, поэтому для его хранения необходим только один байт.
Хранение сетки
Есть несколько ошибок в том, как вы храните сетку. Используемая вами структура данных очень неэффективна как для больших, так и для малых сеток, а также для проверки условий выигрыша. Лучше всего использовать один вектор для хранения всех ячеек сетки:
std::vector<Cell> grid;
Это обеспечивает очень компактную компоновку в памяти, а для поиска произвольной ячейки сетки процессору достаточно выполнить одно умножение и два сложения, что очень дешево для современных процессоров, и, как уже упоминал Тоби Спейт, для проверки горизонтальности , вертикальные и диагональные линии тоже очень просты; просто вычислите начальную точку, конечную точку и шаг для использования, а затем на каждом шаге по линии нужно делать только одно добавление, чтобы найти ячейку сетки для проверки.
Я бы добавил функцию для получения ссылки на ячейку сетки по ее координатам, например:
Cell &at(int row, int col) {
return grid[row * c + col];
}
Работа с огромными сетками
Первое, что следует учитывать при работе с огромными сетками / массивами / матрицами, — будет ли структура данных заполнена плотно или редко. Легко подумать, что он должен быть разреженным, ведь вы начинаете с полностью пустой сетки. Но учтите, что во время финальной игры Connect 4 вы, вероятно, использовали более половины ячеек сетки, поэтому плотная сетка, вероятно, лучший способ сохранить состояние.
С указанным выше Cell
типа, вы используете один байт на ячейку сетки. Поскольку у ячейки есть только три возможных состояния, вы можете относительно легко упаковать до пяти ячеек в байт (поскольку 3⁵ = 243) за счет некоторых дополнительных вычислений при чтении / записи данной ячейки. При этом сетка 100 000 на 50 000 умещается чуть меньше гигабайта.
Вы также можете подумать о том, чтобы как-то сжать сетку, но еще раз подумайте, как выглядит игра connect 4 в конце. Наверняка не будет серий из более чем 3 ячеек одного цвета подряд, иначе уже был бы победитель. И вы редко видите повторяющийся узор. Так что это в основном похоже на шум, который не сжимается. Возможно, для сжатия последовательности ходов, сделанных игроками, можно было бы использовать прогнозирующее кодирование, но сжатые данные, скорее всего, не будут в форме, подходящей для отображения сетки и проверки условий выигрыша.
Единственный вариант, который я вижу для значительного уменьшения объема данных, — это учесть, что большая часть ячеек сетки, в которых игроки уже играли, никогда не будет частью 4 связанных ячеек одного цвета. Например, вы можете пометить все ячейки, которые удалены более чем на 3 позиции (как по горизонтали, так и по вертикали) от любых пустых ячеек, как «мертвые». Таким образом, в принципе, вместо того, чтобы хранить $ mathcal {O} (W cdot H) $, вам нужно только хранить $ mathcal {O} (W + H) $ ячейки сетки. Но это будет означать, что вы больше не можете точно показать все сделанные до сих пор ходы.
Проверка условия выигрыша
К сожалению, ваша идея вести счет за каждую строку не очень полезна. Довольно легко создать линию, в которой общее количество очков будет равно четырем, но нет 4 последовательных ячеек с одним и тем же игроком, например, представляющих игроков 1 и 2 с O
и X
соответственно:
X O O X O O X O O X O O
Есть 8 фигур игрока 1 и 4 игрока 2, поэтому ваш способ подсчета очков приведет к 4
или же -4
, но явно ни один игрок еще не выиграл. Однако, если игрок 1 добавит еще два O
в эту строку:
X O O X O O X O O X O O O O
Тогда у игрока 1 4 подряд, но «счет линии» будет 6
или же -6
. Так что линейный счет бесполезен.
Простое решение — просто всегда проверять область 9×9, окружающую последнее движение, на наличие горизонтальной, вертикальной или диагональной линии с 4 в ряд. Это может показаться немного расточительным в самом начале игры, когда было сделано всего несколько ходов, в долгосрочной перспективе это не имеет особого значения.
Спасибо за ответ. Просто небольшой комментарий по поводу «Проверка условия выигрыша». Функция isValid () проверяет, набрали ли подряд 4 одинаковые игроки подряд, столбец или диагональ. И я намеренно сначала проверил, равен ли счет 4 или -4, а затем вызвал isValid (). Другими словами, isValid вызывается тогда и только тогда, когда abs (score_value) равен 4
— Ашкан