3

Игра жизнь. Разрешение: 1920х1080. Создается 2 одномерных массивов ширина х высота(1920х1080).

public static byte[] Map; //Для хранения данных о клетки старого поколения
public static byte[] NewMap; //Массива в которые на основе данных первого массива, помещается новая информация - Выжила ли клетка в новом поколении или нет.

В байтовой массиве. 0b_0001 - живая клетка. 0b_0000 - Мертвая клетка. Чтобы сгенерировать новое поколение нужно посчитать ближайших 8 соседей.

Правила Игры жизнь

  1. Если клетка живая и около нее 2 или 3 соседа, то клетка выживает и переходит в новое поколение (В массива NewMap), иначе клетка погибает от одиночества (<2) или же от перенаселения(>3).
  2. Если клетка мертва или около нее 3 соседа, то клетка рождается и появляется в новом поколении(В Массиве NewMap).

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

Код генерации случайного первого поколения

// Конструктор класса.
public GameEngine(int rows, int cols, int density = 25)
        {
            GameEngine.Rows = rows; // Кол-во строк
            GameEngine.Cols = cols; // Кол-во столбцов
            GameEngine.Map = new byte[Cols * Rows];
            GameEngine.NewMap = new byte[Cols * Rows];
            for (int y = 1; y < rows - 1; y++)
                for (int x = 1; x < cols - 1; x++)
                    Map[x + y * Cols] = (byte)(rnd.Next(2) == 0 ? 0b0001 : 0b0000);
        }

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

Код подсчета соседей

public void NewGeneration()
        {
            CountGeneration++;
            byte buf = 0;
            for (int y = 1; y < Rows - 1; y++)
                for (int x = 1; x < Cols - 1; x++)
                {
                    int pos = x + y * Cols;

                    buf = (byte)(Map[pos] << 3); 
// До битового сдвига живая клетка выглядит так 0b_0001. Чтобы сохранить данные о том живая клетка или нет нужно сдвинуть на 3 позиции вправо - 0b_1000. После этого 4 разряд хранит данные о том живая клетка или нет.
// а в оставшиеся разряды можно поместить данные о том сколько соседей вокруг данной клетки.
// То есть в текущий байт прибавляется ее соседи (пример вида соседа // 0b_0001 - Живая. 0b_0000 - Мертвая), после сложения текущий байт выглядит примерно так:
// 0b_1010 - Клетка живая и у нее 2 соседа.
// Все эти расчеты происходят через буфер. 
                    buf += Map[pos + Cols];
                    buf += Map[pos - Cols];
                    buf += Map[pos + 1];
                    buf += Map[pos - 1];   
                    if (buf < 4 || buf < 12){
                    buf += Map[pos - Cols - 1];
                    buf += Map[pos - Cols + 1];
                    buf += Map[pos + Cols + 1];
                    }              
                   
                    if (buf < 4 || buf < 12) buf += Map[pos + Cols - 1];

//После того как кол-во соседей просчитано, я использую "таблицу" значений после чего заношу новые данные в массив NewMap.
                    switch (buf)
                    {
                        case 0b_1010: //Клетка живая 2 соседа
                        case 0b_1011: //Клетка живая 3 соседа
                        case 0b_0011: //Клетка мертвая 3 соседа
                            NewMap[pos] = 0b_0001; break; // Клетка переходить в новое поколение
                        default: NewMap[pos] = 0b_0000; break; // Иначе клетка погибает в новом поколении
                    }
                }
            byte[] tmp = Map; // После того как новое поколение было просчитано нужно поменять местами NewMap и Map, чтобы в следующий раз высчитывать новое поколение на основе старого
            Map = NewMap;
            NewMap = tmp;
        }

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

Динамически нельзя менять массива Map иначе, для следующий клеток пойдет неправильный подсчет. Если взять только один массив и в 4 разряде изначально хранить данные о жизнь то чтобы получить сумму соседей в 3 оставшихся разрядов нужно либо сместить 4 разряд либо поделить на 8, так как изначально 0b_1000 нужно сложить и получить 0b_1001. И после еще раз пройтись по массиву и изменить его используя "таблицу"

Если у кого есть какие идеи по оптимизации данного кода, буду очень благодарен. Для подсчета нового поколения размером 1920х1080 уходить примерно 17мс

6
  • Здесь есть ошибка, если все 8 соседей будут 1, то результат будет 10000, то есть живая клетка с 8 соседями умрет. Ну и case надо бы дописать под все варианты. То получается как-то наполовину код про 8 соседей, наполовину про 4.
    – aepot
    30 окт 2022 в 20:02
  • Начните с того что buf за циклом, это не хорошо, компилятору будет проще оптимизировать код если объявите так byte buf = (byte)(Map[pos] << 3);.
    – aepot
    30 окт 2022 в 20:04
  • Нет, вы видать не до конца поняли мою реализацию. В сase прописаны значения при которых нужно изменить состояние клетки. default в case как раз для того чтобы остальные варианты отсеять. Насчет складывания 8 соседей. Получается что в бите в 0b0000_0001 - так выглядит живая клетка. Чтобы посчитать соседей и узнать живая клетка или нет, чтобы потом использовать case, нужно к buf присвоить данные о том живая клетка или нет поэтому мы сдвигаем на 3 разряда вправо, чтобы получить 0b0000_1000 и получается что остальные соседи 0b_0001, то есть можно спокойно сложить и получить готовый результат. 30 окт 2022 в 20:08
  • 8 в двоичной системе это 1000 а не 111. Я об этом. Вы портите данные, если конечно это имеет значение. 1000+1000=10000, то есть нужно << 4 а не << 3.
    – aepot
    30 окт 2022 в 20:10
  • где в 4 разряде инфа - живая клетка или нет, а в остальных 3 разрядах сколько соседей - 0b1011, дальше с помощь case я определяю выживает или рождается клетка в новом поколении и помещаю новою информацию о клетки в массив NewMap и опять же там будет выглядеть все примерно так 0b_0001. То есть битовый сдвиг нужно чтобы в 4 разрядах хранить всю информацию для дальнейшего case 30 окт 2022 в 20:11

1 ответ 1

3

Ну давайте попробуем, сначала инициализация.

public GameEngine(int rows, int cols, int density = 25)
{
    GameEngine.Rows = rows;
    GameEngine.Cols = cols;
    GameEngine.Map = new byte[Cols * Rows];
    GameEngine.NewMap = new byte[Cols * Rows];
    for (int y = 1; y < rows - 1; y++)
        for (int x = 1; x < cols - 1; x++)
            Map[x + y * Cols] = (byte)(rnd.Next(2)); // здесь была инверсия рандома, в которой просто нет никакого смысла
}

density никак не используется, странно?

Теперь генератор

  • Имея 3 соседей клетка будет живая независимо от текущего состояния, так? Тогда смысл проверять его.
  • Смысл проверять текущее состояние есть только если соседа ровно 2, что я и сделаю.
  • Немного причесал остальной код, закешировал вычисления, чтобы не вычислять одно и то же по несколько раз.
public void NewGeneration()
{
    CountGeneration++;
    for (int row = 1; row < Rows - 1; row++)
    {
        int rowOffset = row * Cols;
        for (int col = 1; col < Cols - 1; col++)
        {
            int pos = col + rowOffset;

            byte count = Map[pos - 1];
            count += Map[pos + 1];
            int prevRow = pos - Cols;
            count += Map[prevRow - 1];
            count += Map[prevRow];
            count += Map[prevRow + 1];
            int nextRow = pos + Cols;
            count += Map[nextRow - 1];
            count += Map[nextRow];
            count += Map[nextRow + 1];

            NewMap[pos] = (byte)(count == 3 || (count == 2 && Map[pos] == 1) ? 1 : 0);
            // или так NewMap[pos] = (byte)((count | Map[pos]) == 3 ? 1 : 0);
        }
    }
    byte[] tmp = Map;
    Map = NewMap;
    NewMap = tmp;
}

Большого прироста не обещаю, но на текущем уровне хуже точно не станет. Дальше, я полагаю, только векторизация вычислений поможет. Если текущй вариант не устроит, попробую написать что-нибудь такое.


Попробовал сделать векторную реализацию, не проверял.

using System.Numerics;
public void NewGeneration()
{
    CountGeneration++;
    int vectorSize = Vector<byte>.Count;
    for (int row = 1; row < Rows - 1; row++)
    {
        int rowOffset = row * Cols;
        for (int col = 1; col < Cols - 1; col += vectorSize)
        {
            if (col > Cols - 1 - vectorSize)
                col = Cols - 1 - vectorSize;
            int pos = col + rowOffset;

            Vector<byte> result = GetNextGen(Map, pos);
            result.CopyTo(NewMap, pos);
        }
    }
    byte[] tmp = Map;
    Map = NewMap;
    NewMap = tmp;
}

private Vector<byte> GetNextGen(byte[] input, int offset)
{
    Vector<byte> count = new Vector<byte>(input, offset - 1);
    count += new Vector<byte>(input, offset + 1);
    int prevRow = offset - Cols;
    count += new Vector<byte>(input, prevRow - 1);
    count += new Vector<byte>(input, prevRow);
    count += new Vector<byte>(input, prevRow + 1);
    int nextRow = offset + Cols;
    count += new Vector<byte>(input, nextRow - 1);
    count += new Vector<byte>(input, nextRow);
    count += new Vector<byte>(input, nextRow + 1);
    count |= new Vector<byte>(input, offset);
    Vector<byte> cmp = Vector.Equals(new Vector<byte>(3), count);
    return cmp & Vector<byte>.One;
}

Данная реализация не будет работать на карте шириной меньше, чем длина вектора+2, в моем случае 32+2 байта. То есть можно добавить условие, что если ширина карты меньше, чем Vector<byte>.Count + 2, то использовать обычную реализацию, без векторов. Реальная длина вектора зависит от типа процессора, в основном это 16 или 32 байта.

9
  • density это со старого проекта, забыл убрать. Получается где я зашел в тупик. Сейчас байт используется как: 0b0000_0001. То есть старший разряд всегда пустой. Если я не ошибаюсь то в старший разряд можно поместить информацию о клетки. Тогда бы и массив стал по ширине в 2 раза меньше, но и вычисления стали бы сложней. Я долго размышлял о том как грамотно запихнуть 2 клетки в один байт. И не нашел какого-то простого решения, возможно у вас будут какие-то идеи как это сделать более грамотно, буду очень благодарен за помощь, ваш код выше чу-чуть ускорить вычисления спасибо огромное ))) 30 окт 2022 в 21:27
  • @SevaVorobev не туда думаете, одна клетка - это один бит. :) 8 клеток на байт. Внутренние суммы это без разницы что, вы же только про массив. Но с другой стороны, у вас сейчас 0 мс на копирование в битмап, а если измените структуру данных, то сколько будет? Хотя в таком случае можно Format1bppIndexed битмап использовать :) Но да, вычисления будут посложнее, а следовательно помедленнее.
    – aepot
    30 окт 2022 в 21:33
  • Да 2 клетки вызывают целый комплекс проблем, и с выводом в BitMap буду проблемы. Натыкался на то что некоторые складывали сразу восемь соседей с помощью указателей и восьмибайтных слов используя ulong в котором как раз 64 разряда для 8 соседей, но до конца эту реализацию так и не понял, хотел даже к учителю по ассемблеру подойти и узнать про восьмибайтные слова, потому что как я читал вроде у процессора есть свои инструкции как раз для восьмибайтных слов, четырех байтных и т.д 30 окт 2022 в 21:35
  • 1
    @SevaVorobev я придумал как сделать SIMD из всего этого, ребус еще тот, но решаемый. Завтра, если буду жив после работы и не забуду, то попробую.
    – aepot
    30 окт 2022 в 21:59
  • 1
    Спасибо огромное за помощь 30 окт 2022 в 22:38

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.