Наш телеграм (тут все твои друзья)

Кэшированная версия

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

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

Вернуться   forum.boolean.name > Программирование игр для компьютеров > Blitz3D
Перезагрузить страницу quadrotree or octree

Ответ
 
Опции темы
Старый 26.12.2011, 17:14   #1
polopok
ПроЭктировщик
 
Регистрация: 17.07.2009
Сообщений: 182
Написано 51 полезных сообщений
(для 71 пользователей)
Вопрос quadrotree or octree
прошу помощи..
1 поделить рекурсивно область ,порядка 5 и более вложений(создать "дерево")
2 все области изначально пусты(null)
3 проверить наличие объекта в области
4 вывести путь к объекту используя "дерево"
как-то так ...
вот код примерный :
Global mx,my
Type box Field x,y,xf,yf,n,name$ End Type
Type ent Field x,y,n End Type 

Function enty(x,y,n)
	e.ent = New ent 
	e\x=x
	e\y=y
	e\n=n
End Function
Function boxing(name$,x,y,xf,yf,n)
	b.box = New box
	b\x=x
	b\y=y
	b\xf=xf
	b\yf=yf
	b\n=n
	b\name$=name$
End Function 
enty(240,240,0)
enty(340,200,1)
enty(340,340,2)
boxing("A",200,100,100,100,0)
boxing("A",300,100,100,100,0)
boxing("A",300,200,100,100,0)
boxing("A",200,200,100,100,0)

Graphics 800,600,32,2
i=3
tx=240 : ty=240
SetBuffer BackBuffer()
While Not KeyDown(1)
mx=MouseX(): my=MouseY()
If i>=3 Then i=3
Cls
Rect 200,100,200,200,0
Plot mx,my
Oval tx-1,ty-1,3,3,1

For e.ent = Each ent
	For b.box = Each box
	Rect b\x,b\y,b\xf,b\yf,0
	Text b\x+(b\xf/2),b\y+(b\yf/2),b\name$
If i>0 Then
	If PointInRect(e\x,e\y,b\x,b\y,b\xf,b\yf) Then
		i=i-1
		boxing("B",b\x,b\y,b\xf/2,b\yf/2,0)
		boxing("B",b\x+(b\xf/2),b\y,b\xf/2,b\yf/2,0)
		boxing("B",b\x+(b\xf/2),b\y+(b\yf/2),b\xf/2,b\yf/2,0)
		boxing("B",b\x,b\y+(b\yf/2),b\xf/2,b\yf/2,0)
 		Text 20,20,"IN rect"
	EndIf 
End If 
	Next
Next

Text 30,30,i
Flip
Wend
Delete Each box
End

Function PointInRect(iPointX,iPointY,iXPos1,iYPos1,iXPos2,iYPos2)
    iXPos2=iXPos2 + iXPos1 : iYPos2=iYPos2 + iYPos1
	Return ((((iPointX-iXPos1) Xor (iPointX-iXPos2)) And ((iPointY-iYPos1) Xor (iPointY-iYPos2))) And $80000000)
End Function
(Offline)
 
 Ответить с цитированием
Сообщение было полезно следующим пользователям:
LLI.T.A.L.K.E.R. (27.12.2011)
Старый 26.12.2011, 17:30   #2
polopok
ПроЭктировщик
 
Регистрация: 17.07.2009
Сообщений: 182
Написано 51 полезных сообщений
(для 71 пользователей)
Ответ: quadrotree or octree
принцип понятен ,но никак не могу понять как выстаивать само "дерево" с ссылками на элементы уровнем ниже.

Основной идеей Quadtree является последовательное разделение участков пространства на четыре части. Т.е. берем квадрат, делим его на четыре квадрата поменьше, каждый получившийся — еще на четыре, и так далее. Получается квадратное дерево, потому так и называется.

Основным объектом нашего Quadtree является как раз такой квадрат, или узел дерева. Он содержит список тех объектов, которые находятся непосредственно в нем, а также ссылки на четыре дочерних квадрата поменьше.
(Offline)
 
 Ответить с цитированием
Старый 27.12.2011, 08:39   #3
LLI.T.A.L.K.E.R.
Мастер
 
Аватар для LLI.T.A.L.K.E.R.
 
Регистрация: 24.06.2009
Адрес: Набережные Челны
Сообщений: 930
Написано 292 полезных сообщений
(для 504 пользователей)
Ответ: quadrotree or octree
Сообщение от polopok Посмотреть сообщение
принцип понятен ,но никак не могу понять как выстаивать само "дерево" с ссылками на элементы уровнем ниже.
Ну такое:
добавить записи к боксам
Function boxing(name$,x,y,xf,yf,n,uptree,downtrees)
	b.box = New box
	b\x=x
	b\y=y
	b\xf=xf
	b\yf=yf
	b\n=n
	b\name$=name$
        b\uptree=uptree
        b\downtrees=downtrees  (массив из 4-х)
End Function
И вносить значения веток в:
boxing("B",b\x,b\y,b\xf/2,b\yf/2,0,Handle(b),??downtrees??)
Когда создаём новую ветку - вносим верхнюю.
Это в после
For e.ent = Each ent
	For b.box = Each box
С downtrees косяк, там код доделывать.
Когда создаётся нижняя ветка - (другой может функцией) вносить нижнюю.

1 поделить рекурсивно область ,порядка 5 и более вложений(создать "дерево")
Ну и у тебя это работает. Просто увеличь i - там хоть 10
(Offline)
 
 Ответить с цитированием
Старый 27.12.2011, 09:04   #4
polopok
ПроЭктировщик
 
Регистрация: 17.07.2009
Сообщений: 182
Написано 51 полезных сообщений
(для 71 пользователей)
Ответ: quadrotree or octree
да работать то работает ,но в самом начале нужно рекурсивно создать пустое "дерево", а не по проверке пересечения.
сейчас пытаюсь завязать на связанных списках.
вот разбираю пример http://blitzetc.blitzmax.ru/index.php/%D0%94%D1%80%D0%B5%D0%B2%D0%BE%D0%B2%D0%B8%D0%B4%D 0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1 %82%D1%83%D1%80%D0%B0
(Offline)
 
 Ответить с цитированием
Сообщение было полезно следующим пользователям:
LLI.T.A.L.K.E.R. (27.12.2011)
Старый 27.12.2011, 11:36   #5
polopok
ПроЭктировщик
 
Регистрация: 17.07.2009
Сообщений: 182
Написано 51 полезных сообщений
(для 71 пользователей)
Ответ: quadrotree or octree
ну вот нарыл ...
буду рабираться
http://blitzbasic.com/Community/posts.php?topic=67362
http://www.mikechambers.com/blog/201...mplementation/
Последний раз редактировалось polopok, 28.12.2011 в 09:55.
(Offline)
 
 Ответить с цитированием
Сообщение было полезно следующим пользователям:
LLI.T.A.L.K.E.R. (31.12.2011)
Старый 30.12.2011, 18:44   #6
polopok
ПроЭктировщик
 
Регистрация: 17.07.2009
Сообщений: 182
Написано 51 полезных сообщений
(для 71 пользователей)
Ответ: quadrotree or octree
вот продолжаю разбирать пример ...



; кликайте мышью в смежных квадрантах 
;
;
Global p1x,p1y
Global p2x,p2y
Global id,level ,xx#,yy#
; константы детей 
Const CHILD00 = 0
Const CHILD01 = 1
Const CHILD11 = 2
Const CHILD10 = 3

; QUADTREE
Type QUADTREE
Field Child.QUADTREE[3] ;четыре потомка
Field xmin,ymin ; начальные координаты квадранта
Field xmax,ymax ; оконечные координаты квадранта 
Field id ,lev 
End Type


; ============= создаём квадро-дерево =================
Function Quadtree.QUADTREE(xmin,ymin,xmax,ymax,depth)
this.QUADTREE = New QUADTREE
this\xmin = xmin
this\xmax = xmax
this\ymin = ymin
this\ymax = ymax
id = id + 1
this\id = id
this\lev = 0

If (depth > 0)
; деление квадранта на 4-ре квадранта
xmoy = (xmin+xmax) / 2
ymoy = (ymin+ymax) / 2
depth = depth - 1
this\Child[CHILD00] = Quadtree(xmin,ymin,xmoy,ymoy,depth) 
this\Child[CHILD01] = Quadtree(xmin,ymoy,xmoy,ymax,depth)
this\Child[CHILD11] = Quadtree(xmoy,ymoy,xmax,ymax,depth) 
this\Child[CHILD10] = Quadtree(xmoy,ymin,xmax,ymoy,depth) 
EndIf
Return this
End Function

; ====================   Рендер квадро-дерева   =====================
Function RenderQuadtree(this.QUADTREE,depth)


If RectsOverlap (xx#,yy#,1,1,this\xmin,this\ymin,this\xmax-this\xmin,this\ymax-this\ymin)

If (depth > 1)

Color 188,188,188
Line (this\xmin+this\xmax)/2,this\ymin,(this\xmin+this\xmax)/2,this\ymax
Line this\xmin,(this\ymin+this\ymax)/2,this\xmax,(this\ymin+this\ymax)/2

depth = depth - 1
RenderQuadtree(this\Child[CHILD00],depth)
RenderQuadtree(this\Child[CHILD01],depth)
RenderQuadtree(this\Child[CHILD11],depth)
RenderQuadtree(this\Child[CHILD10],depth)

If this\Child[CHILD00]\lev = 1  And  this\Child[CHILD01]\lev = 1  And this\Child[CHILD11]\lev = 1 And  this\Child[CHILD10]\lev = 1  Then  
this\lev =  1
EndIf
Else

If MouseHit(1) Then  this\lev = 1
If  this\lev = 1 Then Color 255,0,0 : fill = True Else Color 66,66,66 : fill = False 
Rect this\xmin+1,this\ymin+1,this\xmax-this\xmin-1,this\ymax-this\ymin-1,fill 
Color 255,255,255
Text this\xmin+2,this\ymin+2, this\id +".id  "+depth

EndIf
EndIf

If  this\lev = 1 Then Color 255,0,0 : fill = True Else Color 66,66,66 : fill = False 
Rect this\xmin+1,this\ymin+1,this\xmax-this\xmin-1,this\ymax-this\ymin-1,fill 
Color 255,255,255
Text this\xmin+2,this\ymin+12, this\lev
End Function


;==============================================================================================
; Сама Программа :
;==============================================================================================

AppTitle "квадро-дерево "
Graphics 512,512,0,2
SetBuffer BackBuffer()
ClsColor 122,122,122

QuadDepth = 5;число вложений (глубина ) : Level 's
QuadSize = 512 ; размеры квадранта 

; создание основного квадранта
root.QUADTREE = Quadtree(0,0,QuadSize,QuadSize,QuadDepth)

While Not KeyHit(1)
Cls
xx# = MouseX() 
yy# = MouseY() 

Select True 
Case KeyDown(200) ; Up
Case KeyDown(208) ; Down
Case KeyDown(203) ; Left
Case KeyDown(205) ; Right
End Select 

; Рендер квадро-дерева 
Color 255,255,255
Rect root\xmin,root\ymin,root\xmax,root\ymax,0

RenderQuadtree(root,QuadDepth)

Flip
Wend
Delete Each QUADTREE 
End
(Offline)
 
 Ответить с цитированием
Сообщение было полезно следующим пользователям:
LLI.T.A.L.K.E.R. (31.12.2011)
Старый 30.12.2011, 19:56   #7
polopok
ПроЭктировщик
 
Регистрация: 17.07.2009
Сообщений: 182
Написано 51 полезных сообщений
(для 71 пользователей)
Ответ: quadrotree or octree
вместо кружков-квадратов можно загрузить своё изображение

; ведите мышью с зажатой левой кнопкой ,в смежных квадрантах 
;и вы увидите их объединение 
;полезно для редактора карт 
Global p1x,p1y
Global p2x,p2y
Global id,level ,xx#,yy#
; константы детей 
Const CHILD00 = 0
Const CHILD01 = 1
Const CHILD11 = 2
Const CHILD10 = 3
;

; QUADTREE
Type QUADTREE
Field Child.QUADTREE[3] ;четыре потомка
Field xmin,ymin ; начальные координаты квадранта
Field xmax,ymax ; оконечные координаты квадранта 
Field id ,lev 
End Type


; ============= создаём квадро-дерево =================
Function Quadtree.QUADTREE(xmin,ymin,xmax,ymax,depth)
this.QUADTREE = New QUADTREE
this\xmin = xmin
this\xmax = xmax
this\ymin = ymin
this\ymax = ymax
id = id + 1
this\id = id
this\lev = 0

If (depth > 0)
; деление квадранта на 4-ре квадранта
xmoy = (xmin+xmax) / 2
ymoy = (ymin+ymax) / 2
depth = depth - 1
this\Child[CHILD00] = Quadtree(xmin,ymin,xmoy,ymoy,depth) 
this\Child[CHILD01] = Quadtree(xmin,ymoy,xmoy,ymax,depth)
this\Child[CHILD11] = Quadtree(xmoy,ymoy,xmax,ymax,depth) 
this\Child[CHILD10] = Quadtree(xmoy,ymin,xmax,ymoy,depth) 
EndIf
Return this
End Function

; ====================   Рендер квадро-дерева   =====================
Function RenderQuadtree(this.QUADTREE,depth)


If RectsOverlap (xx#,yy#,1,1,this\xmin,this\ymin,this\xmax-this\xmin,this\ymax-this\ymin)

If (depth > 1)

Color 188,188,188
Line (this\xmin+this\xmax)/2,this\ymin,(this\xmin+this\xmax)/2,this\ymax
Line this\xmin,(this\ymin+this\ymax)/2,this\xmax,(this\ymin+this\ymax)/2

depth = depth - 1
RenderQuadtree(this\Child[CHILD00],depth)
RenderQuadtree(this\Child[CHILD01],depth)
RenderQuadtree(this\Child[CHILD11],depth)
RenderQuadtree(this\Child[CHILD10],depth)

If this\Child[CHILD00]\lev = 1  And  this\Child[CHILD01]\lev = 1  And this\Child[CHILD11]\lev = 1 And  this\Child[CHILD10]\lev = 1  Then  this\lev =  2
If this\Child[CHILD00]\lev = 2  And  this\Child[CHILD01]\lev = 2  And this\Child[CHILD11]\lev = 2 And  this\Child[CHILD10]\lev = 2  Then  this\lev =  3
If this\lev =  2 Then 
this\Child[CHILD00]\lev = 0
this\Child[CHILD01]\lev = 0
this\Child[CHILD11]\lev = 0
this\Child[CHILD10]\lev = 0
EndIf 
If this\lev =  3 Then 
this\Child[CHILD00]\lev = 0
this\Child[CHILD01]\lev = 0
this\Child[CHILD11]\lev = 0
this\Child[CHILD10]\lev = 0
this\lev = 3
EndIf 
Else

If MouseDown(1) Then  this\lev = 1
If  this\lev = 1 Then Color 255,0,0 : fill = True Else Color 66,66,66 : fill = False 
Rect this\xmin+1,this\ymin+1,this\xmax-this\xmin-1,this\ymax-this\ymin-1,fill 
Color 255,255,255
Text this\xmin+2,this\ymin+2, this\id +".id  "
Text this\xmin+2,this\ymin+12, this\lev
EndIf
EndIf

If  this\lev = 1 Then Color 255,0,0 : fill = True Else Color 66,66,66 : fill = False 
Rect this\xmin+1,this\ymin+1,this\xmax-this\xmin-1,this\ymax-this\ymin-1,fill 
Color 255,255,255
Text this\xmin+2,this\ymin+12, this\lev
End Function


;==============================================================================================
; Сама Программа :
;==============================================================================================

AppTitle "квадро-дерево "
Graphics 512,512,0,2
;
gor2=CreateImage(64,64) 
gor8=CreateImage(128,128) 
gor1=CreateImage(32,32) 
SetBuffer ImageBuffer(gor2)
Rect 10,10,34,34,1
Oval 34/2,34/2,32,32,0

SetBuffer ImageBuffer(gor1)
Rect 10,10,14,14,0
Oval 30/2,30/2,8,8,1
SetBuffer ImageBuffer(gor8)
Rect 0,0,124,124,0
Rect 20,20,82,82,1
;
SetBuffer BackBuffer()
ClsColor 122,122,122

QuadDepth = 5;число вложений (глубина ) : Level 's
QuadSize = 512 ; размеры квадранта 

; создание основного квадранта
root.QUADTREE = Quadtree(0,0,QuadSize,QuadSize,QuadDepth)

While Not KeyHit(1)
Cls
xx# = MouseX() 
yy# = MouseY() 
;DrawImage  gor1,200,200
Select True 
Case KeyDown(200) ; Up
Case KeyDown(208) ; Down
Case KeyDown(203) ; Left
Case KeyDown(205) ; Right
End Select 

; Рендер квадро-дерева 
Color 255,255,255
Rect root\xmin,root\ymin,root\xmax,root\ymax,0
For wroot.QUADTREE = Each QUADTREE 
	If wroot\lev = 1 Then 
	Color 255,0,0 
	DrawImage  gor1 ,wroot\xmin,wroot\ymin
	;Rect wroot\xmin,wroot\ymin,wroot\xmax-wroot\xmin,wroot\ymax-wroot\ymin,1
	
	
	ElseIf wroot\lev = 2 Then 
	Color 255,0,0 
	DrawImage  gor2 ,wroot\xmin,wroot\ymin
	;Rect wroot\xmin,wroot\ymin,wroot\xmax-wroot\xmin,wroot\ymax-wroot\ymin,1
	
	
	ElseIf wroot\lev = 3 Then 
	Color 255,0,0 
	DrawImage  gor8 ,wroot\xmin,wroot\ymin
	;Rect wroot\xmin,wroot\ymin,wroot\xmax-wroot\xmin,wroot\ymax-wroot\ymin,1
	
	
	EndIf 
Next 
RenderQuadtree(root,QuadDepth)

Flip
Wend
Delete Each QUADTREE 
End
(Offline)
 
 Ответить с цитированием
Сообщение было полезно следующим пользователям:
LLI.T.A.L.K.E.R. (31.12.2011)
Старый 30.12.2011, 20:04   #8
polopok
ПроЭктировщик
 
Регистрация: 17.07.2009
Сообщений: 182
Написано 51 полезных сообщений
(для 71 пользователей)
Ответ: quadrotree or octree
пункт 1,2,3 вроде выполнен а четвёртый хм...
(Offline)
 
 Ответить с цитированием
Старый 24.01.2012, 20:47   #9
LLI.T.A.L.K.E.R.
Мастер
 
Аватар для LLI.T.A.L.K.E.R.
 
Регистрация: 24.06.2009
Адрес: Набережные Челны
Сообщений: 930
Написано 292 полезных сообщений
(для 504 пользователей)
Ответ: quadrotree or octree
Нашёл рабочий quadtree 2D-пример:
http://bond357.free.fr/main/forums/viewtopic.php?id=10
(Offline)
 
 Ответить с цитированием
Старый 13.02.2012, 17:45   #10
Черный крыс
 
Сообщений: n/a
Ответ: quadrotree or octree
Вот только зачем qtree для 2Д ? имхо bsp-2d эффективнее.
 
 Ответить с цитированием
Ответ

« Предыдущая тема | Следующая тема »

Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +4, время: 09:30.


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

Обратная связь - Форум портала www.boolean.name - Вверх