Jump to content
  • Advertisement
Sign in to follow this  
danpsy

2D QuadTree Implementation

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!