Efektywne sprawdzenie kolizji między obiektami

Cześć, mam taką zagwozdkę: powiedzmy, że mam mapę kafelkową i 100 obiektów na mapie. Każdy kafelek może być movement lub nie. Jeśli dany obiekt się porusza to naturalnie dla każdego obiektu należy sprawdzić, czy jego krawędź etc. nie leży na kafelku, który nie jest movement.
Zastanawiam się jednak jak sprawdzać, czy dany obiekt nie zderzył się z innym obiektem? Najprościej chyba porównywać każdy obiekt z każdym, ale to raczej jest mało efektywne, bo mając np. 100 obiektów muszę dla każdego z nich sprawdzać kolizję... W praktyce muszę sprawdzić jakieś (100^2)/2 porównań za każdym razem.
Inne rozwiązanie to zrobić listę wskaźników do obiektów w każdym kafelku i zapisywać do niej każdy obiekt, który znajduje się nad danym kafelkiem a następnie porównywać tylko te obiekty, które są na tym samym kafelku.

A czy jest lepsze rozwiązanie? Jak Wy byście to rozwiązali?

Jak zrobić to, by było w miarę efektywnie a jednocześnie "profesjonalnie"? ;-)

Z góry dzięki za pomoc.

Z grubsza jakaś właśnie modyfikacja tego drugiego rozwiązania jest używana zwykle jako pierwsza faza (eliminacji) wykrywania kolizji. Przy czym trzeba sprawdzać też z obiektami z sąsiednich kafelków i zapewnić, że promień obiektu nie jest większy od rozmiaru kafelka. Mogą też być hierarchie kafelków (większy dzieli się na 4 itd.), żeby obsługiwać obiekty o różnych zakresach wielkości. Sporo może też zależeć od tego, jaki jest koszt takiego uproszczonego sprawdzenia w porównaniu z kosztem sprawdzania pełnego, np. inaczej będzie dla kół 2D, a inaczej dla wielościanów wypukłych w 3D.

Mogą też być hierarchie kafelków (większy dzieli się na 4 itd.), żeby obsługiwać obiekty o różnych zakresach wielkości.

Formalnie nazywa się to http://pl.wikipedia.org/wiki/Drzewo_ósemkowe

Najprostsze rozwiązanie jakie mi przyszło do głowy.
Proponuję dla mapy utworzyć tablicę i trzymać tam informacje czy można wejść na dany kafelek czy nie.

Na przykład (C#):

int[,] myMap = new int[5,5]
{
	{ 1, 0, 0, 0, 0 },
	{ 1, 1, 1, 0, 0 },
	{ 0, 0, 1, 0, 0 },
	{ 0, 0, 1, 1, 1 },
	{ 0, 0, 0, 0, 0 }
};

Jeśli gracz chce iść w prawo to sprawdzasz jaka jest wartość na prawo od gracza.
Jeśli jest to 1 to może iść, jeśli jest to zero to nie może przejść.