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

Question

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

Осколки и куски:

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

Когда осколок сломан, все его соединения с другими осколками и их соединения с ним удаляются.

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

Какой самый быстрый способ сделать это?

В настоящее время у меня есть:

• класс Осколка, имеющий

  • ссылка на родительский блок
  • список соединений с соседними осколками.
  • метод Break (), который
    • удаляет все соединения от соседних осколков к этому.
    • очищает соединения от этого к соседним осколкам.
    • вызывает метод UpdateChunk () родительского блока.

• класс Chunk, имеющий

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

public class Shard : MonoBehaviour
{
    public GameObject parentChunk;

    public List<GameObject> connectedShards = new List<GameObject>();

    public void Break()
    {
        // remove all connections that point to this shard
        foreach (GameObject shard in connectedShards)
        {
            // remove connection to this shard
            shard.GetComponent<Shard>().connectedShards.Remove(gameObject);
        }

        // clear connected shards list
        connectedShards.Clear();

        // check that there is a parent chunk
        if (parentChunk)
        {
            // force parent chunk to update
            parentChunk.GetComponent<Chunk>().UpdateChunk();

            // set parent chunk to null
            parentChunk = null;
        }
    }
}




public class Chunk : MonoBehaviour
{
    public List<GameObject> shards = new List<GameObject>();

    private List<GameObject> unprocessedShards = new List<GameObject>();

    public void UpdateChunk()
    {
        // if there is only one shard in this chunk
        if (shards.Count == 1)
        {
            // break shard
            shards[0].GetComponent<Shard>().parentChunk = null;
            shards[0].GetComponent<Shard>().Break();

            // destroy this chunk
            Destroy(gameObject);
        }
        else // there are multiple shards in this chunk
        {
            // fill the unprocessed shards list
            unprocessedShards = new List<GameObject>(shards);

            // process all shards in this chunk recursively starting from the first
            ProcessShard(unprocessedShards[0], gameObject);

            // if there are still unprocessed shards (this chunk was split)
            if (unprocessedShards.Count > 0)
            {
                // remove the unprocessed shards from this chunk's shard list
                foreach (GameObject unprocessedShard in unprocessedShards)
                {
                    shards.Remove(unprocessedShard);
                }

                // create new chunk(s) from the leftover shards
                parentObject.GetComponent<Fragmenter>().NewChunk(unprocessedShards);
            }
        }
    }



    // process shard
    private void ProcessShard(GameObject shard, GameObject chunk)
    {
        // remove shard from unprocessed list
        unprocessedShards.Remove(shard);

        // add shard to the given chunk
        shard.GetComponent<Shard>().parentChunk = chunk;

        // loop through all shards connected to the given shard
        foreach (GameObject connectedShard in shard.GetComponent<Shard>().connectedShards)
        {
            // connected shard has not been processed yet
            if (unprocessedShards.Contains(connectedShard))
            {
                // process all shards connected to the connected shard
                ProcessShard(connectedShard, chunk);
            }
        }
    }
}

В основном я думаю о методе ProcessShard (), где он обычно обрабатывает каждый осколок несколько раз, так как один может быть смежным со многими. Как я могу наиболее эффективно игнорировать те, которые уже были обработаны?

Answer 1

Во-первых, я бы предложил отойти от List.Remove, так как в худшем случае необходимо проверить каждый элемент, чтобы найти тот, который нужно удалить.Вместо удаления осколков, которые обрабатываются, из списка необработанных осколков, вы можете сохранить еще один список обработанных осколков и добавить к нему.Тогда ваша проверка состояния, если подключенный осколок не обработан, станет if(!processedShards.Contains(connectedShard)).

Подробнее о выполнении операций со списком вы можете узнать в документах Microsoft , просто прокрутив вниз до раздела «Примечания».

---

Еще одним улучшением будет поискальтернатива List.Contains при проверке, был ли обработан осколок.Подобно List.Remove, ему необходимо проверить каждый элемент в списке, прежде чем он сможет определить, присутствует ли этот элемент.

Один из способов сделать это - использовать HashSet вместо списка.Он предоставляет гораздо более быстрые способы доступа к определенным элементам и проверки наличия элементов в коллекции.Он также предоставляет многие из тех же методов, поэтому рефакторинг должен быть легким.

---

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

Answer 2

Похоже, что сценарий больше всего замедлился при рекурсии метода ProcessShard (), поэтому я переименовал и переписал метод как ProcessShards (), который использует цикл while и очередь для обработки всех сегментов. Производительность была примерно в десять раз лучше для фрагмента с 100 осколками.

    // process shards
    private void ProcessShards()
    {
        // create a list for shards to process
        Queue<GameObject> shardsToProcess = new Queue<GameObject>();

        // select the first shard to process
        shardsToProcess.Enqueue(unprocessedShards[0]);

        // remove shard from unprocessed list
        unprocessedShards.Remove(unprocessedShards[0]);

        // loop while there are shards to process
        while (shardsToProcess.Count > 0)
        {
            // get the first shard to process
            GameObject shard = shardsToProcess.Dequeue();

            // add the shard to this chunk
            shard.GetComponent<Shard>().parentChunk = gameObject;

            // loop through all shards connected to the given shard
            foreach (GameObject connectedShard in shard.GetComponent<Shard>().connectedShards)
            {
                // connected shard has not been processed yet
                if (unprocessedShards.Contains(connectedShard))
                {
                    // add shard to be processed
                    shardsToProcess.Enqueue(connectedShard);

                    // remove shard from unprocessed list
                    unprocessedShards.Remove(connectedShard);
                }
            }
        }
    }