Интересна ситуация,
наихудшая для оптимизации: когда за 1 кадр может поменяться максимальное число связей. Предположу, что это сетка из равносторонних треугольников, где длина ребра равна «триггерной» дистанции:
картинка треугольной сетки Тут большинство точек, кроме крайних, взаимосвязаны. У каждой по 6 ближайших соседей. Примерно
200 * 6 / 2 = 600 связей (чуть меньше из-за краёв).
Если такую сетку пропорционально увеличить на любую малую величину, сразу все связи порвутся, их станет ноль. Пусть на месте останется, скажем, левый верхний угол сетки. Тогда наибольший путь проделает нижний правый угол. Тут вопросы к особенностям вашей задачи:
- округляются ли координаты до целых или до какой-то точности?
- какой наибольший путь может проделать за один кадр точка?
В идеальном мире всем достаточно проделать бесконечно малый шаг, и, вуаля!, было 600 связей, стало 0. Такой же шажок назад – не было связей, и вот их 600. Т.е. надо бы в каждый кадр проверять 600 ребер. Считать это за теоретический предел оптимизации?
Сущности
Точки и рёбра. Ребро ссылается на две точки. Точка ссылается на рёбра. Ребро имеет длину и, в зависимости от длины, может быть «видимым».
Важнее всего следить за рёбрами, длина которых близка к пороговой – и с меньшей и с большей стороны. Такие стоит проверять почти каждый кадр, т.к. статус ребра может поменяться за один кадр. Прочие рёбра и кандидаты в рёбра проверять можно изредка.
Можно давать рёбрам веса, пропорциональные желаемой частоте их обновления. Скажем, от 0 до 1. Вес равный 1 значит, что нужно проверять каждый кадр. Например, вес
W = Math.max(0, D - Math.abs( length - D))/D, где D – пороговая дистанция.
Остаётся сделать механизм, отбирающий рёбра в работу на очередном кадре, исходя из их весов. Запоминать время, когда ребро было обновлено. Приоритет его попадания в обработку равен
W * (time - timeUpdated)
