Zwei Listen gegeneinander prüfen

Häufig müssen die Einträge zweier Listen miteinander verglichen werden oder jeder Eintrag einer Liste soll mit allen anderen Einträgen der Liste verglichen werden. Dabei möchte man natürlich möglichst wenige Prüfungen durchführen und genau dies möchte hier ich zeigen.

Als Beispiel nehmen wir die Kollisionsprüfung. Wir haben eine Liste, in der sich alle auf Kollision zu prüfenden Objekte befinden. Mit einer einfachen, geschachtelten Schleife können wir nun jeden Eintrag mit jedem vergleichen.

foreach (Enemy enemy1 in myEnemyList) 
{ 
  foreach (Enemy enemy2 in myEnemyList) 
  { 
    if (enemy1 != enemy2 && enemy1.Intersects(enemy2)) 
    { 
         // mach was... 
     } 
  } 
}

Dieser Code sollte mehr oder weniger selbsterklärend sein. Es wird beachtet, daß nicht auf Kollision mit dem Objekt selbst geprüft wird.

Ist dies nun die beste Lösung? Nein, denn sonst würde ich diese rhetorische Frage sicherlich nicht stellen. Folgendes passiert mit diesem Code, wenn 5 Objekte in der Liste sind. Die Zahlen sind jeweils ein Index eines Eintrages in der Liste.


1 2
1 3
1 4
1 5
2 1
2 3
2 4
2 5
3 1
3 2
3 4
3 5
4 1
4 2
4 3
4 5
5 1
5 2
5 3
5 4

Wie wir sehen, müssen 20 Prüfungen durchgeführt werden und wenn man sich das etwas genauer betrachtet, dann sieht man, daß sowohl Objekt 1 mit Objekt 2 verglichen wird, als auch Objekt 2 mit Objekt 1. Dies ist aber meistens unnötig, wir wollen folgendes:


1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

da wir so lediglich halb soviele Prüfungen benötigen.

Dies ist relativ einfach möglich und zwar mit folgendem Code:

int countEnemies = m_Enemies.Count; 
for(int i = 0; i < countEnemies - 1; i++) 
{ 
   for(int ii = (i + 1); ii < countEnemies; ii++) 
   { 
     if (myEnemyList[i].Intersects(myEnemyList[ii]))
     {
       // mach was... 
     }
   } 
} 
Advertisements

Veröffentlicht am 28.02.2010 in C#, Grundlagen, Grundlagen, Kollision, Mini-Tutorial, Optimierung, XNA und mit , , , getaggt. Setze ein Lesezeichen auf den Permalink. Hinterlasse einen Kommentar.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: