Задача на алгоритм взаимной видимости объектов

>Перебираем все регионы

Уменьши размер региона. Можно еще деражать два списка отсоритированных по x и по y. И выбирать из них.

>Уменьши размер региона.

Да, есть такая мысль. Но - шило на мыло представляется. Более того, вполне вероятно, придётся вводить тогда два набора регионов. Сейчас, кроме поиска объектов они (регионы) используются и для нотификации активных объектов о приближении других. Входит игрок в регион - находящийся там агрессивный монстр может напасть на игрока. С малоразмерными регионами придётся просматривать не только текущий, но и соседние регионы.

>Можно еще деражать два списка отсоритированных по x и по y. И выбирать из них.

Такая мысль тоже есть.

Но, думается мне, тут менять что-то нужно глубже :D

quadtree?

>quadtree?

пошёл искать по ключевому слову :)

Эээ. Система сама по себе представляется разумной. Из добавлений могу предложить по-разному обрабатывать регионы, полностью попадающие в круг, и пересекемые его окружностью: в первых все объекты "нужные", и расстояние до каждого из них считать излишне.

Возможно, стоит сделать двухуровневую схему регионов: но у вас там, как я понял, кол-во регионов >> кол-ва объектов, т.е. это вас не спасает никак.

просто как вариант-идея : описанными регонами пользоваться только при добавлении/резком перемещении объекта;

для каждого объекта держать список объектов на расстоянии до r (R, только маленькая - минимальное типовое расстояние при поиске), для чтобы найти объекты на расстоянии не более чем r*N используются хорошо известные алгоритмы широковещательной рассылки (волновой алгоритм, обход графа/дерева etc), при незначительной плотности объектов может быть получен выигрыш в производительности. Под 'списком объектов' конечно подразумевается не линейные список, а некая дин. структура-контейнер на вкус-и-цвет, возможно просто внешняя-ассоциативная.

Конечно, как всегда, правда окажется где-то посередине: есть объекты стационарные, есть медленно движущиеся, есть быстрые и к тому-же все разделенны по приоритетам. Вообщем каждому овощу-своя грядка, возможно их стоит обрабатывать по отдельности и разными алгоритмами.

я бы сделал так (правдо не ручаюсь за эффективность).
1. Вообще не разбивать на регионы
2. Имеется индексированный список с координатами объектов, из которого можно быстро получить ORDER BY X и OEDER BY Y. Возможно этим будет заниматься некая функция.
3. Произвольно выбираем точку с координатами xr, yr.
4. Быстро находим обекты в квадрате (xr-R,yr-R) (xr-R, yr+R) (xr+R, yr-R) (xr+R, yr+R).
5. Из найденого множества в квадрате с шириной 2R с ценром в произвольной форме разбираемся с теми обектами, который попадают во вписанную окружность радиуса R.

Пока читал топик, тоже подумал об этом. Т.е. сначала ищем не в кругах, а в квадратах. Это, очевидно, проще.