GetPixel, HDC, and heartattacks

You then break up the screen into 9 equal divisions. The grayed out parts show regions that there can not possibly be any Dudes that will collide, or are in fear of crossing a boundary into the same region as the Dude being checked.

As you can see, it's not the gain that the Quadtree had at first...

After that, you break up the regoin that the Dude being checked is in into 9 more squares. Based on his location, in the picture below, you know that the newly grayed out squared (3 of them) can not be in danger of possessing Dudes that are about to cross over the regional area. The dark grey, as in your examples Bubba, again just shows squares that have been previously eliminated. Once those regions have been eliminated, you break up the remaining regions into 9 pieces as well.

Finally, you eliminate all regions that are not directly surrounding the Dude. At the borders, this would take a few additional lines to ensure you include anything that need so be wrapped around or not. You're then left with 9 Regions which could possess Dudes that also will be crossing the boundaries. So then, you check the Dude against all Dudes in the surrounding boundaries. Implementing the Distance and Dot Product check as much as you like, because there shouldn't be any case where they could spit out a "wrong" answer.

Of course, if it meets your fancy. You can split to more depths.

What are the thoughts on this?

Looks good.

But let me re-enforce that the dot product operation will never spit out incorrect information. If two vectors are pointing in nearly the same direction their dot product will ALWAYS be >0 since the angle between them is acute. When they are perpendicular the dot product will ALWAYS be zero and when they are pointing in nearly opposite directions the dot product will ALWAYS be <0 since the angle between them is obtuse.

Sorry, with the dot product I just meant that if two Dudes are travelling in opposite directions, then there still is a chance that they can hit because of how the world wraps around the edges of the screen. If two Dudes are at opposite edges of the screen, both about to cross over, the dot product would be < 0 no?

And after some more thought, The Quadtree could also accomplish what I had with that "Nontree" couldn't it?. Probably even better. 800x600, 1024x768, 1152x864, and 1280x1024 can all be split do a depth of 4 by the Quadtree and still use whole numbers (while some can go much deeper). I'm a big fan of whole numbers when it comes to dividing things up like this.

So, Quadtree it is, with checking surrounding regions as well. Then optimizing. And I hope I don't lose too much speed once it's all done Thanks, alot, for the most recent help Bubba.

It's been my pleasure.



Post the final product here if you could. I'd like to see what you come up with.
Culling is essential in graphics and I think this is a very important topic.

I can't believe I've actually gotten this far. You have no clue how hopeless I felt when I first left this thread

Current condition:
- Basic framework is complete

- Can create a Quadtree of your chosen Width/Height/Depth

- If you don't supply a Depth, it calculates the most amount of Depths possible before whole numbers run out.
I.e. 800x600 will go to a Depth of 3, because there, the leaves will have dimensions of 100x75, any lower depth causes decimals to arise.

Soon to come:
- Traversing the Quadtree to stored data

I tested the nuts out of this one, and I would be very heartbroken if somebody told me it wasn't working properly. I tested by running a 800x600 screen to a depth of 4, and diagramming each Branch's Information on paper. What I got was the result that any Quadtree should give, so I'm very confident it's initialising properly.

The picture below shows how it's layed out in the Vector. It's an example of going to a Depth of 2, with the arrows showing parent/child relationships. Green highlighted numbers are leaves.

IDs:
1 = Top Left
2 = Top Right
3 = Bottom Left
4 = Bottom Right

I've included the source code for now incase you want to take a peek at it anyways. It gives limited information as you go, though you can uncomment a few lines (you'll know which ones) in cQUADTREE.cpp that will give information on a per-branch basis.

Give 'er a look if you like. I'll post an update once it's ready.

UPDATE EDIT:
Wow, I'm so excited After a few hours of writing out many, many numbers onto paper, I think I've finally found an algorithm to traverse the Quadtree. I know nobody else is excited about this, but I am, so there.

ANOTHER UPDATE EDIT:
I just wrote...a one-dimensional Quadtree. See, I read some brief descriptions of Quadtrees, and then I decided to figure the rest out on my own. The final product is something that works EXACTLY like a Quadtree, except, it's not a Quadtree. It's just an array. Which makes it slower, especially when having to calculate exponents to find proper indices...never mind...it doesn't make much sense unless you're sitting here beside me looking at the code I put together. I'm going to add one more method that draws a rectangle on the screen that represents the leaf you click on.

But after that, I'm scrapping it and writing a real Quadtree. You'll see (or maybe not) what I mean soon.

Big Note:
This is not a Quadtree. It just thinks it's one. I use the term Quadtree in this post very loosely.

Okay, here's the final product:
- Acts completely like a Quadtree except for the whole Quadtree part.
- Minor Informational MessageBoxes pop up during initialization to give you minimal info as to how the Quadtree is being initialized.
- More Information can be gotten by uncommenting lines in the source code. It's pretty easy to spot, the important ones are surrounded by a lot of comments detailing what to expect.
- I lost much motive when I realized I wasn't actually making a Quadtree.
- This method is much slower, for the reason of having to calculate the index at which a leaf is located in my one-dimensional Quadtree Array:

Code:

Offset = 1;
for(int I = 1; I < (TargetDepth - Depth); I++)
{
	Temp = 1;
	for(int J = I; J < (TargetDepth - Depth); J++)
	{
		Temp = Temp * 4;
	}
	Offset = Offset + Temp;
}

- If anybody can tell me how to calculate exponents without needing those for loops (and keeping header dependancies to a minimum), then the shabbiness of this method would also be erased.
- When you run the program, and you click on the screen, the corresponding leaf (based on your values given) will be coloured a random green. It looks pretty cool if you colour everything in.
- Set your values in cQUADTREE.h
- The DrawLeaf() method, yeah, I know, SetPixel is slow. But Drawing a rectangle without anything extra is a pain, and it's the simplest method I could think of.
- If a Depth isn't specified (I.e. 0) then the program will calculate the maximum Depth Level. I find this very neat. But then again, my opinion is somewhat biased.

Now, I'm off to make a real Quadtree, and let's never speak of this ever again.

I'm close to finishing up this Quadtree, but I've started wondering if it's actually completely necessary...

Once you have your Quadtree, your screen is split up into a various number of leaves. The plan so far was to start with Leaf(0,0) and check all surrounding leaves for collisions with Dudes, then move to the next leaf, and then so on.

But, each time you want to check a Dude, you have to traverse through the Quadtree to find the Leaf he is located in, so, would it not make more sense to just have a 2-Dimensional Array of leaves once you're done the tree, and then just scrap the Quadtree completely?

This would eliminate traversing time and leave you with just the necessary components.

I'm thinking of going with this idea more, and making something along the lines of a 2-Dimensional Array, but in a linked list form. Each region would be linked to its 8 surrounding squares to ease many future problems (I.e. adding/removing Dudes).

So, the blueprint for one Leaf:
- Left, Right, Top, Bottom Boundaries
- Pointer to 8 Surrounding Leaves
- And some other stuff that I'm sure I'm missing

Essentially it does the same as the Quadtree, but leaves out the unnecessary traversal portion. It will be a bit more complicated to set up and link properly (I'm thinking) but in the end, I think it will be a bit more useful and efficient...

Your thoughts?