Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DLL Talk / Quadtree DLL

Author
Message
Atreides
20
Years of Service
User Offline
Joined: 11th Oct 2003
Location: Switzerland (but NOT on a mountain !)
Posted: 24th Jun 2007 14:09
Hmm... Yesterday in the evenings, I made a small DLL to use easily quadtrees with DBP. Since I learnt what is a quadtree some time after I finished it, I called it "node.dll" and not "quadtree.dll" ; I guess I'll have to change that in a next version.

Right now, it does little else than what a simple array would do, but the syntax is more agreable than using dbp arrays. In a next version, I'll add a fast ray casting system and then it'll be more powerful than the array.

Here are the current commands :
NODE INIT%FF%_Z5init2ff%Optimization level
Initialisation of the quadtree. The floats are its width and height.

NODE FINISH%0%_Z6finishv%No parameters
Free the memory.

NODE SET LEVELS%L%_Z9setLevelsi%Levels quantity
Set how many levels in the quadtree you want.

NODE POKE%FF%_Z4pokeff%x coordinate, y coordinate
"Tell" the quadtree that there is an obstacle at these coordinates.

NODE PEEK[%LFF%_Z4peekff%x coordinate, y coordinate
Ask the quadtree if there is an obstacle at these coordinates - or rather in the leaf containing these coordinates.

NODE OPTIMIZE%0%_Z8optimizev%No parameters
Optimize the quadtree by removing useless leaves.

NODE COUNT[%0%_Z5countv%No parameters
Counts how many leaves and branches the quadtree contains.

NODE SIZE[%0%_Z4sizev%No parameters
Tells you how much memory the quadtree uses.

Here is an example of program : there's a 512x512 pixels grid in the screen. The columns and rows of the grid depends on the maximum levels of the quadtree.
On the side of the grid, there is a colored rectangle. If it's red, then the position of the mouse contains an obstacle. If it's green, there's no obstacle.
You can put obstacles by clicking with the mouse, they are represented by white pixels.
When you press return, the quadtree is optimized.


You need to put the DLL in the "compiler\plugins-user" directory. The DLL is attached to this post.


The sleeper must awaken !

Attachments

Login to view attachments
Atreides
20
Years of Service
User Offline
Joined: 11th Oct 2003
Location: Switzerland (but NOT on a mountain !)
Posted: 27th Jun 2007 20:03 Edited at: 27th Jun 2007 20:05
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


The DLL is attached to the message. Any comment or question is welcome.

The sleeper must awaken !

Attachments

Login to view attachments
Olby
20
Years of Service
User Offline
Joined: 21st Aug 2003
Location:
Posted: 3rd Jul 2007 00:45
WOW! This is just wonderful! I actually do not have time to try it right now but it does look like it will suit my current needs. Thanks for making this. I'll test it 100% fully later.

PentiumIV 1.60GHz, 256MB, NVIDIA GeForce FX 5200 128MB, AC'97, WinXP Pro SP2, DirectX 9.0c (Feb2007), DBPro 6.6b
http://www.myspace.com/producerolby
http://www.olby.times.lv
Slooper
21
Years of Service
User Offline
Joined: 13th Feb 2003
Location: Sweden
Posted: 3rd Jul 2007 20:01 Edited at: 3rd Jul 2007 21:32
This is exactley what i need, think i made a post a week or 2 back asking for just this stuff

EDIT, hmm in example 2 when holding space down too see the green visibility range, are you gonna optimize it to increase the speed a bit? Becuse what i need it for is to in real time make a fog of war effect, like the one in nox if you have played that game?


You never fail, only make mistakes.
Atreides
20
Years of Service
User Offline
Joined: 11th Oct 2003
Location: Switzerland (but NOT on a mountain !)
Posted: 5th Jul 2007 13:52
@Olby:
If there are new commands you'd need, feel free to ask. If they're not impossible to make, I'll try to add them.


@Slooper:
I'm not sure I can improve much the speed, I've already optimized almost as much as I could. I looked at the source, there are two things I changed and it should be faster. Not much, I'd say less than 5% but that's still faster :p

I attach the newest version to this message, but there are three changes :
- qtree intersect() is now called qtree fast intersect()
- the new version of qtree intersect() tells you where the ray hits something but it doesn't work correctly yet. In fact, it almost never work, I've already spent quite a long time on this one.
- the functions qtree intersect x() and qtree intersect y() would give you the coordinates where the ray hits something, if qtree intersect() worked. Right now, they give you strange things.

Beside that, you can improve speed for your fog of war in three ways :
- instead of checking each pixel, you can make little squares of 10x10 pixels, it's be 100 times faster
- you don't need to test the whole screen, only the areas which are close to your player
- You don't have to update everything at each loop. You could update 200 or 300 squares everytime.

The sleeper must awaken !

Attachments

Login to view attachments
Olby
20
Years of Service
User Offline
Joined: 21st Aug 2003
Location:
Posted: 5th Jul 2007 20:01
Wow I just saw that it only supports X and Y. Why only 2D? Or I am getting something wrong here?

PentiumIV 1.60GHz, 256MB, NVIDIA GeForce FX 5200 128MB, AC'97, WinXP Pro SP2, DirectX 9.0c (Feb2007), DBPro 6.6b
http://www.myspace.com/producerolby
http://www.olby.times.lv
Atreides
20
Years of Service
User Offline
Joined: 11th Oct 2003
Location: Switzerland (but NOT on a mountain !)
Posted: 5th Jul 2007 21:41 Edited at: 5th Jul 2007 21:43
Err... why "only" 2D ? Right now, I'm working on the function that calculates the coordinates where the ray hits something. This function is recursive, contains 72 return and calls 12 other recursive functions which contain between 6 and 10 return.
I'm maybe doing it the wrong and hard way, but I dislike reading tutorials, I prefere searching the way myself

I don't feel like making the same in 3D now.

The sleeper must awaken !
Manic
21
Years of Service
User Offline
Joined: 27th Aug 2002
Location: Completely off my face...
Posted: 5th Jul 2007 21:41
quad trees are mostly concerned with 3d space (according to wiki)
http://en.wikipedia.org/wiki/Quadtree

you could probably apply the y coord to the z though.

I don't have a sig, live with it.
Atreides
20
Years of Service
User Offline
Joined: 11th Oct 2003
Location: Switzerland (but NOT on a mountain !)
Posted: 5th Jul 2007 21:57
Err.. I think you misread the article : "Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions."

For three dimensional space, one use octrees.
http://en.wikipedia.org/wiki/Octree

If I understand what's not working with my quadtree, I may then start an octree, but... well, as student, I've also other things to do.

Ah, Manic, about your "I don't have a sig, live with it." : I do have two. One under my messages and my assault rifle :p

The sleeper must awaken !
Slooper
21
Years of Service
User Offline
Joined: 13th Feb 2003
Location: Sweden
Posted: 7th Jul 2007 09:00 Edited at: 7th Jul 2007 09:02
Atreides Why i was asking about the speed was becuse i need it to do an certain task but mabey this the is wrong aproach. Look at my thread and the youtube link that i added there and mabey you have the answer to that. Becuse in the game Nox the effect are very fast calculated and rendered.

http://forum.thegamecreators.com/?m=forum_view&t=108291&b=1

Cheers


You never fail, only make mistakes.
Manic
21
Years of Service
User Offline
Joined: 27th Aug 2002
Location: Completely off my face...
Posted: 7th Jul 2007 17:03
oops, what a mistype!

yes i meant 2d


Quote: "Ah, Manic, about your "I don't have a sig, live with it." : I do have two. One under my messages and my assault rifle :p"


eh?

I don't have a sig, live with it.
Olby
20
Years of Service
User Offline
Joined: 21st Aug 2003
Location:
Posted: 7th Jul 2007 17:34
Octrees would rule this game then.

PentiumIV 1.60GHz, 256MB, NVIDIA GeForce FX 5200 128MB, AC'97, WinXP Pro SP2, DirectX 9.0c (Feb2007), DBPro 6.6b
http://www.myspace.com/producerolby
http://www.olby.times.lv
Atreides
20
Years of Service
User Offline
Joined: 11th Oct 2003
Location: Switzerland (but NOT on a mountain !)
Posted: 15th Jul 2007 13:32
Sorry for answering late, I had a game programming challenge. I spent 9 days making a little game with a robot one can control with three keys only.

@Slooper:
I think I see another way which may be faster, but.. still, I'm not sure it's possible to calculate every pixel in real time in a basic language...
In my quadtree system, each square (or rectangle, but lets talk about squares, it's shorter), each square is made of four lines. A ray, coming from any direction, can hit only one or two of these lines while entering the square, never three. If you don't see why, try to make a drawing

In my intersection system, I look if there's a collision between the lines that can be hit. If there is a collision (and of course if the square contains an obstacle), I do the same for the chldren squares. And I do it again and again... Until I checked the leaves.

You could do the same, but differently. If you don't make a grid with these lines, you could, for example, draw the walls of a house. If there's a window in the wall, then you'd need two lines. It may be faster if there aren't many obstacles, but ... I think it may still be too slow, because you'd have then to draw the screen pixel by pixel.

I do think the best way would be to make n*n pixels tiles. It'd be n^2 times faster for the line of sight and also faster to draw the map. Keep in mind that Nox was made by professionals guys, that they may have spent monthes working on that system and that they did not use a basic language


@Manic:
It was just a little... err... "word play" with "sig". Sig is also a brand of rifles, the swiss assault rifle is the sig 550 and like every swiss soldier-citizen, I've to keep mine at home, hidden somewhere in my room. That's why I've two sig : my signature and my sig 550


@Olby:
Yep, but they'd be slower too because one would have to check the intersections on three axes. Beside that, DBP has the command intersect object() (if I remember correctly the name) which is pretty fast and accurate

The sleeper must awaken !

Login to post a reply

Server time is: 2024-03-29 15:33:50
Your offset time is: 2024-03-29 15:33:50