Как улучшить производительность для дорогих функций в 2d city builder

Я уже искал ответы, но мне не удалось найти лучший подход для обработки дорогих функций / вычислений.

В моей текущей игре (двумерное городское здание на основе плиток) пользователь может размещать здания, строить дороги и т. Д. Все здания нуждаются в соединении с перекрестком, который пользователь должен разместить на границе карты. Если здание не подключено к этому перекрестку, над поврежденным зданием появится всплывающее сообщение «Не связано с дорогой» (в противном случае его необходимо удалить). Большинство зданий имеют радиус и могут быть связаны друг с другом (например, пожарная служба может помочь всем домам в радиусе 30 плиток). Это то, что мне также нужно обновить / проверить, когда меняется дорожное сообщение.

Вчера я столкнулся с большой проблемой производительности. Давайте рассмотрим следующий сценарий: Пользователь, конечно, может также стирать здания и дороги. Так что, если пользователь теперь разрывает соединение сразу после пересечения, мне нужно обновить много зданий одновременно . Я думаю, что одним из первых советов было бы избегать вложенных циклов (что, безусловно, является большой причиной в этом сценарии), но я должен проверить ...

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

2. список радиальных плиток и получить здания в радиусе (вложенные циклы - большая проблема!) .

   // Go through all buildings affected by erasing this road tile.
   foreach(var affectedBuilding in affectedBuildings) {
       // Get buildings within radius.
       foreach(var radiusTile in affectedBuilding.RadiusTiles) {
           // Get all buildings on Map within this radius (which is technially another foreach).
           var buildingsInRadius = TileMap.Buildings.Where(b => b.TileIndex == radiusTile.TileIndex);  
   
           // Do stuff.
       }
   }

Все это снижает мой FPS с 60 до почти 10 за одну секунду.

Так бы я мог сделать. Мои идеи будут:

• Не использовать основной поток (функцию обновления) для этого, а другого потока. Я могу столкнуться с проблемами блокировки, когда начну использовать многопоточность.
• Использование очереди для обработки большого количества вычислений (что будет лучшим подходом в этом случае?)
• Храните больше информации в моих объектах (зданиях), чтобы избежать дополнительных вычислений (например, зданий в радиусе).

Используя последний подход, я мог бы вместо этого удалить одно вложение в форме:

// Go through all buildings affected by erasing this road tile.
foreach(var affectedBuilding in affectedBuildings) {
    // Go through buildings within radius.
    foreach(var buildingInRadius in affectedBuilding.BuildingsInRadius) {
        // Do stuff.
    }
}

Но я не знаю, достаточно ли этого. Такие игры, как Cities Skylines должны обрабатывать намного больше зданий, если у игрока есть большая карта. Как они справляются с этими вещами ?! Может быть очередь обновления, так как не все здания обновляются одновременно.

Я с нетерпением жду ваших идей и комментариев!

Большое спасибо!

Покрытие кэширования

Идея кэширования информации о том, какие здания находятся в зоне действия эффекторного здания (которое вы можете кешировать как из эффектора, так и из затронутого объекта), безусловно, является хорошей идеей. Здания (как правило) не двигаются, поэтому нет оснований повторять эти дорогостоящие вычисления. «На что влияет это здание» и «Что влияет на это здание» - это то, что вам нужно проверить только при создании или удалении здания.

Это классический обмен процессорных циклов на память.

Обработка информации о покрытии по регионам

Если окажется, что вы используете слишком много памяти для отслеживания этой информации, посмотрите, можете ли вы обрабатывать такую ​​информацию по регионам карты. Разделите вашу карту на квадратные области n*nплитка. Если район полностью охвачен пожарной службой, все здания в этом регионе также покрыты. Таким образом, вам нужно хранить информацию о покрытии только по регионам, а не по отдельным зданиям. Если регион покрыт только частично, вам нужно вернуться к обработке внутренних связей в этом регионе. Таким образом, функция обновления для ваших зданий будет сначала проверять: «Район, в котором находится это здание, покрыт пожарной службой?» и если нет, "Это здание индивидуально закрыто пожарной службой?" Это также ускоряет обновления, поскольку после удаления пожарной части вам больше не нужно обновлять состояния покрытия 2000 зданий, вам нужно обновить только 100 зданий и 25 регионов.

Задержка обновления

Другая оптимизация, которую вы можете сделать, это не обновлять все сразу и не обновлять все одновременно.

Независимо от того, подключено ли здание к дорожной сети или нет, вам не нужно проверять каждый кадр (кстати, вы также можете найти некоторые способы оптимизировать это, в частности, изучив теорию графов). Было бы вполне достаточно, если бы здания проверяли это периодически каждые несколько секунд после того, как здание было построено (И если произошло изменение в дорожной сети). То же самое относится к эффектам построения диапазона. Вполне приемлемо, если здание проверяет только каждые несколько сотен кадров. «По крайней мере, одно из пожарных подразделений, которые влияют на меня, все еще активно?»

Таким образом, ваш цикл обновления может выполнять только эти дорогостоящие вычисления для нескольких сотен зданий одновременно для каждого обновления. Возможно, вы захотите задать предпочтения зданиям, которые в данный момент находятся на экране, чтобы игроки сразу получали отзывы о своих действиях.

Относительно многопоточности

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

1. Дублирующая работа .

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

var toBeUpdated = new HashSet<Tiles>();
foreach(var affectedBuilding in affectedBuildings) {
    foreach(var radiusTile in affectedBuilding.RadiusTiles) {
         toBeUpdated.Add(radiusTile);

}
foreach (var tile in toBeUpdated)
{
    var buildingsInTile = TileMap.Buildings.Where(b => b.TileIndex == radiusTile.TileIndex);
    // Do stuff.
}

2. Неподходящие структуры данных.

var buildingsInTile = TileMap.Buildings.Where(b => b.TileIndex == radiusTile.TileIndex);

должно быть ясно

var buildingsInRadius = tile.Buildings;

где Buildings - IEnumerableс постоянным временем итерации (например, a List<Building>)