Самый эффективный способ выбора ряда классов из большого списка классов?

Question

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

Проблема у меня есть, очевидно, чем больше мой общий список плиток становится больше лаг, который я испытываю при попытке выбрать Плитки в радиусе действия. Я в настоящее время использую Linq внутри для цикла, чтобы выбрать плитку, например, так:

//loop from the maximum view at the top of the screen to the maximum view at the bottom 
for (int height = topView; height < bottomView; height++) 
{ 
    //loop from the maximum view to the left of the screen to the maximum view of the right 
    for (int width = leftView; width < rightView; width++) 
    { 
     //select the tile at this grid position 
     Tile t = tileList.Where(x => x.GridPosition == new Vector2(width, height)).FirstOrDefault(); 
     if (t != null) 
     { 
      //calculate the screen position and add it to the list of local tiles within range 
      t.ScreenPosition = new Vector2(screenWidth * 30, screenHeight * 30); 
      localList.Add(t); 
     } 
     else 
     { 
      //the tile wasn't found, add a random blank one to fill the gap. 
      Tile brokenTile = new Tile(game, new Vector2(width, height), 9001); 
      brokenTile.ScreenPosition = new Vector2(screenWidth * 30, screenHeight * 30); 
      localList.Add(brokenTile); 
     } 
     //increment the screen width used to calculate the screen position 
     screenWidth++; 
    } 
    //increment the screen height used to calculate the screen position and reset the width 
    screenHeight++; 
    screenWidth = 1; 
} 

мне интересно, если есть способ сделать это более эффективно, в идеале сократить отставание опытной при увеличении общего размера «карты» и выбора этих плиток в радиусе действия.

Единственное, что я могу придумать, это как-то разбить общий список на «куски», когда карта загружена, и только смотреть в каждом куске, чтобы вытащить Плитки. Однако я не совсем уверен, как я 'd делать это, потому что это может быть проблемой, если мне нужно вытащить узлы из нескольких «кусков». Любая помощь по хорошему способу сделать это тоже будет здорово!

Спасибо большое! :)

Edit: вот несколько скриншотов: http://i.imgur.com/RJmSYYF.png по сравнению с http://i.imgur.com/LgwB8CJ.png

Answer 1

Я хотел бы использовать некоторую форму space partitioning, такую ​​как quadtree.

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

Answer 2

Коллекция, которая позволяет быстро найти объект в к-мерном пространстве является KD-Tree.

См. k-d tree в Википедии и Geometric Algorithms.

Я портировал реализацию Java KD-дерева на C#. Пожалуйста, см. User:Ojd/KD-Tree на RoboWiki. Вы можете скачать код там.

A K-D Tree имеет O (log n) Время поиска.

---

UPDATE:

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

Tile[,] grid = new Tile[m,n]; 

Выбор плитки становится вполне естественным, так как вы можете рассчитать свое положение в сетке из положения экрана. Как и вы, вы можете получить к ним доступ непосредственно через свои x-y-индексы без поиска их в списке лагров. Время доступа для одной плитки: O (1), то есть независимо от общего количества плиток.