Обработка столкновений объектов в 2D-сетке

Согласно обсуждению с OP, объекты следует перемещать таким образом, чтобы максимизировать количество всех перемещенных объектов.

Объекты со своими ссылками образуют лес деревьев. Если объект A ссылается на ячейку, занятую объектом B, мы можем сказать, что B является родителем объекта A в дереве. Таким образом, объекты соответствуют узлам, а ссылки соответствуют ребрам в деревьях. В корне каждого дерева будет некоторая пустая ячейка (на самом деле это тот случай, когда пустая ячейка соответствует узлу). Деревья не имеют общих узлов.

Прежде чем двигаться дальше, мы должны признать, что могут быть ситуации с циклами. Как это:

[A] -> [B]                 
 ^      v       or     [A] <=> [B]
[D] <- [C]                 

Такие циклы легко идентифицировать. Некоторые объекты могут прямо или косвенно ссылаться на объекты цикла, а также формировать дерево. Цикл может происходить только в корне дерева.

Допустим, мы построили все деревья. Теперь возникает вопрос: Как мы можем разрешать коллизии? имея в виду, что мы хотим максимизировать количество перемещенных узлов. Столкновения соответствуют узлу, имеющему более 1 дочернего элемента.

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

В дереве пустой корневой ячейки сначала мы должны решить, какой корневой дочерний элемент будет помещен в корневую пустую ячейку. Затем у нас появится новая пустая ячейка, где мы должны будем принять такое же решение. И так далее до листового узла. Чтобы максимизировать количество перемещенных узлов, мы должны взять самую длинную цепочку от корня до некоторого листа и переместить ее узлы. Все остальные узлы не двигаются. Это можно легко сделать, пройдя по дереву с помощью некоторой рекурсивной функции и вычислив следующую функцию f для каждого узла f_leaf = 0 и >f_узел = MAX(f_{дочерний элемент1}, f_{дочерний элемент2}, ...) + 1. Таким образом, вышеупомянутое решение заключается в выборе дочернего узла с самым большим f.

    *
   /|\
  A B C         The optimal move path  is   * <- C <- E <- H
 /   /|\
D   E F G
   /
  H

Проверка «заблаговременно»/«следующий шаг» приведет к сложным вычислениям и даже взрывам.

Вместо этого вы можете (параллельно) использовать проверку «какая частица может двигаться в это место?» на каждую ячейку. Для этого вам понадобится карта скоростей с вектором скорости в каждой ячейке. Затем, следуя этому вектору в обратном направлении, вы замечаете ячейку. Если есть частица, попасть в клетку.

Таким образом, коллизий не происходит, потому что выполняется только 1 действие на ячейку. Просто получите ближайшую ячейку от конечной точки отрицательного вектора скорости.

Это несколько сложно вычислить, так как скорость может не попасть точно в центр ячейки. Нужна вероятность (если она очень близко к углам, чем к центру) для равенства движения / макроэффектов.

Таким образом, будет состояние гонки только для индекса ячеек, и это будет допускаться случайностью движения (или выбором частиц в зависимости от расстояния от центра ячейки).

В квантовой физике частицы могут перепрыгивать через стену, стоять на месте (даже если этого не должно быть) и делать некоторые другие вещи, которые не являются естественными для классической физики. Так что, если разрешение высокое, а скорость не выше размера карты, это должно выглядеть естественно, особенно со случайностью, когда несколько ячеек конкурируют за получение частицы из другой ячейки.

Несколько проходов:

• рассчитать, какие ячейки нужно собрать из каких ячеек,
• рассчитать вероятности, а затем выигрышные ячейки
• ячейки выигрыша собирают свои частицы из исходных ячеек параллельно.
• (не рекомендуется), если все еще есть не выбранные частицы со скоростью, то выполнение вычислений для каждой частицы для их перемещения (если их целевая ячейка пуста) должно еще больше уменьшить стационарные частицы.
• рассеять скорости частиц по ячейкам несколько раз (используя 2D-трафарет), которые будут использоваться в следующей итерации (это легко обрабатывает сложные расчеты столкновений и смущающе параллельным способом, хорошо подходит для многопоточности-gpgpu) (если частицы могут двигаться только ближайшим соседям, это также помогает узнать, какой из них, даже без какого-либо приоритета или вероятности, поскольку каждая ячейка изгибает скорости соседних ячеек с помощью диффузии скоростей)

проверить Гаусса-Зейделя (https://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method) для решения многих линейных уравнений.

вычисления выполняются на ячейках, а не на частицах, поэтому границы карты будут неявно пуленепробиваемыми, а вычисления могут быть равномерно распределены между всеми ядрами.

Пример:

частица А падает

частица B движется вправо

они на пути к столкновению

решить для состояния равновесия карты скорости (Гаусс-Зейдель)

теперь ячейка частицы А имеет скорость вниз+вправо

то же, что Б

как будто они столкнулись, но они все еще на своих ячейках.

Перемещение их со скоростью их клеток заставит их выглядеть так, как будто они находятся в столкновении.