This topic is 2580 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I've been searching and attempting to implement my own QuadTree algorithm for the past few days, but I haven't had any luck. What's the basic idea behind setting up and using a QuadTree?

Currently I have a blocks vector that I loop through each iteration to determine what to draw and for collision checks. An example:

 player.update(); for (int bi = 0; bi < blocks.size(); bi++) { if (InCameraView(blocks[bi])) { draw(blocks[bi]); player.TouchGround(blocks[bi]); for (int ei = 0; ei < enemies.size(); ei++) { enemies[ei].update(); enemies[ei].TouchGround(blocks[bi]); } } } 

This works alright for smaller maps, but the game certainly starts to feel more sluggish with larger maps. Would a QuadTree implimentation be beneficial, or would something else be better for what I'm trying to accomplish?

Thanks for any help!

##### Share on other sites
My guess is that the problem is coming from within the InCameraView itself. Perhaps are you testing all of the pixels and or verts of the block in the InCameraView function? If so you might want to attempt a slightly more generic calculation here. Perhaps keep track of a single center point, increase the calculatory frustum size slightly larger then that of the actual camera frustum size and this would limit you to only testing one position per block per frame? Also maybe think of completely deleting really far away blocks from the tree. You could implement a function that deletes anything that would be so far away that it would take more then say 3 seconds at your cameras top speed before it's even getting close again. Then I would personally track how far the camera has moved since the last test and use that to determine if you need to reload the assets on the fly. Of course this will take a lot of testing to get right but might be a couple ideas to think of. Best of luck.

##### Share on other sites
They way you describe what you have it seems like you making a 2d game, no? If you want to index objects that move around in the scene a spacial hash works very well and isn't too hard to implement.

Spatial Hashing

1. 1
2. 2
3. 3
Rutin
20
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633656
• Total Posts
3013186
×