Возможно ли избежать ошибку чтения в массиве если алгоритм задействует ячейку которой нет?

Question

[Colinp]

Привет! Суть ошибки такая. Я делаю симуляцию клеточного аппарата "Жизнь". При исполнении алгоритма, который меняет состояние клетки, он проверяет ячейку которой нет (не выделена память). Что в таком случае стоит сделать? Стоит ли выделить массив больше дабы избежать ошибки?

Некоторое пояснение:
Алгоритм проходит по двумерному массиву, к примеру 5x5. И при исполнении, когда он находится на ячейке к примеру [0][0], то он проверяет ячейки [-1][0] и т.п. Т.е пытается получить доступ фактически ни к чему.

Что в этом случае будет сделать легче или разумнее? Изучаю C++ некоторое время и поэтому вместо копирования с чего-либо решил спросить у комьюнити хабра. Заранее спасибо, с радостью приму любую критику!

Код тут

#define EMPTY_CELL ' '
#define CLAIM_CELL '#'

#include <cstdio>
#include <windows.h> //смешная библиотека, ничего не понимаю


const int cols = 5, rows = 5;
const bool isInfinit = true;
int steps = 25;
const int delayTime = 1000;

void Log(const char* msg) {
    printf(msg);
    printf("\n");
}// а
void LogPrefers() {
    printf("PREFERS: \n");
    printf("\t cols %d\n", cols);
    printf("\t rows %d\n", rows);
    printf("\t infinity %d\n", isInfinit);
    printf("\t steps %d\n", steps);
    printf("\t delay %d\n", delayTime);
}

int main(int argc, char* argv[]) {
    // Initialize simulation field
    LogPrefers();
    Log("Start initializing <?");
    char** field = new char* [cols];
    for (size_t i = 0; i < cols; ++i) {
        field[i] = new char[rows];
    }
    Log("Memory initialized <!");
    Log("Initializing by fill <?");
    for (size_t i = 0; i < cols; ++i) {
        for (size_t k = 0; k < rows; ++k) {
            field[i][k] = ' ';
        }
    }
    field[2][2] = '#';
    Log("Memory initialized <!");
    Log("Start simulation <?");
    Log("Started <!");
    // Simulation
    do {
        int temp = 0;
        for (size_t i = 0; i < cols; ++i) {
            for (size_t k = 0; k < rows; ++k) { // Господи, заработай пожалуйста с первого раза, аминь
                // Проверка соседей вокруг клетки.
                if (field[i - 1][k - 1] != NULL && field[i - 1][k - 1] == CLAIM_CELL) temp += 1;
                else if (field[i][k - 1] != NULL && field[i - 1][k - 1] == CLAIM_CELL) temp += 1;
                else if (field[i + 1][k - 1] != NULL && field[i - 1][k - 1] == CLAIM_CELL) temp += 1;
                else if (field[i - 1][k] != NULL && field[i - 1][k - 1] == CLAIM_CELL) temp += 1;
                else if (field[i + 1][k] != NULL && field[i - 1][k - 1] == CLAIM_CELL) temp += 1;
                else if (field[i + 1][k + 1] != NULL && field[i - 1][k - 1] == CLAIM_CELL) temp += 1;
                else if (field[i][k + 1] != NULL && field[i - 1][k - 1] == CLAIM_CELL) temp += 1;
                else if (field[i - 1][k + 1] != NULL && field[i - 1][k - 1] == CLAIM_CELL) temp += 1;
                if (temp == 3 || temp == 2) {
                    field[i][k] == '#';
                }
                else {
                    field[i][k] == ' ';
                }
                temp = 0; // Сбрасываем счётчик!111
            }
        }
        for (size_t i = 0; i < cols; ++i) {
            printf("\n");
            for (size_t k = 0; k < rows; ++k) {
                printf("%c", field[i][k]);
            }
        }
        steps -= 1;
        //Sleep(delayTime);
    } while (steps > 0 || isInfinit);

    // Free ramm from simulation field  linux suck
    Log("! END !");
    for (int i = 0; i < cols; ++i) {
        delete[] field[i];
    }
    delete[] field;

    return 0;
}

Comments

[Acaunt]

Я когда делал свой клеточный автомат, сделал мир не "плоским", а закальцевал его. А именно связал верх и низ, лево и право.

Чтобы это обеспечить и уменьшить количество проверок, я создал класс Cell, который хранит bool value и bool* ptr[8].

Когда создал массив клеток мне нужно было просто записать в массив указателей соседей.

А потом я ещё создал класс Rules он представлял интерфейс для обеспечения правил мира. Так как клеточный автомат может быть с разными правилами. И просто новые правила наследовал от него и реализовал уже в них. (Например количество соседей только сверху, снизу и по бокам, или количество соседей только по углам).

П.С. Вместо закрашивания клетки #, я использовал []. Так клетки выглядят более квадратными и более читабельными.

П.П.С. ещё нужны два похожих массива хранящих закрашенные клетки. Это будет как буфер кадров. Иначе закрасив одну клетку следующие будут учитывать новую клетку и всё сломается.

[Colinp]

Acaunt, хочу спросить а почему именно bool* ptr[8]; ? Вместо cell* ptr[8]

[Acaunt]

Colinp, потому что это масив указателией именно на переменные bool value, которые хранятся именно в соседних ячейках. Так скажем без посредника. Чтобы не писать например:

Cell a; // типо ячейка у которой хотим посмотреть соседей
(*a.ptr[2]).value;

А например так писать:
*a.ptr[2];

[Acaunt]

Colinp, если хочешь могу завтра показать свой код

[Acaunt]

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

Game_of_life

#include <iostream>
#include <stdint.h>
#include <thread>
#include <chrono>
#include <random>

class Cell {
private:
    bool value;
    bool* ptr[8];

public:
    Cell() : value(std::rand() % 2) {}

    operator bool() const {
        return value;
    }

public:
    friend class Rules;
    template<size_t Y, size_t X, class type_rules>
    friend class Game_of_life;
};

class Rules {
public:
    virtual bool is_life(const Cell& cell) = 0;

protected:
    bool check(const Cell& cell, uint8_t index) {
        return *cell.ptr[index];
    }
};

class Standard_rules : public Rules {
public:
    bool is_life(const Cell& cell) override {
        uint8_t count = 254;

        for (uint8_t i = 0; i < 8; ++i) {
            count += check(cell, i);
        }
        return (cell && count < 2) || (!cell && count == 1);
    }
};

template<size_t Y, size_t X, class type_rules = Standard_rules>
class Game_of_life {
private:
    type_rules rules;
    bool buffer;
    Cell board1[Y][X];
    Cell board2[Y][X];

public:
    Game_of_life()
        : buffer(true) {
        init(board1);
        init(board2);
    }

    void draw() const {
        draw_(buffer ? board1 : board2);
    }

    void swap_buffer() {
        buffer ? swap(board2, board1) : swap(board1, board2);
    }

private:
    void draw_line() const {
        for (size_t i = 0; i <= X; ++i) {
            std::cout << "##";
        }

        std::cout << std::endl;
    }

    void draw_(const Cell(*board)[X]) const {
        draw_line();

        for (size_t y = 0; y < Y; ++y) {
            std::cout << '#';

            for (size_t x = 0; x < X; ++x) {
                std::cout << (board[y][x] ? "[]" : "  ");
            }

            std::cout << '#' << std::endl;
        }

        draw_line();
    }

    void init_cell(Cell(*board)[X], size_t y, size_t x) {
        size_t start_y = (y == 0 ? Y : y) - 1;
        size_t start_x = (x == 0 ? X : x) - 1;
        size_t end_y = y == Y - 1 ? 0 : (y + 1);
        size_t end_x = x == X - 1 ? 0 : (x + 1);

        board[y][x].ptr[0] = &board[start_y][start_x].value;
        board[y][x].ptr[1] = &board[start_y][x].value;
        board[y][x].ptr[2] = &board[start_y][end_x].value;

        board[y][x].ptr[3] = &board[y][start_x].value;
        board[y][x].ptr[4] = &board[y][end_x].value;

        board[y][x].ptr[5] = &board[end_y][start_x].value;
        board[y][x].ptr[6] = &board[end_y][x].value;
        board[y][x].ptr[7] = &board[end_y][end_x].value;
    }

    void init(Cell(*board)[X]) {
        for (size_t y = 0; y < Y; ++y) {
            for (size_t x = 0; x < X; ++x) {
                init_cell(board, y, x);
            }
        }
    }

    void swap(Cell(*first)[X], Cell(*second)[X]) {
        for (size_t y = 0; y < Y; ++y) {
            for (size_t x = 0; x < X; ++x) {
                first[y][x].value = rules.is_life(second[y][x]);
            }
        }

        buffer = !buffer;
    }
};

int main() {
    std::srand(time(0));
    
    Game_of_life<19,19, Standard_rules> play;

    for (;;) {
        play.draw();
        play.swap_buffer();
 
       std::this_thread::sleep_for(std::chrono::milliseconds(500));
        system("cls);
    }
    
    return 0;
}

Answer 1

[Wataru]

Для игры "жизнь" есть несколько вариантов:
1) Увеличить поле на 2 клетки по каждому измерению, поле будет храниться с 1, а индексы 0 и n+1 - всегда будут пустыми. Потребление памяти это почти не увеличит, а код упростит.
2) Если соседние клетки считаются циклами, то можно границы области 3x3 пересечь с полем:

for (int nx = max(0, x-1); nx < min(x+2, n); ++nx) {
  for (int ny = max(0, y-1); ny < min(y+2, n); ++ny) {
    if (nx == x && ny == y) continue;
    // {nx, ny} - сосед в поле, обрабатываем его.
  }
}

Можно код чуть ускорить, предподсчитав границы.
3) Более читаемый, но чуть более медленный метод - явно проверять, а не за границей ли соседняя клетка:

for (int nx = x-1; nx <= x+1; ++nx) {
  for (int ny = y-1; ny <= y+1; ++ny) {
    if ((nx == x && ny == y) || nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
    // {nx, ny} - соседняя клетка.
  }
}

Я бы просто раздул поле - так код сильно проще.

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

Answer 2

[Сергей Соловьев]

Граничные значения обрабатывать особенным образом:
- Если это первая и последняя строка, то не берем в учет верхнюю или нижнюю строки соответственно
- Если это самый левый или правый столбец, то не берем в учет левый или правый (относительно текущего) столбец соответственно

Т.е. в каждый цикл дополнительно вставляются окаймляющие участки (для этих случаев)