Проверка на перекрытие размещения на большой сетке

Question

Я работаю над игрой, в которой вы размещаете здания, соединенные разъемами на прямоугольной сетке. Ничто не может перекрываться. Здания и соединители не могут меняться, когда они находятся в сетке; они могут быть уничтожены в любое время. Сетка определяется так, что нижний левый угол равен (0,0).

Здания представляют собой прямоугольники, каждая из которых может иметь длину 1 - 4 единицы; есть также 5x5 квадратов.

Соединители имеют начальную точку и конечную точку. Они не могут перекрываться и имеют ширину 1 единицу. Они могут идти по прямым линиям EDIT: (влево, вправо, вверх и вниз) и сгибаться везде на 90 градусов. Неограниченная длина.

Сетка в идеале должна быть довольно большой (200x200 или выше), но это означает, что может быть много тысяч этих объектов и разъемов.

Когда объект строится, мне нужно проверить, не перекрывает ли он что-либо. Если я создам сетку битов, размер ее будет непомерно большим, чем 300x300. Если я создам список всех объектов, я мог бы найти в каком-то пределе, но как я буду разбираться с коннекторами?

Невозможно видеть в виде двумерного массива битов, я должен индексировать все здания и сортировать их по координатам x, а затем по координатам y. Я мог бы выполнять линейный поиск разъемов, но это было бы очень утомительно и мучительно.

Есть ли у кого-нибудь предложение? P.S. Я делаю это в C++

Answer 1

Кроме того, 300x300 невелик, и если вы действительно хотите, чтобы вы могли упаковывать ваши логические значения в биты в байт (но я не предлагаю это по соображениям скорости), вы можете проверить, не пересекаются ли разъемы с простой функцией: https://stackoverflow.com/a/565282/2436175

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