Here is a new version
This new version allows you to "throw" a ray fast and accurately. In the following picture, I sent rays from the center of the white circle to each pixels of the map. If the ray was not cut by an obstacle, I colored the pixel in green.
A part of the code also do the same thing without coloring the pixel, in order to count how much time is needed by the qtree intersect function. There are 512x512 = 262144 pixels and it was done in 1.386 seconds, that makes 0.0053 millisecond for each pixel - and I don't have a very powerful computer (laptop 2 years old, 1.7GHz).
In this new version, I also corrected a little bug which made jokes when the quadtree did not cover a square area. Now, rectangles are well supported. Beside that, I renamed the commands by replacing node by qtree. Here is the commands list :
[B]QTREE INIT[/B] Width, height
Initialize the quadtree system. The parameters are the width and the height of the area covered by the quadtree.
[B]QTREE FINISH[/B] No parameters
This command frees the memory used by the quadtree. You must use it when you do not need the quadtree anymore or before using the command qtree init [U]if and only if[/U] you have already used it before.
[B]QTREE SET LEVELS[/B] Levels quantity
Tells the level of details you want. For more details, try to change the value of LVL in the code below.
[B]QTREE POKE[/B] x coordinate, y coordinate
Tells the quadtree that there is an obstacle at these coordinates.
[B]QTREE PEEK[/B] x coordinate, y coordinate
Ask the quadtree if there is an obstacle near these coordinates.
[B]QTREE OPTIMIZE[/B] No parameters
A small optimization that removes useless leaves.
[B]QTREE COUNT[/B] No parameters
Tells how many leaves and branches the tree contains.
[B]QTREE SIZE[/B] No parameters
Tells how much memory the quadtree uses.
[B]QTREE INTERSECT[/B] StartX, startY, dx, dy
Throws a ray between the point (startX, startY) and (startX+dx, startY+dy) and tells you if there is an obstacle (returns 1) or not (returns 0).
Here's the source of the program I used to make that screenshot. The commands are easy :
- arrow keys to move the circle
- mouse to change the place aimed by the ray
- spacekey (keep pressed) to throw rays to all pixels and to color them
- returnkey to count the time needed to throw rays to all pixels
Since I'm lazy and nobody seems to be interrested in this DLL, I didn't spend time to translate the comments in english. Have fun - and a good dictionary
sync on
sync rate 30
sync sleep 1
sync
`niveau de précision du quadtree. Ici, c'est 6, autrement dit, la grille la plus fine
`contiendra 2^6 x 2^6 cellules, c'est-à-dire 64x64=4096 cellules.
#constant LVL 6
`initialisation du quadtree. On veut que sa surface soit de 512x512 pixels.
qtree init 512, 512
`on règle le niveau de précision du quadtree
qtree set levels LVL
`affichage d'une "carte" en fonction du niveau de détails du quadtree
ink rgb(128,128,128),0
for x=0 to 2^LVL-1
for y=0 to 2^LVL-1
`chaque case est aléatoirement pleine ou vide
if rnd(3*LVL)=1
`si elle est pleine, on colorie en gris
box (512/2^LVL)*x, (512/2^LVL)*y, (512/2^LVL)*(x+1), (512/2^LVL)*(y+1)
`et on indique au quadtree qu'il y a un obstacle
qtree poke ((512/2^LVL)*x)+2,((512/2^LVL)*y)+2
else
endif
next y
next x
`un petit coup d'optimisation...
qtree optimize
`on récupère l'image, comme ça on n'aura pas à tout redessiner à chaque boucle
get image 1, 0, 0, 511, 511, 0
`initialisation d'un "joueur" qui sera en fait un simple cercle
`tirant un rayon.
posx=256
posy=256
do
cls
paste image 1, 1, 1
`ceci est la grande modification par rapport à la version précédente. On peut maintenant
`tirer des rayons dans une direction donnée. La fonction qtree intersect() dit si le
`rayon rencontre un obstacle. Je travaille à un système permettant de récupérer les
`coordonnées de la collision.
`syntaxe : res=qtree intersect(x, y, dx, dy), avec
`res : résultat
`x : coordonnée de départ x
`y : coordonnée de départ y
`dx : longueur du rayon sur l'axe x
`dy : longueur du rayon sur l'axe y
`dans cet exemple, on va tracer des rayons entre chaque pixel de l'image et les coordonnées
`posx, posy. Il y a au total 262144 pixels, ça fait donc 262144 rayons.
`si le rayon ne rencontre aucun obstacle, le pixel est coloré en vert.
if spacekey()=1
lock pixels
for x=0 to 511
for y=0 to 511
if qtree intersect(posx, posy, x-posx, y-posy)=0
dot x,y,rgb(0,255,0)
endif
next y
next x
unlock pixels
endif
`même principe que précédemment, mais dans le but de chronométrer le temps de calcul. Pour
`n'avoir que les lancers de rayons, j'ai retiré l'affichage.
if returnkey()=1
chrono=timer()
for x=0 to 511
for y=0 to 511
a=qtree intersect(posx, posy, x-posx, y-posy)=0
next y
next x
chrono = timer()-chrono
endif
`affichage du temps de calcul
set cursor 520, 0
print "Chrono> ",chrono
`moyenne de temps par pixel
set cursor 520, 25
print "Average time per node intersect(): "
set cursor 520, 50
print chrono / 262144.0, " milliseconds."
`affichage d'informations supplémentaires.
set cursor 520, 75
print "The quadtree uses ", int(qtree size()/1024.), "Kb for ", qtree count()
set cursor 520, 100
print " nodes."
`déplacement et affichage du "joueur"
if leftkey()=1 then dec posx,3
if rightkey()=1 then inc posx,3
if downkey()=1 then inc posy,3
if upkey()=1 then dec posy,3
circle posx, posy, 5
`juste pour le fun, affichage d'une ligne entre le joueur et la souris. Si la ligne est
`coupée, on l'affiche en rouge, sinon en blanc.
if (qtree intersect(posx, posy, mousex()-posx, mousey()-posy)=0)
ink rgb(255,255,255),0
else
ink rgb(255,0,0),0
endif
line posx, posy, mousex(), mousey()
`et ici, on vérifie l'état du pixel sous la souris. S'il contient un obstacle, on affiche la
`boîte se trouvant sous l'image en rouge, sinon en gros.
if qtree peek(mousex(),mousey())=1
ink rgb(255,0,0),0
else
ink rgb(128,128,128),0
endif
box 0, 512, 512, 564
sync
loop
The DLL is attached to the message. Any comment or question is welcome.
The sleeper must awaken !
