C # XNA: Optymalizacja wykrywania kolizji?
Pracuję nad prostym demo do wykrywania kolizji, które zawiera tylko kilka obiektów odbijających się w oknie. (Celem jest sprawdzenie, ile obiektów gra może obsłużyć jednocześnie bez upuszczania klatek.)
Istnieje grawitacja, więc obiekty albo się poruszają, albo zderzają się ze ścianą.
Naiwnym rozwiązaniem było O (n^2):
foreach Collidable c1:
foreach Collidable c2:
checkCollision(c1, c2);
CollisionCell obiekty, które przechowują informacje o części ekranu. Pomysł jest to, że każdy Collidable musi tylko sprawdzić, czy nie ma innych obiektów w swojej komórce. Z ogniwami 60 px na 60 px daje to prawie 10-krotną poprawę, ale chciałbym ją dalej popchnąć.
Profiler ujawnił, że kod spędza 50% swojego czasu w funkcji, której używa każda komórka, aby uzyskać jego zawartość. Tutaj jest:
// all the objects in this cell
public ICollection<GameObject> Containing
{
get
{
ICollection<GameObject> containing = new HashSet<GameObject>();
foreach (GameObject obj in engine.GameObjects) {
// 20% of processor time spent in this conditional
if (obj.Position.X >= bounds.X &&
obj.Position.X < bounds.X + bounds.Width &&
obj.Position.Y >= bounds.Y &&
obj.Position.Y < bounds.Y + bounds.Height) {
containing.Add(obj);
}
}
return containing;
}
}
Z tego 20% czasu programu jest spędzane w tym warunkowym.
Tutaj zostanie wywołana powyższa funkcja:
// Get a list of lists of cell contents
List<List<GameObject>> cellContentsSet = cellManager.getCellContents();
// foreach item, only check items in the same cell
foreach (List<GameObject> cellMembers in cellContentsSet) {
foreach (GameObject item in cellMembers) {
// process collisions
}
}
//...
// Gets a list of list of cell contents (each sub list = 1 cell)
internal List<List<GameObject>> getCellContents() {
List<List<GameObject>> result = new List<List<GameObject>>();
foreach (CollisionCell cell in cellSet) {
result.Add(new List<GameObject>(cell.Containing.ToArray()));
}
return result;
}
W tej chwili, muszę iterować nad każdą komórką - nawet pustą. Być może można to jakoś poprawić, ale nie jestem pewien, jak zweryfikować, że komórka jest pusta, nie patrząc na nią jakoś. (Może mógłbym zaimplementować coś w rodzaju śpiących obiektów, w niektórych silnikach fizyki, gdzie jeśli obiekt będzie nieruchomy przez jakiś czas przechodzi w stan uśpienia i nie jest uwzględniany w obliczeniach dla każdej klatki.)
Co mogę zrobić, aby to zoptymalizować? (Również jestem nowy w C# - czy są jakieś inne rażące stylistycznie błędy?)
Kiedy gra zaczyna się opóźniać, obiekty są dość szczelnie zapakowane, więc nie dzieje się zbyt wiele ruchu. Być może mogę to jakoś wykorzystać, pisząc funkcję, aby sprawdzić, czy, biorąc pod uwagę aktualną prędkość obiektu, może on opuścić swoją obecną komórkę przed następnym wywołaniem do Update()
UPDATE 1 postanowiłem zachować listę obiektów, które zostały znalezione w komórce w ostatniej aktualizacji, i sprawdzić te pierwsze, aby zobaczyć, czy były nadal w celi. Ponadto utrzymałem area zmiennej CollisionCell, Kiedy po wypełnieniu komórki mogłem przestać szukać. Oto moja implementacja tego, co sprawiło, że całe demo było znacznie wolniejsze: {]}
// all the objects in this cell
private ICollection<GameObject> prevContaining;
private ICollection<GameObject> containing;
internal ICollection<GameObject> Containing {
get {
return containing;
}
}
/**
* To ensure that `containing` and `prevContaining` are up to date, this MUST be called once per Update() loop in which it is used.
* What is a good way to enforce this?
*/
public void updateContaining()
{
ICollection<GameObject> result = new HashSet<GameObject>();
uint area = checked((uint) bounds.Width * (uint) bounds.Height); // the area of this cell
// first, try to fill up this cell with objects that were in it previously
ICollection<GameObject>[] toSearch = new ICollection<GameObject>[] { prevContaining, engine.GameObjects };
foreach (ICollection<GameObject> potentiallyContained in toSearch) {
if (area > 0) { // redundant, but faster?
foreach (GameObject obj in potentiallyContained) {
if (obj.Position.X >= bounds.X &&
obj.Position.X < bounds.X + bounds.Width &&
obj.Position.Y >= bounds.Y &&
obj.Position.Y < bounds.Y + bounds.Height) {
result.Add(obj);
area -= checked((uint) Math.Pow(obj.Radius, 2)); // assuming objects are square
if (area <= 0) {
break;
}
}
}
}
}
prevContaining = containing;
containing = result;
}
UPDATE 2 porzuciłem to ostatnie podejście. Teraz próbuję utrzymać pulę kolidabli (orphans) i usuwać z nich obiekty, gdy znajdę komórkę, która je zawiera:
internal List<List<GameObject>> getCellContents() {
List<GameObject> orphans = new List<GameObject>(engine.GameObjects);
List<List<GameObject>> result = new List<List<GameObject>>();
foreach (CollisionCell cell in cellSet) {
cell.updateContaining(ref orphans); // this call will alter orphans!
result.Add(new List<GameObject>(cell.Containing));
if (orphans.Count == 0) {
break;
}
}
return result;
}
// `orphans` is a list of GameObjects that do not yet have a cell
public void updateContaining(ref List<GameObject> orphans) {
ICollection<GameObject> result = new HashSet<GameObject>();
for (int i = 0; i < orphans.Count; i++) {
// 20% of processor time spent in this conditional
if (orphans[i].Position.X >= bounds.X &&
orphans[i].Position.X < bounds.X + bounds.Width &&
orphans[i].Position.Y >= bounds.Y &&
orphans[i].Position.Y < bounds.Y + bounds.Height) {
result.Add(orphans[i]);
orphans.RemoveAt(i);
}
}
containing = result;
}
To daje tylko marginalną poprawę, a nie 2x czy 3x Szukam za.
UPDATE 3 ponownie porzuciłem powyższe podejścia i postanowiłem pozwolić każdemu obiektowi utrzymać swoją obecną komórkę:
private CollisionCell currCell;
internal CollisionCell CurrCell {
get {
return currCell;
}
set {
currCell = value;
}
}
Wartość ta zostanie zaktualizowana:
// Run 1 cycle of this object
public virtual void Run()
{
position += velocity;
parent.CellManager.updateContainingCell(this);
}
Kod Cellmanagera:
private IDictionary<Vector2, CollisionCell> cellCoords = new Dictionary<Vector2, CollisionCell>();
internal void updateContainingCell(GameObject gameObject) {
CollisionCell currCell = findContainingCell(gameObject);
gameObject.CurrCell = currCell;
if (currCell != null) {
currCell.Containing.Add(gameObject);
}
}
// null if no such cell exists
private CollisionCell findContainingCell(GameObject gameObject) {
if (gameObject.Position.X > GameEngine.GameWidth
|| gameObject.Position.X < 0
|| gameObject.Position.Y > GameEngine.GameHeight
|| gameObject.Position.Y < 0) {
return null;
}
// we'll need to be able to access these outside of the loops
uint minWidth = 0;
uint minHeight = 0;
for (minWidth = 0; minWidth + cellWidth < gameObject.Position.X; minWidth += cellWidth) ;
for (minHeight = 0; minHeight + cellHeight < gameObject.Position.Y; minHeight += cellHeight) ;
CollisionCell currCell = cellCoords[new Vector2(minWidth, minHeight)];
// Make sure `currCell` actually contains gameObject
Debug.Assert(gameObject.Position.X >= currCell.Bounds.X && gameObject.Position.X <= currCell.Bounds.Width + currCell.Bounds.X,
String.Format("{0} should be between lower bound {1} and upper bound {2}", gameObject.Position.X, currCell.Bounds.X, currCell.Bounds.X + currCell.Bounds.Width));
Debug.Assert(gameObject.Position.Y >= currCell.Bounds.Y && gameObject.Position.Y <= currCell.Bounds.Height + currCell.Bounds.Y,
String.Format("{0} should be between lower bound {1} and upper bound {2}", gameObject.Position.Y, currCell.Bounds.Y, currCell.Bounds.Y + currCell.Bounds.Height));
return currCell;
}
Myślałem, że to poprawi sytuację - teraz muszę tylko iterować nad collidables , a nie wszystkimi collidables * komórkami. Zamiast tego, gra jest teraz potwornie powolny, dostarczając tylko 1/10 jego wydajności z moich powyższych podejść.
Profiler wskazuje że inna metoda jest teraz głównym hot spot, a czas, aby uzyskać sąsiadów dla obiektu jest trywialnie krótki. Ta metoda się nie zmieniła, więc może nazywam ją bardziej niż kiedyś...
7 answers
Spędza 50% swojego czasu w tej funkcji, ponieważ często ją wywołujesz. Optymalizacja tej jednej funkcji przyniesie tylko stopniowe ulepszenia wydajności.
Alternatywnie, po prostu wywołaj funkcję less!
Rozpocząłeś już tę ścieżkę, ustawiając schemat partycjonowania przestrzennego (lookup Quadtrees, aby zobaczyć bardziej zaawansowaną formę swojej techniki).
Drugim podejściem jest przełamanie pętli N*N do postaci przyrostowej i użycie a Budżet CPU .
Możesz przydzielić budżet procesora dla każdego z modułów, które chcą działać w czasie klatek (podczas aktualizacji). Collision jest jednym z tych modułów, AI może być innym.
Powiedzmy, że chcesz uruchomić grę z prędkością 60 fps. Oznacza to, że masz około 1/60 s = 0.0167 S czasu procesora na nagrywanie między klatkami. Nie możemy podzielić te 0.0167 S między nasze moduły. Dajmy 30% budżetu: 0,005 s.Teraz twój algorytm kolizji wie, że może spędzić tylko 0.005 S pracy. Jeśli więc skończy się czas, będzie musiał odłożyć niektóre zadania na później - sprawisz, że algorytm będzie Przyrostowy. Kod do osiągnięcia tego może być tak prosty jak:
const double CollisionBudget = 0.005;
Collision[] _allPossibleCollisions;
int _lastCheckedCollision;
void HandleCollisions() {
var startTime = HighPerformanceCounter.Now;
if (_allPossibleCollisions == null ||
_lastCheckedCollision >= _allPossibleCollisions.Length) {
// Start a new series
_allPossibleCollisions = GenerateAllPossibleCollisions();
_lastCheckedCollision = 0;
}
for (var i=_lastCheckedCollision; i<_allPossibleCollisions.Length; i++) {
// Don't go over the budget
if (HighPerformanceCount.Now - startTime > CollisionBudget) {
break;
}
_lastCheckedCollision = i;
if (CheckCollision(_allPossibleCollisions[i])) {
HandleCollision(_allPossibleCollisions[i]);
}
}
}
Teraz nie ma znaczenia, jak szybki jest kod kolizji, zostanie on wykonany tak szybko, jak to możliwe bez wpływu na postrzeganą Wydajność Użytkownika .
Korzyści obejmują:
- algorytm jest zaprojektowany tak, aby zabrakło czasu, to po prostu wznawia się na następnej ramce, więc nie musisz się martwić o ten konkretny przypadek edge. [30]}budżetowanie procesora staje się coraz ważniejsze wraz ze wzrostem liczby zaawansowanych/czasochłonnych algorytmów. Myśl AI. Warto więc wdrożyć taki system na wczesnym etapie.
- Czas reakcji człowieka jest mniejszy niż 30 Hz, twoja pętla ramki działa przy 60 Hz. Daje to algorytmowi 30 klatek na ukończenie jego pracy, więc jest OK, że nie kończy swojej pracy.
- robienie tego w ten sposób daje stabilny, niezależne od danych liczby klatek na sekundę. [30]}nadal korzysta z optymalizacji wydajności do samego algorytmu kolizji.
- algorytmy kolizji są zaprojektowane do śledzenia "ramki podrzędnej", w której miały miejsce kolizje. To znaczy, nigdy nie będziesz tak szczęśliwy, aby złapać kolizję po prostu tak jak to się dzieje - myślenie, że to robisz, to okłamywanie siebie.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-26 22:59:42
Mogę tu pomóc; napisałem własne wykrywanie kolizji jako eksperyment. Myślę, że mogę ci teraz powiedzieć, że nie osiągniesz potrzebnej wydajności bez zmiany algorytmów. Jasne, naiwny sposób jest ładny, ale działa tylko na tak wiele przedmiotów przed upadkiem. To czego potrzebujesz to zamiatać i ścinać . Podstawowa idea wygląda tak (z mojego projektu biblioteki wykrywania kolizji):
using System.Collections.Generic;
using AtomPhysics.Interfaces;
namespace AtomPhysics.Collisions
{
public class SweepAndPruneBroadPhase : IBroadPhaseCollider
{
private INarrowPhaseCollider _narrowPhase;
private AtomPhysicsSim _sim;
private List<Extent> _xAxisExtents = new List<Extent>();
private List<Extent> _yAxisExtents = new List<Extent>();
private Extent e1;
public SweepAndPruneBroadPhase(INarrowPhaseCollider narrowPhase)
{
_narrowPhase = narrowPhase;
}
public AtomPhysicsSim Sim
{
get { return _sim; }
set { _sim = null; }
}
public INarrowPhaseCollider NarrowPhase
{
get { return _narrowPhase; }
set { _narrowPhase = value; }
}
public bool NeedsNotification { get { return true; } }
public void Add(Nucleus nucleus)
{
Extent xStartExtent = new Extent(nucleus, ExtentType.Start);
Extent xEndExtent = new Extent(nucleus, ExtentType.End);
_xAxisExtents.Add(xStartExtent);
_xAxisExtents.Add(xEndExtent);
Extent yStartExtent = new Extent(nucleus, ExtentType.Start);
Extent yEndExtent = new Extent(nucleus, ExtentType.End);
_yAxisExtents.Add(yStartExtent);
_yAxisExtents.Add(yEndExtent);
}
public void Remove(Nucleus nucleus)
{
foreach (Extent e in _xAxisExtents)
{
if (e.Nucleus == nucleus)
{
_xAxisExtents.Remove(e);
}
}
foreach (Extent e in _yAxisExtents)
{
if (e.Nucleus == nucleus)
{
_yAxisExtents.Remove(e);
}
}
}
public void Update()
{
_xAxisExtents.InsertionSort(comparisonMethodX);
_yAxisExtents.InsertionSort(comparisonMethodY);
for (int i = 0; i < _xAxisExtents.Count; i++)
{
e1 = _xAxisExtents[i];
if (e1.Type == ExtentType.Start)
{
HashSet<Extent> potentialCollisionsX = new HashSet<Extent>();
for (int j = i + 1; j < _xAxisExtents.Count && _xAxisExtents[j].Nucleus.ID != e1.Nucleus.ID; j++)
{
potentialCollisionsX.Add(_xAxisExtents[j]);
}
HashSet<Extent> potentialCollisionsY = new HashSet<Extent>();
for (int j = i + 1; j < _yAxisExtents.Count && _yAxisExtents[j].Nucleus.ID != e1.Nucleus.ID; j++)
{
potentialCollisionsY.Add(_yAxisExtents[j]);
}
List<Extent> probableCollisions = new List<Extent>();
foreach (Extent e in potentialCollisionsX)
{
if (potentialCollisionsY.Contains(e) && !probableCollisions.Contains(e) && e.Nucleus.ID != e1.Nucleus.ID)
{
probableCollisions.Add(e);
}
}
foreach (Extent e2 in probableCollisions)
{
if (e1.Nucleus.DNCList.Contains(e2.Nucleus) || e2.Nucleus.DNCList.Contains(e1.Nucleus))
continue;
NarrowPhase.DoCollision(e1.Nucleus, e2.Nucleus);
}
}
}
}
private bool comparisonMethodX(Extent e1, Extent e2)
{
float e1PositionX = e1.Nucleus.NonLinearSpace != null ? e1.Nucleus.NonLinearPosition.X : e1.Nucleus.Position.X;
float e2PositionX = e2.Nucleus.NonLinearSpace != null ? e2.Nucleus.NonLinearPosition.X : e2.Nucleus.Position.X;
e1PositionX += (e1.Type == ExtentType.Start) ? -e1.Nucleus.Radius : e1.Nucleus.Radius;
e2PositionX += (e2.Type == ExtentType.Start) ? -e2.Nucleus.Radius : e2.Nucleus.Radius;
return e1PositionX < e2PositionX;
}
private bool comparisonMethodY(Extent e1, Extent e2)
{
float e1PositionY = e1.Nucleus.NonLinearSpace != null ? e1.Nucleus.NonLinearPosition.Y : e1.Nucleus.Position.Y;
float e2PositionY = e2.Nucleus.NonLinearSpace != null ? e2.Nucleus.NonLinearPosition.Y : e2.Nucleus.Position.Y;
e1PositionY += (e1.Type == ExtentType.Start) ? -e1.Nucleus.Radius : e1.Nucleus.Radius;
e2PositionY += (e2.Type == ExtentType.Start) ? -e2.Nucleus.Radius : e2.Nucleus.Radius;
return e1PositionY < e2PositionY;
}
private enum ExtentType { Start, End }
private sealed class Extent
{
private ExtentType _type;
public ExtentType Type
{
get
{
return _type;
}
set
{
_type = value;
_hashcode = 23;
_hashcode *= 17 + Nucleus.GetHashCode();
}
}
private Nucleus _nucleus;
public Nucleus Nucleus
{
get
{
return _nucleus;
}
set
{
_nucleus = value;
_hashcode = 23;
_hashcode *= 17 + Nucleus.GetHashCode();
}
}
private int _hashcode;
public Extent(Nucleus nucleus, ExtentType type)
{
Nucleus = nucleus;
Type = type;
_hashcode = 23;
_hashcode *= 17 + Nucleus.GetHashCode();
}
public override bool Equals(object obj)
{
return Equals(obj as Extent);
}
public bool Equals(Extent extent)
{
if (this.Nucleus == extent.Nucleus)
{
return true;
}
return false;
}
public override int GetHashCode()
{
return _hashcode;
}
}
}
}
A oto kod, który sortuje wstawianie (mniej więcej bezpośrednie tłumaczenie pseudocode TUTAJ):
/// <summary>
/// Performs an insertion sort on the list.
/// </summary>
/// <typeparam name="T">The type of the list supplied.</typeparam>
/// <param name="list">the list to sort.</param>
/// <param name="comparison">the method for comparison of two elements.</param>
/// <returns></returns>
public static void InsertionSort<T>(this IList<T> list, Func<T, T, bool> comparison)
{
for (int i = 2; i < list.Count; i++)
{
for (int j = i; j > 1 && comparison(list[j], list[j - 1]); j--)
{
T tempItem = list[j];
list.RemoveAt(j);
list.Insert(j - 1, tempItem);
}
}
}
IIRC, udało mi się dzięki temu uzyskać bardzo duży wzrost wydajności, szczególnie w przypadku dużej liczby zderzających się ciał. Musisz dostosować go do swojego kodu, ale to jest podstawowa przesłanka za sweep and prune.
Inną rzeczą, którą chcę ci przypomnieć, Jest to, że powinieneś użyć profilera, takiego jak ten stworzony przez Red Gate. Jest bezpłatny okres próbny, który powinien trwać wystarczająco długo.Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-26 22:36:36
Wygląda na to, że przeglądasz wszystkie obiekty w grze tylko po to, aby zobaczyć, jakie obiekty są zawarte w komórce. Wydaje się, że lepszym podejściem byłoby przechowywanie listy obiektów gry, które są w komórce dla każdej komórki. Jeśli zrobisz to i każdy obiekt wie, w jakich komórkach się znajduje, przenoszenie obiektów między komórkami powinno być łatwe. Wydaje się, że przyniesie to największy wzrost wydajności.
Oto kolejna wskazówka optymalizacyjna do określenia, w jakich komórkach znajduje się obiekt: Jeśli już określa, w jakiej komórce (komórkach) znajduje się obiekt i wie, że na podstawie prędkości obiektów nie zmieni komórek dla bieżącej ramki, nie ma potrzeby ponownego uruchamiania logiki, która określa, w jakich komórkach znajduje się obiekt. Szybkie sprawdzenie można wykonać, tworząc obwiednię zawierającą wszystkie komórki, w których znajduje się obiekt. Następnie można utworzyć obwiednię o rozmiarze obiektu + prędkości obiektu dla bieżącej ramki. Jeśli Obwiednia komórki zawiera obwiednię obiektu + prędkość box, nie trzeba przeprowadzać dalszych kontroli. Jeśli obiekt się nie porusza, jest to jeszcze łatwiejsze i możesz po prostu użyć obwiedni obiektu.
Daj mi znać, jeśli to ma sens, lub szukaj google / bing dla "Quad Tree", lub jeśli nie masz nic przeciwko użyciu kodu open source, sprawdź tę niesamowitą bibliotekę fizyki: http://www.codeplex.com/FarseerPhysics
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-27 02:26:01
Jestem na tej samej łodzi co Ty. Próbuję stworzyć strzelankę z głową i muszę zwiększyć wydajność, aby mieć mnóstwo pocisków i wrogów na ekranie jednocześnie.
Umieściłbym wszystkie moje obiekty w tablicy z numerowanym indeksem. Daje to możliwość skorzystania z obserwacji: jeśli w pełni powtórzysz listę dla każdego elementu, będziesz powielał wysiłki. Czyli (i zauważ, że wymyślam nazwy zmiennych tylko po to, żeby łatwiej było wypluć jakiś pseudo-kod)
if (objs[49].Intersects(objs[51]))
Jest równoważne:
if (objs[51].Intersects(objs[49]))
Więc jeśli używasz numerowanego indeksu, możesz zaoszczędzić trochę czasu, nie powielając wysiłków. Do this instead:
for (int i1 = 0; i1 < collidables.Count; i1++)
{
//By setting i2 = i1 + 1 you ensure an obj isn't checking collision with itself, and that objects already checked against i1 aren't checked again. For instance, collidables[4] doesn't need to check against collidables[0] again since this was checked earlier.
for (int i2 = i1 + 1; i2 < collidables.Count; i2++)
{
//Check collisions here
}
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-03-01 18:40:06
Tylko uwaga: niektórzy sugerują farseer; który jest świetną biblioteką fizyki 2D do użytku z XNA. Jeśli jesteś na rynku silnika fizyki 3D dla XNA, użyłem bulletx (port C# bullet) w projektach XNA z wielkim skutkiem.
Uwaga: nie mam powiązania z projektami bullet lub bulletx.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-03-01 18:46:32
Pomysłem może być użycie okręgu ograniczającego. Zasadniczo, gdy tworzony jest Zderzalny, śledź jego punkt środkowy i Oblicz promień / średnicę, która zawiera cały obiekt. Możesz wtedy zrobić eliminację pierwszego przejścia używając czegoś takiego;
int r = C1.BoundingRadius + C2.BoundingRadius;
if( Math.Abs(C1.X - C2.X) > r && Math.Abs(C1.Y - C2.Y) > r )
/// Skip further checks...
To rzuca porównania do dwóch dla większości obiektów, ale ile to zyskasz, nie jestem pewien...profil!
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-26 18:30:06
Jest kilka rzeczy, które można zrobić, aby przyspieszyć ten proces... ale z tego, co widzę, twoja metoda sprawdzania prostego prostokątnego zderzenia jest w porządku.
Ale zamieniłbym czek
if (obj.Position.X ....)
Z
if (obj.Bounds.IntersercsWith(this.Bounds))
I podmieniłbym też linię
result.Add(new List<GameObject>(cell.Containing.ToArray()));
Dla
result.Add(new List<GameObject>(cell.Containing));
As the Containing property returns an ICollection<T> and that inherits the IEnumerable<T> that is accepted by the List<T> constructor.
I metoda ToArray() po prostu iteracja do lista zwracająca tablicę i th