Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   www.boolean.name > Программирование игр для компьютеров > Blitz3D > Библиотеки

Библиотеки Сторонние библиотеки для Blitz

Ответ
 
Опции темы
Старый 23.09.2007, 22:05   #1
HolyDel
 
Регистрация: 25.09.2006
Сообщений: 6,030
Написано 1,469 полезных сообщений
(для 2,690 пользователей)
Секционная разбивка

Здравствуйте.
Речь зайдет о секционной разбивке поля. Что это такое?
Чаще всего нужно для проверки коллизий, и подобных задач, когда множество объектов необходимо проверить с учетом расстояния и подобных задач.
Как это работает:
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 - остановить их перемещения.
большие зеленые клетки - ето те ячейки , которые обрабатываются.
(Offline)
 
Ответить с цитированием
Эти 3 пользователя(ей) сказали Спасибо HolyDel за это полезное сообщение:
Egor Rezenov (10.02.2011), LLI.T.A.L.K.E.R. (10.02.2011), RBK (10.02.2011)
Старый 24.09.2007, 05:23   #2
Damp
Знающий
 
Регистрация: 12.07.2007
Сообщений: 297
Написано 50 полезных сообщений
(для 133 пользователей)
Re: Секционная разбивка

Как раз подобное сейчас пишу, для оптимизации рендера и физики.
Только планирую что будут такие сферы которые надо расставить на карте и все что в них попадет будет оптимизировано.
Заценю твой пример! Вообще это правильный путь, иначе большой уровень не создать...
(Offline)
 
Ответить с цитированием
Старый 24.09.2007, 08:19   #3
SBJoker
Злобный Админ
 
Аватар для SBJoker
 
Регистрация: 04.09.2005
Сообщений: 5,921
Написано 3,411 полезных сообщений
(для 9,319 пользователей)
Re: Секционная разбивка

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

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

Вот например таблицы синусов/косинусов в блитзмаксе нерулят ибо реализация доставания нужного значения из таблицы тормазит больше прямого расчёта значения.
__________________
(Offline)
 
Ответить с цитированием
Старый 24.09.2007, 08:25   #4
dimanche13
Мастер
 
Регистрация: 19.03.2007
Сообщений: 1,039
Написано 153 полезных сообщений
(для 252 пользователей)
Re: Секционная разбивка

SBJoker , не понял то есть не имеет смысла сохдавать sin[360] & cos[360]?
А по теме.. это один из самых древних способов оптимизации, странно что до HolyDel-а никто такой либы не делал.
(Offline)
 
Ответить с цитированием
Старый 24.09.2007, 09:32   #5
Damp
Знающий
 
Регистрация: 12.07.2007
Сообщений: 297
Написано 50 полезных сообщений
(для 133 пользователей)
Re: Секционная разбивка

Делали конечно, но тут нестандартный подход...
Вечером буду разбираться глубже.
Полный перебор - это не страшно. Обычно делается за несколько циклов, ведь камера не может мгновенно перелететь из зоны А в зону В, поэтому перебор можно растянуть по циклам, так что он вообще не займет времени.
(Offline)
 
Ответить с цитированием
Старый 24.09.2007, 10:16   #6
IGR
Blitz's Shame !!
 
Регистрация: 31.03.2007
Сообщений: 3,639
Написано 832 полезных сообщений
(для 2,012 пользователей)
Re: Секционная разбивка

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

странно что до HolyDel-а никто такой либы не делал
to dimanche13: я давно пытался , но так и незакончил !!
(Offline)
 
Ответить с цитированием
Старый 24.09.2007, 17:09   #7
HolyDel
 
Регистрация: 25.09.2006
Сообщений: 6,030
Написано 1,469 полезных сообщений
(для 2,690 пользователей)
Re: Секционная разбивка

полный перебор только один раз - чтобы занести объекты в ячейки сетки.
Далее, если нам надо проверить 10 каких то объектов (а у нас их например 10000), то нам уже ненаждо прогонять 10*10000 раз. а достаточно проверить только те, которые находятся в ближайших ячейках. (а представь, если надо 10000 * 10000 проверить?), вот тут уже начинается чудовищная оптимизация.
(Offline)
 
Ответить с цитированием
Старый 10.02.2011, 11:40   #8
LLI.T.A.L.K.E.R.
Мастер
 
Аватар для LLI.T.A.L.K.E.R.
 
Регистрация: 24.06.2009
Адрес: Набережные Челны
Сообщений: 930
Написано 292 полезных сообщений
(для 504 пользователей)
Хорошо Ответ: Секционная разбивка

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

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

Спасибо HolyDel!

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

Некрофил? ==> Важная тема забыта в 2007

В примере рисуемая сетка немного смещена.


Перебор всё же будет по всем (+100700) объектам типов.
Но так можно упростить "физику", используя её только для нужных объектов.
А если эти объекты статичны, то вроде всё будет намного легче?
(Offline)
 
Ответить с цитированием
Старый 10.02.2011, 11:53   #9
Mr_F_
Терабайт исходников
 
Аватар для Mr_F_
 
Регистрация: 13.09.2008
Сообщений: 3,907
Написано 2,157 полезных сообщений
(для 5,843 пользователей)
Ответ: Секционная разбивка

лучше юзать не просто сетку, а квадтри/BVH
(Offline)
 
Ответить с цитированием
Старый 10.02.2011, 13:18   #10
LLI.T.A.L.K.E.R.
Мастер
 
Аватар для LLI.T.A.L.K.E.R.
 
Регистрация: 24.06.2009
Адрес: Набережные Челны
Сообщений: 930
Написано 292 полезных сообщений
(для 504 пользователей)
Ответ: Секционная разбивка

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

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

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

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

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

Движение - клавишами стрелок или мышью.
Квадратики окрашены:
вверх зеленее
вправо краснее
Вложения
Тип файла: rar Cell_LOD.rar (488.0 Кб, 168 просмотров)
(Offline)
 
Ответить с цитированием
Старый 10.02.2011, 14:13   #11
RBK
Знающий
 
Аватар для RBK
 
Регистрация: 05.12.2010
Адрес: Луганск
Сообщений: 252
Написано 112 полезных сообщений
(для 166 пользователей)
Ответ: Секционная разбивка

HolyDel не вводи людей в заблуждение, скажи прямо: Это двухмерный массив с произвольным числом элементов в ячейке.
Секционную разбивку поля эта dll-ка не делает, а только хранит информацию о ней. Хорошо подойдет для статичных объектов (движущиеся все равно надо пересчитывать).
(Offline)
 
Ответить с цитированием
Старый 28.12.2011, 21:10   #12
LLI.T.A.L.K.E.R.
Мастер
 
Аватар для LLI.T.A.L.K.E.R.
 
Регистрация: 24.06.2009
Адрес: Набережные Челны
Сообщений: 930
Написано 292 полезных сообщений
(для 504 пользователей)
Ответ: Секционная разбивка


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

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

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

Пишу на Delphi (первый опыт dll).
В планах:
попадание ячейки в угол обзора (иначе скрывать). Пока хотя бы "входит ли точка (центр ячейки) в треугольник (угол обзора)"
(Offline)
 
Ответить с цитированием
Старый 28.12.2011, 23:35   #13
Crayzi
ПроЭктировщик
 
Регистрация: 25.06.2007
Сообщений: 194
Написано 21 полезных сообщений
(для 25 пользователей)
Ответ: Секционная разбивка

Ну я хз конешно, но у меня при перемещении персонажей они автоматом вносятся в новые ячейки, создал массив , создал тип в который будут писатся все игроки какие в ячейках и т. д., создал количество объектов в типе = количеству ячеек массива, создал ф-цию перевода координат в номера ячеек, создал ф-цию перебора всех персонажей в пределах 1 ячейки вокруг... и т. д. Там вытоге ниче сложного...
Как в этой либе прально узнать сколько рыл находится в конкретной ячейке?
(Offline)
 
Ответить с цитированием
Старый 28.12.2011, 23:57   #14
HolyDel
 
Регистрация: 25.09.2006
Сообщений: 6,030
Написано 1,469 полезных сообщений
(для 2,690 пользователей)
Ответ: Секционная разбивка

Как в этой либе прально узнать сколько рыл находится в конкретной ячейке?
tt=PrepareCell(i,j) // готовим ячейку и заодно узнаем скока всего объектов в ней
да это самый тупой метод. да, посути это просто двухмерный массив. раньше это казалось крутым
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
LLI.T.A.L.K.E.R. (29.12.2011)
Старый 29.12.2011, 00:00   #15
Crayzi
ПроЭктировщик
 
Регистрация: 25.06.2007
Сообщений: 194
Написано 21 полезных сообщений
(для 25 пользователей)
Ответ: Секционная разбивка

Сообщение от HolyDel Посмотреть сообщение
tt=PrepareCell(i,j// готовим ячейку и заодно узнаем скока всего объектов в ней 
да это самый тупой метод. да, посути это просто двухмерный массив. раньше это казалось крутым

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


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Дальность прорисовки или разбивка на блоки Ekzi 3D-программирование 10 08.11.2007 12:34


Часовой пояс GMT +1, время: 03:45.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com