Как при движении объекта переносить запись о нем в соответствующий массив?

Question

[Ди Ма]

Добрый день!

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

Но сами объекты не удобно хранить в матрице. Объекты хранятся в одном месте, а в матрице только их имена.

Если объект движется, то как переносить его имя из ячейки в ячейку? Не проверять же каждый раз, в своей ли он клетке..

Answer 1

[GreatRash]

1) Нужна не сетка, а т.н. "дерево квадрантов" или, на языке вероятного противника - quadtree.
2) В этих ваших ютубах есть отличный туториал на тему построения такого дерева. Ну и вообще можно погуглить по запросу "javascript quadtree collision detection".
3) Вот я даже нагуглил за вас реализацию сего принципа. В демке коллизии проверяются только внутри зелёного прямоугольника, остальное игнорируется движком. На этом и построен принцип использования дерева квадрантов.

Comments

[Ди Ма]

Спасибо, это интересно, но пока не очень понятно. Буду читать)

Answer 2

[Даниил Басманов]

Эта оптимизация называется space partitioning, один из её минусов это необходимость обновления информации о положении объектов. Есть нюансы реализации, конечно, но в целом так и делают, двигают объект, а потом обновляют положение в матрице или дереве. Вообще говоря, если вам это нужно для столкновений, то лучше брать готовый физический движок, если вы не хотите угробить несколько месяцев на оптимизацию и тестирование.

Comments

[Ди Ма]

Спасибо)
Игру писать пока не планирую. Просто показалась интересной задача