Jak w grze opartej na kafelkach 2D NPC i kafelki powinny się nawzajem odnosić?

Robię silnik kafelkowy dla odgórnych gier 2D. Zasadniczo świat składa się z siatki płytek.

Teraz chcę umieścić na przykład NPC, którzy mogą poruszać się po mapie.

Co uważasz za najlepsze:

1. każdy kafelek ma wskaźnik do NPC znajdującego się na jego kafelku lub wskaźnik NULL
2. z listą NPC i mają współrzędne kafelka, na którym się znajdują.
3. coś innego?

Myślę

1. jest szybszy w wykrywaniu kolizji, ale zużyłby dużo więcej pamięci i wolniej znajdowałby wszystkich NPC na mapie.
2. jest odwrotnie.

Dlaczego nie oba? Są chwile, w których będziesz chciał sprawdzić, czy na danym kafelku jest jakiś NPC (na przykład do wykrywania kolizji), a innym razem, gdy będziesz chciał iterować wszystkich NPC na świecie ( takich jak uruchamianie metod AI w każdej ramce).

Wskaźnik na kafelek nie ma tyle pamięci, chyba że pracujesz na platformie z ograniczoną pamięcią lub masz naprawdę ogromną mapę.

Jak radzisz sobie z kolizjami z mapą? Jeśli masz warstwę kolizyjną, bardzo łatwym sposobem byłoby najpierw utworzenie listy NPC ze współrzędnymi wskazującymi, na której płytce się znajdują, a następnie iterowanie tej listy i oznaczenie płytki warstwy kolizyjnej pod NPC jako płytkę kolizyjną. W ten sposób kolizje z NPC będą obsługiwane w tym samym czasie, co reszta mapy. Oczywiście jeśli NPC się nie ruszą ...