Coś pochodnego BSP, albo OctTree. Dzielisz planszę wg każdej osi na połowę. Zapisujesz sobie to w postaci drzewa. Jeśli w którejś połowie nikt nie był, wskaźnik na tą połowę jest nil, jeśli był, wskaźnik na tę połowę jest wskaźnikiem na opis połówek tej połowy. itd.
Planszę 2D możesz dzielić albo na ćwiartki albo wg. dwóch drzew - po jednym do każdej osi.
TElement = array[0..3] of Pointer;
Jeśli w danej ćwiartce nikt nie był, wartość pola jest nil, jeśli był, pole wskazuje na taką samą tablicę dla mniejszego podziału.
Taka metoda jest dobra, jeśli postać nie jest w stanie zająć całej planszy. Jeśli jest, warto dodać jeszcze jedno pole - jeśli gracz był we wszystkich ćwiartkach danego obszaru, pola są ustawiane na nil (kasowanie podtablic), a zmienna jest ustawiana - cały zapełniony obszar nie wymaga więc podtablic.
Podział na podtablicę powinieneś u siebie zrobić do 14 stopnia, bo 2^14> 10000; Wtedy tablica 14 stopnia będzie dla 4 obszarów 1x1.
DOPISANE:
Załóżmy, że obszar dzielimy na ćwiartki numerowane:
1 0
2 3
Załóżmy taki obszar:
Dla niego można by na przykład zrobić coś takiego:
TElement = packed record
PodObszary: array[0..3] of Pointer;
Zajety: boolean;
end;
Dla tej mapy wynik w pamięci może być taki (@ADRES: [PodObszar0, PodObszar1, PodObszar2, PodObszar3], Zajety):
@0: [nil, 1, 2, -1], FALSE //Cała mapa
@1: [nil, -1, nil, -1], FALSE //Podobszar1
@2: [-1, nil, nil, nil], FALSE //Podobszar2
Zauważ, że w dalszych podziałach już nie dzielisz Podobszar0, bo wg mapy głównej jest pusty (nil) - nigdy tam nie było zapisu, oraz PodObszar3, bo wg mapy głównej ma -1, w więc jest cały zajęty. Pozostałę 2 podobszary dzielisz na takiej samej zasadzie. Tutaj mapa jest 4x4 więc robisz tylko 2 podziały (2^2) - główny i ćwiartek, przy mapie 8x8 miałbyś jeszcze ćwiartki ćwiartek, itd.
Musisz też zadbać, by żaden element nie miał adresu -1 (co przy niejednobajtowym rozmiarze rekordu już samo przez się nie jest możliwe).
Jeśli ktoś dużo będzie zwiedzał pewien obszar powiedzmy w rogu lewym, górnym, pamięci w ogóle nie będzie zajmowała część prawa czy dolna (czyli oszczędzasz informacje o 3 ćwiartkach dużej mapy i iluś podpodpodziałach w lewej górnej części.
Ale zamieszałem..