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 проверить?), вот тут уже начинается чудовищная оптимизация.

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

Хотел было создать тему по самому важному в Blitz3D :
"Оптимизация, разбиение объектов по секциям"!
ведь в последнее время все обсуждения к этому и ведут

Но воспользовался поиском и нашёл здесь ответ.

Спасибо HolyDel!

Может тему поднять и закрепить как важное?

Перебор всё же будет по всем (+100700) объектам типов.
Но так можно упростить "физику", используя её только для нужных объектов.
А если эти объекты статичны, то вроде всё будет намного легче?

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

лучше юзать не просто сетку, а квадтри/BVH

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

Сделал 3Д пример секционной очистки статических объектов.

Пересчёт For Count = 1 To 500 и более делается СОВСЕМ один раз, при инициализации программы!

Функции wlakи написаны не так красиво. В них по клеткам определяется скрывать или нет.

# скрывать
~ рисовать
И игрок

#####
#~~~#
#~И~#
#~~~#
#####

Движение - клавишами стрелок или мышью.
Квадратики окрашены:
вверх зеленее
вправо краснее

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

HolyDel не вводи людей в заблуждение, скажи прямо: Это двухмерный массив с произвольным числом элементов в ячейке.
Секционную разбивку поля эта dll-ка не делает, а только хранит информацию о ней. Хорошо подойдет для статичных объектов (движущиеся все равно надо пересчитывать).

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

на рисунке: Игрок двигается вправо, слева скрыты дальние объекты.

Качать здесь.
(exe-пример без алгоритма оптимизаций, ранняя версия заготовки)

Это двухмерный массив с произвольным числом элементов в ячейке.
+Отличие - произвольное количество X/Y ячеек. Не нужно заранее инициализировать количество ячеек: если располагается новый объект в неподготовленной ячейке - добавляется эта ячейка в цепь массива.

Пишу на Delphi (первый опыт dll).
В планах:
попадание ячейки в угол обзора (иначе скрывать). Пока хотя бы "входит ли точка (центр ячейки) в треугольник (угол обзора)"

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

Цитата:

Как в этой либе прально узнать сколько рыл находится в конкретной ячейке?

Цитата:

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

да это самый тупой метод. да, посути это просто двухмерный массив. раньше это казалось крутым :)

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

Цитата:

Сообщение от HolyDel (Сообщение 215658)

PHP код:


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

да это самый тупой метод. да, посути это просто двухмерный массив. раньше это казалось крутым :)

Всмысле "Готовим ячейку"? На медленном огне чтоль? )))
П.с. Поф насколько тупой метод, главное чтобы быстро работал)

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

ну ладно, подготавливаем.

самое основное это ответ на твой вопрос - "и заодно узнаем скока всего объектов в ней". работает быстро.

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

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

Код:

Global maxArrayX

Global maxArrayY

Global maxArrayThings

Global ArrayStartX                        = 0

Global ArrayStartY                        = 0

Global ArrayStepX                 = 10 

Global ArrayStepY                        = 10

Global ArrayHeroRadiusX        = 1

Global ArrayHeroRadiusY        = 1

Global maxArrayParams        = 3

Dim ThingsArray(maxArrayX,maxArrayY,maxArrayThings,maxArrayParams)

Const ArrayThingType = 0, ArrayThingHNDL = 1, ArrayThingCnt=2, ArraySingleMesh=3



Function InitArrayThings(x, y, thingsCnt)

        Dim ThingsArray(0,0,0,0)

        maxArrayX = x

        maxArrayY = y

        maxArrayThings = thingsCnt

        Dim ThingsArray(maxArrayX,maxArrayY,maxArrayThings,maxArrayParams)

End Function



Function GetArrayX(x#)

        Return Floor ((x - ArrayStartX) / ArrayStepX)

End Function



Function GetArrayY(y#)

        Return Floor ((y - ArrayStartY) / ArrayStepY)

End Function



Function AddThingToArray(HNDL)

        Local dx#,dy#,dz#,cnt

        

        Local t.ThingT = Object.ThingT(HNDL)

        dx = GetArrayX(xEntityX(t\ent,1))

        dy = GetArrayY(xEntityZ(t\ent,1))

        If dy>=0 And dx>=0 And dy <= maxArrayY And dx <= maxArrayX Then

                If ThingsArray(dx,dy,0,ArrayThingCnt) < maxArrayThings Then

                        ThingsArray(dx,dy,0, ArrayThingCnt) = ThingsArray(dx,dy,0, ArrayThingCnt) + 1

                        cnt = ThingsArray(dx,dy,0, ArrayThingCnt)

                        ThingsArray(dx,dy,cnt, ArrayThingType) = t\typ

                        ThingsArray(dx,dy,cnt, ArrayThingHNDL) = HNDL

                        t\ArrayX = dx

                        t\ArrayY = dy

                        t\ArrayNum = cnt

                        Return True

                Else

                        ;RuntimeError("no more things to array.")

                        Return False

                EndIf

        Else

                ;RuntimeError("thing out from array.")

                Return False

        EndIf

End Function



Function MergeThingArray(HNDL,n,x,y)

        FreeThingFromArray(x,y,n)

        AddThingToArray(HNDL)

End Function



Function FreeThingFromArray(x,y,n)

        Local cnt, k, t.ThingT

        cnt = ThingsArray(x,y,0,ArrayThingCnt)

        If n = cnt Then

                ThingsArray(x,y,n,ArrayThingType) = 0

                ThingsArray(x,y,n,ArrayThingHNDL) = 0

        Else

                For k = n+1 To cnt

                        ThingsArray(x,y,k-1,ArrayThingType) = ThingsArray(x,y,k,ArrayThingType)

                        ThingsArray(x,y,k-1,ArrayThingHNDL) = ThingsArray(x,y,k,ArrayThingHNDL)

                        t.ThingT = Object.ThingT(ThingsArray(x,y,k,ArrayThingHNDL))

                        t\ArrayNum = k-1

                Next

        EndIf

        ThingsArray(x,y,0,ArrayThingCnt) = ThingsArray(x,y,0,ArrayThingCnt) - 1

End Function



Function UpdateArrayThings()

        Local cnt, N, X, Y

        For X = H\ArrayX-ArrayHeroRadiusX To H\ArrayX+ArrayHeroRadiusX

                For Y = H\ArrayY-ArrayHeroRadiusY To H\ArrayY+ArrayHeroRadiusY

                        If InArrayCheck(X, Y) Then

                                cnt = ThingsArray(X,Y,0,ArrayThingCnt)

                                For N = 1 To cnt

                                        CheckAndUseThing(ThingsArray(X,Y,N,ArrayThingType), ThingsArray(X,Y,N,ArrayThingHNDL))

                                Next

                        EndIf

                Next

        Next

End Function



Function InArrayCheck(x, y)

        If y>=0 And x>=0 And y <= maxArrayY And x <= maxArrayX Then Return True

        Return False

End Function

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

H@NON - некрофил! :crazy:

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

Цитата:

Сообщение от Diablo1909 (Сообщение 215736)

H@NON - некрофил! :crazy:

Разница времени сообщения H@NONа от предыдущего около 10 часов.

ЗЫ: да HolyDel делал библиотечку в 2007, может в чём-то можно упрекнуть код или сам способ реализации..
Но Blitz3D всё ещё требуется великая оптимизация.

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

Видео:

Сектора (ячейки) перед зрением игрока становятся видимыми, остальные остаются скрытыми (ShowEntity | HideEntity).

Квадратами могут быть и комнаты со множеством приборов интерьера, или же леса, поля с деревьями и камнями (на что я и рассчитываю).
Лучшим будет если деревья AddMesh-ить в один меш поля.

Для наглядности размер квадратов 50. Применять можно и большие величины (как DeltaForce)

Пока идёт перебор всех ячеек вокруг в радиусе (затем сортировка). Нужно постараться оптимизировать код для меньшего перебора.

Про момент: игрок идёт назад и попадает в невидимый на тот момент сектор - просто пивот передвинуть на b3d-метры назад, чтобы зад мог подготовиться.

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

Сталкер, в начале ты нормальную тему раскручивал, а сейчас тебя немного не туда понесло )
Дело в том, что блитз автоматически проверяет что входит в обзор камеры и скрывает ненужные элементы.
Сам попробуй - запихни на сцену в одном месте например 100 сфер детализацией 64, выдай фпс и отверни от них камеру ;)

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

Тут скорее оптимизация не рендера, а логики.

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

Цитата:

Сообщение от burovalex (Сообщение 233706)

http://www.youtube.com/watch?v=K0_eh...ilpage#t=66 s
Разница всё же есть. Просто обдумывать блитзу придётся меньше объектов.

То что квадратики в начале видео - это сектора, в них может быть до 100 (и более) мини-объектов.