Обработка множества столкновений

@Return0 · Регистрация: 08.02.2015

Студворк — интернет-сервис помощи студентам

Есть игра на js и сервер на nodejs, на карте более 1000 обьектов и все нужно обрабатывать на столкновения, если обрабатывать все обьекты то получиться (1000^2)/2 * 30(кадров в секунду), без алгоритма слишком много вычислений и сервер начинает жутко виснуть.
Есть у меня пару идей по оптимизации, да и в интернете видел существующие алгоритмы, но хотел бы спросить у вас как бы вы это реализовали?

@TrustNo1 · 17.09.2016, 13:47

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

Можно посмотреть на игру? Пришлите в лс ссылочку

@Jewbacabra · 17.09.2016, 13:50

Не по теме:

Сообщение от Return0

Есть игра на js и сервер на nodejs

Но почему тогда вопрос в разделе php?

@Return0 · 17.09.2016, 14:08 **[ТС]**

Не совсем понял ваш совет, мне не нужен код мне нужна именно идея реализации, представте что у вас есть система координат например 6000x6000, на ней 100 обьектов, и нужно просчитать какие обьекты сталкиваются, например обьект A(100, 200) и радиус r1 = 10, и B(100, 205) радиус тоже r2 = 10, я нахожу расстояние между двумя точками по теореме векторов, пусть это будет D, потом проверяю if(r1 + r2 < D){То столкновение произошло}, так вот чтобы проверить 100 обьектов мы должны взять каждый обьект и проверить его со всеми оставшимися мы получаем (100^2)/2 = 5000 операций, если обьектов 1000, то уже пол миллиона

Добавлено через 46 секунд
Jewbacabra,
Везде раскидал, в надежде вдруг кто ответит

@TrustNo1 · 17.09.2016, 14:23

Сообщение от Return0

нужна именно идея реализации

Я имел ввиду вот что:
1) После движения объекта записывать его координаты + периметр окружности. Тогда если второй объект входит в этот периметр - значит произошло столкновение. И вычисления, которые вы писали, больше не нужны.
2) А еще можно ограничить область видимости. Как в эпохе империй было. Если действия происходят с объектами вне зоны видимости пользователя, тогда их не просчитываем (или просчитываем, но позже, по мере освобождения ресурсов)

Добавлено через 3 минуты
А все объекты одновременно движутся?

Добавлено через 57 секунд
Еще мысль появилась:
3) Разбить карту на клеточки, как в шахматах, тогда вычислений будет еще меньше

@Return0 · 17.09.2016, 14:26 **[ТС]**

А если обьектов 10, нам в любом случае прийдеться проверять все, то есть 1 обьект не знает сталкивается он с 9 другими или нет, поэтому прийдеться уже 9 операций просчитать, потом берем 2 обьект его уже с 8 другими просчитываем(т.к. с первым уже просчитали)
2 вариант более подходит но мне нужно карту всю постоянно прогружать даже если не в зоне видимости, если например человек выстрелил а пуля вылетела из его видимости ее все еще нужно прогружать, но я думаю разбить карту на зоны и по мере перемещения обьектов перемещать их координаты из этих массивов зон

@TrustNo1 · 17.09.2016, 14:41

Еще:
4) Ограничить количество возможно объектов на карте
5) Взять более мощный процессор

Идея с клеточками должна решить вопрос, как мне кажется

@wingblack · 18.09.2016, 17:50

Разбить карту на клетки с размером не менее размера объектов, в каждой клетке хранить информацию о находящихся в ней объектах, столкновения проверять только между объектами в данной клетке и соседних.

@Shamil1 · 19.09.2016, 17:18

Используйте, например, k-d tree.
1. Находите список объектов, которые потенциально могут быть столкнувшимися (используя дерево).
2. Проверяете на пересечение содержащие их кубы.
3. Проверяете на пересечение сами шары.

@Igor3D · 20.09.2016, 10:53

Сообщение от wingblack

Разбить карту на клетки с размером не менее размера объектов, в каждой клетке хранить информацию о находящихся в ней объектах, столкновения проверять только между объектами в данной клетке и соседних.

Здесь может потребоваться слишком много клеточек (кубиков) что часто делает этот способ непригодным в 3D, особенно когда сцена "sparsed" т.е. большие расстояния между объектами. Также если какие-то объекты велики, это увеличит размер клетки и в нее может попасть масса мелких объектов

Сообщение от Shamil1

Используйте, например, k-d tree.

Оно заточено на нахождение "ближайших точек". Напр центры объектов находятся далеко, но за счет размеров они могут пересекаться, тут kd-tree не поможет

Подходит OcTree или AABB tree (должно быть в CGAL). Ну все это цветочки - вот когда найдете пересечения - пойдут ягодки (не надейтесь что их будет по одному на объект). Может взять готовый движок? (напр Bullet). На мой взгляд велосипедизм здесь неуместен

@Shamil1 · 20.09.2016, 11:30

Сообщение от Igor3D

Оно заточено на нахождение "ближайших точек". Напр центры объектов находятся далеко, но за счет размеров они могут пересекаться, тут kd-tree не поможет

Я исходил из того, что максимальный размер существенно меньше размера игрового поля. Поэтому, выбирая точки на расстоянии не больше r + r_max от нашей, отсечём очень много объектов.

@Yury Komar · 21.09.2016, 18:47

а если у каждого объекта создать событие столкновенмя (Event) пускай каждый объект сам себя просчитывает по мере смены координат своих? тоесть при возникновении события смены координат совершать просчет столкновений. ведь если это игра, то не все 1000 объектов будут двигаться одновременно? а вообще, думаю нужно минимизировать вычисления. и как предложил выше TrustNo1.

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@Return0 10 / 4 / 1 Регистрация: 08.02.2015 Сообщений: 119

	Обработка множества столкновений 17.09.2016, 13:40. Показов 2598. Ответов 11 Метки нет (Все метки) Есть игра на js и сервер на nodejs, на карте более 1000 обьектов и все нужно обрабатывать на столкновения, если обрабатывать все обьекты то получиться (1000^2)/2 * 30(кадров в секунду), без алгоритма слишком много вычислений и сервер начинает жутко виснуть. Есть у меня пару идей по оптимизации, да и в интернете видел существующие алгоритмы, но хотел бы спросить у вас как бы вы это реализовали? 0

@TrustNo1 78 / 78 / 35 Регистрация: 08.09.2013 Сообщений: 397
	17.09.2016, 13:47
	Я не знаю как работают игры, но чтобы избавиться от постоянных вычислений наверное нужно заготовить заранее все возможные варианты и выдать только готовое пользователю когда это будет нужно Можно посмотреть на игру? Пришлите в лс ссылочку 1

@Return0 10 / 4 / 1 Регистрация: 08.02.2015 Сообщений: 119
	17.09.2016, 14:08 [ТС]
	Не совсем понял ваш совет, мне не нужен код мне нужна именно идея реализации, представте что у вас есть система координат например 6000x6000, на ней 100 обьектов, и нужно просчитать какие обьекты сталкиваются, например обьект A(100, 200) и радиус r1 = 10, и B(100, 205) радиус тоже r2 = 10, я нахожу расстояние между двумя точками по теореме векторов, пусть это будет D, потом проверяю if(r1 + r2 < D){То столкновение произошло}, так вот чтобы проверить 100 обьектов мы должны взять каждый обьект и проверить его со всеми оставшимися мы получаем (100^2)/2 = 5000 операций, если обьектов 1000, то уже пол миллиона Добавлено через 46 секунд Jewbacabra, Везде раскидал, в надежде вдруг кто ответит 0

@Return0 10 / 4 / 1 Регистрация: 08.02.2015 Сообщений: 119
	17.09.2016, 14:26 [ТС]
	А если обьектов 10, нам в любом случае прийдеться проверять все, то есть 1 обьект не знает сталкивается он с 9 другими или нет, поэтому прийдеться уже 9 операций просчитать, потом берем 2 обьект его уже с 8 другими просчитываем(т.к. с первым уже просчитали) 2 вариант более подходит но мне нужно карту всю постоянно прогружать даже если не в зоне видимости, если например человек выстрелил а пуля вылетела из его видимости ее все еще нужно прогружать, но я думаю разбить карту на зоны и по мере перемещения обьектов перемещать их координаты из этих массивов зон 0

@TrustNo1 78 / 78 / 35 Регистрация: 08.09.2013 Сообщений: 397
	17.09.2016, 14:41
	Сообщение было отмечено Return0 как решение Решение Еще: 4) Ограничить количество возможно объектов на карте 5) Взять более мощный процессор Идея с клеточками должна решить вопрос, как мне кажется 1

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	18.09.2016, 17:50
	Разбить карту на клетки с размером не менее размера объектов, в каждой клетке хранить информацию о находящихся в ней объектах, столкновения проверять только между объектами в данной клетке и соседних. 1

@Shamil1 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,877
	19.09.2016, 17:18
	Используйте, например, k-d tree. 1. Находите список объектов, которые потенциально могут быть столкнувшимися (используя дерево). 2. Проверяете на пересечение содержащие их кубы. 3. Проверяете на пересечение сами шары. 0

@Yury Komar Модератор 4356 / 3426 / 512 Регистрация: 27.01.2014 Сообщений: 6,257
	21.09.2016, 18:47
	а если у каждого объекта создать событие столкновенмя (Event) пускай каждый объект сам себя просчитывает по мере смены координат своих? тоесть при возникновении события смены координат совершать просчет столкновений. ведь если это игра, то не все 1000 объектов будут двигаться одновременно? а вообще, думаю нужно минимизировать вычисления. и как предложил выше TrustNo1. 0

Обработка множества столкновений

Решение