Bounty
Этот вопрос вызывает несколько вопросов. Щедрость будет идти к ответу, который обращается к ним целостно.
Здесь проблема, с которой я играл.
ПРИМЕЧАНИЕ Меня особенно интересуют решения, которые не основаны в евклидовом пространстве.
Существует множество Актеров, которые образуют толщу размера K. Расстояние d(ActorA,ActorB) легко вычислимо для любых двух участников (решения должны работать для различных определений "расстояние" ), и мы можем найти множество N ближайших соседей для любого данного Актера, использующего любой из установленных алгоритмов.
Этот соседний набор корректен в первый момент, но Актеры всегда двигаются, и я хочу поддерживать меняющийся список N ближайших соседей для каждого Актера. Меня интересуют приблизительные решения, которые более эффективны, чем идеальные решения.
- Решения должны сходиться к правильности после появления ошибок.
- Допустимо иногда выполнять полную перерасчету, если ошибки становятся слишком большими, но обнаружение этих ошибок должно быть дешевым.
До сих пор я использовал алгоритм friend-of-a-friend:
recompute_nearest (Actor A)
{
Actor f_o_f [N*N];
for each Actor n in A.neighbours
append n to f_o_f if n != A and n not in f_o_f
Distance distances [N*N];
for 0 <= i < f_o_f.size
distances [i] = distance (A, f_o_f [i])
sort (f_o_f, distances)
A .neighbours = first N from f_o_f
}
Это хорошо работает, когда толпа медленно движется, а N достаточно велика. Он сходится после небольших ошибок, удовлетворяющих первым критериям, но
- У меня нет хорошего способа обнаружить большие ошибки,
- У меня нет количественного описания размера и частоты ошибок,
- он сходится на практике, но я не могу доказать, что он всегда будет.
Можете ли вы помочь с любым из этих пунктов?
Кроме того, вы знаете какие-либо альтернативные подходы, которые хорошо работают
- когда толпа быстро движется,
- когда некоторые участники быстро движутся,
- когда N мало,
- когда толпа в некоторых местах скудна и плотная в других,
- или с конкретными алгоритмами пространственного индексирования?
Расширение, над которым я сейчас работаю, заключается в том, чтобы обобщить друга друг друга, чтобы взять друга друг друга в случаях, когда сосед быстро перемещается. Я подозреваю, что это не масштабируется, и трудно получить правильные параметры без количественного определения ошибок.
Я приветствую все предложения! Это забавная небольшая проблема: -)
Известные предложения до сих пор
Fexvez: выбор случайных дополнительных соседей, размер выборки в зависимости от скорости Агента. Выборка из области, в которой он собирается двигаться, вероятно, также поможет.
Повторите выбор соседей, когда агенты speed*delta_time превышают расстояние до самого дальнего известного соседа.
Поддерживайте триангуляцию Delaunay, которая является надмножеством графика ближайшего соседа. Учитывается только ближайший сосед один.
Дэвид Маунт Библиотека ANN Кажется, что не обрабатывает тела движущиеся.
