Как сделать 1D дискретное обнаружение столкновений максимально эффективным?

У меня следующая ситуация. В дискретной области 0, 1, ..., L имеется M независимых случайных блуждающих. Сделаем это для N одинаковых областей. В результате получается матрица X, где X[i, j] — это позиция пешехода i в домене j. Чтобы сделать случайный шаг, я добавляю матрицу идентичной формы со случайными +1 и -1 к матрице X. Затем занимаюсь краями. Это хорошо работает.

Однако я хочу расширить эту модель, чтобы иметь твердые частицы, которые не могут проходить друг через друга. Это показано в 2 случаях.

  1. Одна частица находится в позиции i, вторая в позиции i+1. Первая частица движется вправо, а вторая — влево.
  2. Одна частица находится в позиции i, вторая — в позиции i+2. Первая частица движется вправо, а вторая частица движется влево.

Если я выполняю все шаги независимо, я могу проверить каждый шаг вручную, чтобы убедиться, что это законный шаг. Однако это плохая O(M^2N) производительность. Есть ли более эффективный способ определить, какие пары матричных элементов X[i,j], X[k, j] приводят к прохождению двух частиц друг через друга, желательно векторизованным способом? Таким образом, я могу заставить симуляцию пропустить эти шаги.


python numpy collision-detection random-walk discrete-space
person R van Genderen    schedule 25.09.2020    source источник
comment
Каково ожидаемое поведение для случаев 1 и 2? Вы хотите сэмплировать до тех пор, пока не будет столкновений, или вы хотите разрешить это вручную? т.е. первый ходок идет, а второй движется в другом направлении?   -  person scleronomic    schedule 25.09.2020
comment
Я чувствую, что самый простой способ сделать это — просто не обновлять эти два шагохода для этого временного шага.   -  person R van Genderen    schedule 01.10.2020
comment
Вы добились какого-то прогресса?   -  person scleronomic    schedule 09.10.2020

Ответы (1)


arrow_upward
0
arrow_downward

Я думаю, вам нужно использовать некоторую форму циклов для достижения этого, но, возможно, это поможет:

import numpy as np
import matplotlib.pyplot as plt

L = 50
N = 30
W = 20
n_steps = 1000

# Initialize all walkers on the left side
wn0 = np.arange(W)[:, np.newaxis].repeat(N, axis=1)

# Set up the plot
fig, ax = plt.subplots()
worlds = np.zeros((N, L))
worlds[np.arange(N)[np.newaxis, :], wn0] = np.arange(W)[:, np.newaxis]
h = ax.imshow(worlds, cmap='gray_r')  # cmap='tab20')
ax.set_xlabel('Distance in 1D World')
ax.set_ylabel('Ensemble of Worlds')

for _ in range(n_steps):

    r = np.where(np.random.random(wn0.shape) < 0.5, 1, -1)

    wn1 = wn0 + r
    wn1 = np.clip(wn1, 0, L-1)

    # Case 1
    rest_mat = np.zeros_like(wn0, dtype=bool)
    for i in range(W):
        for j in range(i+1, W):
            rest_mat[[[i], [j]], np.logical_and(wn0[i] == wn1[j], wn1[i] == wn0[j])] = True
    wn1[rest_mat] = wn0[rest_mat]

    # Case 2, go from 0->W and than from W->0 to make sure all duplicates are gone
    for i in np.hstack((range(W), range(W)[-2::-1])):
        temp = (wn1[i] == wn1).sum(axis=0) > 1
        wn1[i, temp] = wn0[i, temp]

    # for wn1_j in wn1.T:  Check if there are collisions
    #     assert len(np.unique(wn1_j)) == W

    wn0 = wn1

    worlds = np.zeros((N, L))
    worlds[np.arange(N)[np.newaxis, :], wn1] = np.arange(W)[:, np.newaxis]
    h.set_data(worlds)
    plt.pause(0.1)

Случайное блуждание GIF

person scleronomic    schedule 25.09.2020