Как я могу сделать свои клеточные автоматы быстрее

У меня есть сетка 300x300 ячеек. Я проверяю каждую ячейку по отдельности, что означает, что я проверяю 90000 ячеек по крайней мере каждую секунду. Я знаю, что одна секунда — это довольно быстро, учитывая, что процессор обрабатывает 300 ^ 2 разных ячеек. Но этот материал просто недостаточно быстр. Я наблюдал за парнем на YouTube, у которого его симуляция обновлялась каждые 20 мс. И у него было 512^2 ячеек. Как это возможно? Оптимизация? Мой компьютер - картошка? Я покажу свой код, если кто-то хочет увидеть, что именно я делаю.

for (int y = GY; y >= 0; y--)
    for (int x = 0; x < GX; x++) {
        cell* cell_pointer = &grid[x][y];
        if (grid[x][y].CellT == type::SAND) {
            if (grid[x][y+1].CellT == type::AIR) {
                if (y+1 > GY-1) {
                    continue;
                }
                cell* cell_below = &grid[x][y+1];

                cell_below->Color ={ 255,0,0 };
                cell_below->CellT = type::SAND;

                cell_pointer->Color ={ 0,0,0 };
                cell_pointer->CellT = type::AIR;
            }
            else if (grid[x+1][y+1].CellT == type::AIR) {
                cell* cell_below = &grid[x+1][y+1];

                cell_below->Color ={ 255,0,0 };
                cell_below->CellT = type::SAND;

                cell_pointer->Color ={ 0,0,0 };
                cell_pointer->CellT = type::AIR;
            }
            else if (grid[x-1][y+1].CellT == type::AIR) {
                cell* cell_below = &grid[x-1][y+1];

                cell_below->Color ={ 255,0,0 };
                cell_below->CellT = type::SAND;

                cell_pointer->Color ={ 0,0,0 };
                cell_pointer->CellT = type::AIR;
            }
        }
    }

Приведенный выше код — это моя функция обновления. Я обновляю ячейки снизу вверх, слева направо. Это симуляция песка, поэтому мы проверяем нижние левые, нижние правые, а также нижние соседние ячейки.

//Square//
SDL_SetRenderDrawColor(renderer, 0, 0, 255, 255);
SDL_RenderClear(renderer);

//////////

int X = floor(mousePos.x/r.w);
int Y = floor(mousePos.y/r.h);

if (left) {
        grid[X][Y].CellT = type::SAND;
        grid[X][Y].Color ={ 255,0,0 };
}
if (right) {
        grid[X][Y].CellT = type::WALL;
        grid[X][Y].Color ={ 0,255,0 };
}

for (int y = 0; y < GY; y++)
for (int x = 0; x < GX; x++) {
        cell* cell_pointer = &grid[x][y];
        SDL_SetRenderDrawColor(renderer, cell_pointer->Color.r, cell_pointer->Color.g, cell_pointer->Color.b, 255);
        r.x = cell_pointer->PosG.x;
        r.y = cell_pointer->PosG.y;

        SDL_RenderFillRect(renderer, &r);
}

SDL_RenderPresent(renderer);

SDL_UpdateWindowSurface(window);

Приведенный выше код — это моя функция рисования. Я использую SDL в качестве графического API. Я получаю положение мыши относительно сетки, поэтому, когда я нажимаю левую или правую кнопку мыши, я могу нарисовать ячейку песка или ячейку стены. Поэтому я проверяю каждую ячейку по отдельности сверху вниз и слева направо, а затем рисую квадрат отдельно, где находится позиция ячейки.


person Idiot Boy    schedule 21.07.2020    source источник
comment
В зависимости от расположения данных переключение циклов for для x и y иногда может творить чудеса.   -  person Mooing Duck    schedule 22.07.2020
comment
Вы профилировали код, чтобы определить, что обновление идет медленно? Или медленная часть SDL_RenderFillRect?   -  person Mooing Duck    schedule 22.07.2020
comment
Я думаю, что вы читали с y-1 до проверки if (y+1 > GY-1), и в этом случае вы читаете за пределами допустимого.   -  person Mooing Duck    schedule 22.07.2020
comment
Внутренние части блоков if идентичны по коду и различаются только значениями, что означает, что в кэше инструкций содержится в 3 раза больше кода, чем необходимо, что теоретически может снизить производительность. На практике это вряд ли повлияет на что-то заметное.   -  person Mooing Duck    schedule 22.07.2020
comment
Оптимизатор компилятора должен уже знать этот трюк, но рассмотрите возможность использования ссылки вместо указателя на cell* cell_below = &grid[x][y+1]; и друзей. Говоря об этом, не тратьте свое время на скорость программы, если у вас не включена средняя или высокая оптимизация.   -  person user4581301    schedule 22.07.2020
comment
Один лакомый кусочек заключается в том, что вы обновляете все 90 тыс. ячеек за одно обновление. Если вы обновляете только ячейки, смежные с обновлениями из предыдущего кадра, вы можете (иногда) добиться гораздо более высокой производительности, в зависимости от того, какая часть экрана обновляется в каждом кадре.   -  person Mooing Duck    schedule 22.07.2020
comment
Теперь, когда я прочитал код, я на 95% уверен, что проблема в SDL_RenderClear(renderer), за которой следуют 90k SDL_RenderFillRect вызовов. Это тонна данных, которые нужно передавать на видеокарту каждый кадр.   -  person Mooing Duck    schedule 22.07.2020
comment
@MooingDuck Итак, как мне решить эту проблему? Я очень привык очищать, а затем снова рисовать.   -  person Idiot Boy    schedule 22.07.2020
comment
что-то что-то hashlife :)   -  person genpfault    schedule 22.07.2020
comment
@IdiotBoy: я мало разбираюсь в графике (пока), но мои деньги будут заключаться в том, чтобы не делать очистку, а только рисовать измененные ячейки. Или делать алгоритм полностью на графическом процессоре, где все распараллелено, но я не знаю, как это работает.   -  person Mooing Duck    schedule 22.07.2020
comment
@genpfault Я посмотрю на это, спасибо.   -  person Idiot Boy    schedule 22.07.2020
comment
@IdiotBoy: Нет, я пошутил, извини. Mooing Duck имеет слишком много SDL_RenderFillRect() вызовов на кадр. Вы захотите изменить свой массив цветов состояния CA на стороне процессора, загрузите его в SDL_Texture, а затем нарисуйте ее. Таким образом, у вас будет только (по сути) только один вызов отрисовки графического процессора на кадр.   -  person genpfault    schedule 22.07.2020
comment
В более общем плане RE: оптимизация CA, просмотрите структуры кода шаблона, они могут использовать шаблоны и потоки для автоматически распараллеливать обновления CA, сохраняя при этом (относительно) нормальный код правил внутреннего цикла   -  person genpfault    schedule 22.07.2020
comment
Кроме того, отредактируйте минимально воспроизводимый пример, мне интересно посмотреть, каков общий эффект.   -  person genpfault    schedule 22.07.2020