Какую структуру данных я бы использовал для размещения бесконечной сетки?

Question

Мне нужно выяснить, как создать бесконечную доску (вроде того, что использует wordsquared.com), которая может расширяться по требованию без потери расположения объектов, уже находящихся на доске.

Какие данныекакие структуры я буду использовать для создания аналогичной доски?

Следует также упомянуть, что мне нужно будет выполнять запросы местоположения и иметь возможность проверять окружение определенной точки.

Answer 1

Используйте список.Когда вы добавляете объект на доску, добавляйте его в список.Когда вы удалите объект с доски, удалите его из списка.Это O(1) для вставки и удаления, что так же быстро, как и получается.Каждый объект имеет (x,y) координату.

Или вы имели в виду что-то еще?Я могу ответить только на те вопросы, которые вы на самом деле задаете ...

Answer 2

Два способа, которыми я могу думать о себе:

1. Выделите пул узлов, каждый из которых имеет указатель на узел выше, ниже, слева и справа оттекущий узел.Поскольку ваша доска должна только расти, вам не придется иметь дело с какими-либо уродливыми удалениями.Для облегчения рендеринга держите указатель на верхний левый угол доски (обход прост и очевиден).

2. Выделите матрицу узлов и используйте ее как естьКогда вам нужно увеличить свою доску, выделите новую и скопируйте данные из старой в новую, прежде чем удалять ее.Это будет немного медленным при перераспределении, но облегчит взаимодействие с платой.