forum.boolean.name - Секционная разбивка

forum.boolean.name (http://forum.boolean.name/index.php)

- Библиотеки (http://forum.boolean.name/forumdisplay.php?f=28)

- - Секционная разбивка (http://forum.boolean.name/showthread.php?t=4545)

Секционная разбивка

Здравствуйте.
Речь зайдет о секционной разбивке поля. Что это такое?
Чаще всего нужно для проверки коллизий, и подобных задач, когда множество объектов необходимо проверить с учетом расстояния и подобных задач.
Как это работает:
1.необходимо отчистить поле
2.в ячейку поля нужно добавить объект, но только в ту ячейку «над» которой он находится.
3.При проверке, проверять не все объекты, а только те, которые находятся в ближайших ячейках.
Вообще значительно проще будет понять суть посмотрев пример в аттаче (там же и либа).
В примере:
Вы возите зеленый круг
Сами по себе ездят «огоньки», внутри которых записан их счет.
Считается сумма всех огоньков, которые находятся внутри зеленой окружности.
Обычно, для этого надо было перебрать все огоньки и проверить их расстояние до центра окружности, если оно меньше, то прибавляем к сумме, его очки. Теперь это делается несколько иначе. Т.е. Используя секционную разбивку.
Вообще там прокомментированы необходимые участки. Плюсы – увеличение быстродействия при большом количестве объектов и большой карте, возможно разбитой на много участков.

Синтаксис команд либы:

InitMap%(width,height) – инициализирует 2д карту, соответственно width * height размерностью. В случае успешной инициализации возвращает 1, в случае неудачной – 0;
DeInitMap%() - итак ясно.
ClearMap%() - отчищает всю карту.
ClearCell%(i%,j%) - отчищает ячейку на позиции i и j.
PushToMap%(i%,j%,value%) - добавляет в i,j -итую ячейку значение value. К значению нет никаких условий. Их можно записывать хоть сколько.

PrepareCell%(i%,j%) - подготавливает ячейку. Возвращет число элементов в ней.

PopValue%(i%) - сначала надо подготовить ячейку. Когда ячейка подготовленна, то можно получать конкретные значения, примерно таким макаром:

Код:

tt=PrepareCell(i,j) // готовим ячейку и заодно узнаем скока всего объектов в ней

        For k=0 To tt-1

                a=PopValue(k) // в а будут постепенно записаны все объекты из этой ячейки

        Next

этот код конечно бессмысленный, но так, просто чтобы показать.

Эти функции не для работы с сеткой, но они есть, поэтому я их опишу.
Dist#(x1#,y1#,x2#,y2#) - возвращает дистанцию между двумя точками
Dist3D#(x1#,y1#,z1#,x2#,y2#,z2#) - тоже самое тока в 3д
Insect2D%(r#,x#,y#,x1#,y1#,x2#,y2#) - проверяет , не пересекает ли отрезок с концами в (x1,y1)(x2,y2), окружность с центром (x,y) и радиусом r.
Insect3D%(r#,x#,y#,z#,x1#,y1#,z1#,x2#,y2#,z2#) - тоже самое тока в 3д.

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

Спасибо за внимание, пример демонстрирующий приемущества напишу завтра.

upd: насчет примера.
там space - остановить их перемещения.
большие зеленые клетки - ето те ячейки , которые обрабатываются.

Re: Секционная разбивка

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

Re: Секционная разбивка

Да но от полного перебора то неуйти :)
А функции коллизий в блитцах всегда сначала проверяют на пересечение ограничивающих прямоугольников/кубов.

Нужно делать тест обычного варианта проверки и вашего..и судить по результатам о востребованности...

Вот например таблицы синусов/косинусов в блитзмаксе нерулят ибо реализация доставания нужного значения из таблицы тормазит больше прямого расчёта значения.

Re: Секционная разбивка

SBJoker , не понял то есть не имеет смысла сохдавать sin[360] & cos[360]?
А по теме.. это один из самых древних способов оптимизации, странно что до HolyDel-а никто такой либы не делал.

Re: Секционная разбивка

Делали конечно, но тут нестандартный подход...
Вечером буду разбираться глубже.
Полный перебор - это не страшно. Обычно делается за несколько циклов, ведь камера не может мгновенно перелететь из зоны А в зону В, поэтому перебор можно растянуть по циклам, так что он вообще не займет времени.

Re: Секционная разбивка

HolyDel спасибо, нужная штука !!

Цитата:

странно что до HolyDel-а никто такой либы не делал

to dimanche13: я давно пытался :), но так и незакончил !!

Re: Секционная разбивка

полный перебор только один раз - чтобы занести объекты в ячейки сетки.
Далее, если нам надо проверить 10 каких то объектов (а у нас их например 10000), то нам уже ненаждо прогонять 10*10000 раз. а достаточно проверить только те, которые находятся в ближайших ячейках. (а представь, если надо 10000 * 10000 проверить?), вот тут уже начинается чудовищная оптимизация.