Занимаюсь преждевременной оптимизацией (сейчас или никогда) 2д физики. Хочется разбить пространство на квадраты (клетки) и с помощью этого быстро находить соседние объекты, для детекции коллизий. Особенность в том, что будет очень много мелких объектов, одна итерации физики (обсчет за время dt) это несколько проходов (возможно >10) по всем объектам и определение коллизий. Из-за этого нужны эффективные структуры данных.
Что есть сейчас (ещё не в коде), статичный массив клеток, каждая клетка это список пересекающих её объектов. Каждый объект хранит список содержащих его клеток.
Задачи,
1. Быстрый список, не отъедающий много памяти на указатели.
Решение: Unrolled linked list
2. Быстрый пересчет списков клеток и объектов после их перемещения.
Решение: Объект хранит список пар (клетка, ссылка на ссылку на себя в этой клетке), по ссылке объект удаляется за постоянное время. При пересчете определяется новый список клеток для каждого объекта, сравнивается со старым, исчезнувшие клетки удаляются из списка и одновременно удаляются ссылки на объект из этих клеток, ну а появившиеся клетки добавляются в список вместе с соответствующей ссылкой на элемент списка клетки. И вот здесь уже есть проблема, при удалении из unrolled linked list меняется порядок элементов и ссылки будут указывать не туда куда должны. Не менять порядок элементов значит допускать пустоту в списке, нехорошо.
Иное описание проблемы, два списка, первый содержит элементы, второй ссылки на элементы первого. Как при проходе по второму списку правильно и быстро удалить соответствующие элементы первого. Вторых списков может быть много. Первых тоже. Ссылки могут быть на элементы разных первых. Использовать не unrolled списки тоже есть нехорошо.
