Секционная разбивка
Вложений: 2
Здравствуйте.
Речь зайдет о секционной разбивке поля. Что это такое? Чаще всего нужно для проверки коллизий, и подобных задач, когда множество объектов необходимо проверить с учетом расстояния и подобных задач. Как это работает: 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) // готовим ячейку и заодно узнаем скока всего объектов в ней Эти функции не для работы с сеткой, но они есть, поэтому я их опишу. 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 спасибо, нужная штука !!
Цитата:
|
Re: Секционная разбивка
полный перебор только один раз - чтобы занести объекты в ячейки сетки.
Далее, если нам надо проверить 10 каких то объектов (а у нас их например 10000), то нам уже ненаждо прогонять 10*10000 раз. а достаточно проверить только те, которые находятся в ближайших ячейках. (а представь, если надо 10000 * 10000 проверить?), вот тут уже начинается чудовищная оптимизация. |
Ответ: Секционная разбивка
Хотел было создать тему по самому важному в Blitz3D :
"Оптимизация, разбиение объектов по секциям"! ведь в последнее время все обсуждения к этому и ведут Но воспользовался поиском и нашёл здесь ответ. Спасибо HolyDel! Может тему поднять и закрепить как важное? Перебор всё же будет по всем (+100700) объектам типов. Но так можно упростить "физику", используя её только для нужных объектов. А если эти объекты статичны, то вроде всё будет намного легче? |
Ответ: Секционная разбивка
лучше юзать не просто сетку, а квадтри/BVH
|
Ответ: Секционная разбивка
Вложений: 1
Сделал 3Д пример секционной очистки статических объектов.
Пересчёт For Count = 1 To 500 и более делается СОВСЕМ один раз, при инициализации программы! Функции wlakи написаны не так красиво. В них по клеткам определяется скрывать или нет. # скрывать ~ рисовать И игрок ##### #~~~# #~И~# #~~~# ##### Движение - клавишами стрелок или мышью. Квадратики окрашены: вверх зеленее вправо краснее |
Ответ: Секционная разбивка
HolyDel не вводи людей в заблуждение, скажи прямо: Это двухмерный массив с произвольным числом элементов в ячейке.
Секционную разбивку поля эта dll-ка не делает, а только хранит информацию о ней. Хорошо подойдет для статичных объектов (движущиеся все равно надо пересчитывать). |
Ответ: Секционная разбивка
на рисунке: Игрок двигается вправо, слева скрыты дальние объекты. Качать здесь. (exe-пример без алгоритма оптимизаций, ранняя версия заготовки) Это двухмерный массив с произвольным числом элементов в ячейке. +Отличие - произвольное количество X/Y ячеек. Не нужно заранее инициализировать количество ячеек: если располагается новый объект в неподготовленной ячейке - добавляется эта ячейка в цепь массива. Пишу на Delphi (первый опыт dll). В планах: попадание ячейки в угол обзора (иначе скрывать). Пока хотя бы "входит ли точка (центр ячейки) в треугольник (угол обзора)" |
Ответ: Секционная разбивка
|
Ответ: Секционная разбивка
Цитата:
Цитата:
|
Ответ: Секционная разбивка
Цитата:
Всмысле "Готовим ячейку"? На медленном огне чтоль? ))) П.с. Поф насколько тупой метод, главное чтобы быстро работал) |
Часовой пояс GMT +4, время: 17:56. |
vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot