Thread: GetPixel, HDC, and heartattacks

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?