JavaScript: Обнаружение коллизий
кто-то мог помочь мне понять, как обнаружение коллизий работает в JS? Я не могу использовать jQuery или gameQuery - уже использование прототипа - так, я ищу что-то очень простое. Не прося полное решение, просто укажите на меня на правильное направление.
Скажем, существует:
<div id="ball"></div>
and
<div id="someobject0"></div>
Теперь шар перемещается (любое направление). "Someobject"(0-X) уже предопределен и существует 20-60 из них случайным образом расположены как это:
#someobject {position: absolute; top: RNDpx; left: RNDpx;}
Я могу создать массив с "someobject (X)" положения и протестировать коллизию, в то время как "шар" перемещается... Что-то как:
for(var c=0; c<objposArray.length; c++){
........ and code to check ball's current position vs all objects one by one....
}
Но я предполагаю, что это было бы решением "новичка", и это выглядит довольно медленным. Есть ли лучше что-нибудь?
2 ответа
Первое, что нужно сделать have - это фактическая функция, которая определит, есть ли у вас столкновение между мячом и объектом.
Для повышения производительности было бы здорово реализовать некоторую грубую технику обнаружения столкновений, например ограничивающие прямоугольники , и более точный, если необходимо, в случае обнаружения столкновения, чтобы ваша функция бежать немного быстрее, но используя точно такой же цикл.
Другой вариант, который может помочь повысить производительность, - это выполнить некоторую предварительную обработку с имеющимися у вас объектами. Например, вы можете разбить всю область на ячейки, как в общей таблице, и сохранить соответствующий объект, который содержится в определенных ячейках. Поэтому для обнаружения столкновения вы определяете ячейки, занятые мячом, извлекаете объекты из этих ячеек и используете функцию обнаружения столкновений.
Чтобы еще больше ускорить его, вы можете реализовать 2d-дерево , квадродерево или R-дерево .
Это простой способ, который неэффективен, но вполне разумен, когда вам не нужно ничего слишком сложного или у вас мало объектов.
В остальном существует много разных алгоритмов, но большинство из них довольно сложно реализовать.
Например, вы можете использовать подход Разделите и Импера , в котором вы группируете объекты иерархически в соответствии с их расстоянием и вы даете каждому кластеру ограничивающую рамку, которая содержит все элементы кластера. Затем вы можете проверьте, какие кластеры сталкиваются, и избегайте проверки пар объектов, принадлежащих кластерам, которые не сталкиваются / не перекрываются.
В противном случае вы можете придумать общий алгоритм разделения пространства, чтобы аналогичным образом разделить объекты, чтобы избежать бесполезных проверок. Такого рода алгоритмы разделяют обнаружение столкновений на две фазы: грубый , в котором вы видите, какие объекты могут сталкиваться, и точный , в котором вы эффективно проверяете отдельные объекты. {{1 }} Например, вы можете использовать википедию QuadTree , чтобы найти простое решение.
Взгляните на страницу википедии , она может дать вам несколько советов.