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 you have read our privacy policy.

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