Archive
This post is archived and may contain outdated information. It has been set to 'noindex' and should stop showing up in search results.
This post is archived and may contain outdated information. It has been set to 'noindex' and should stop showing up in search results.
Quadtree Beginner Guide 2D Games
Nov 20, 2011ProgrammingComments (0)
At some point when programming you probably realized that collision testing every object in your game is rather inefficient. A better way is to group objects based on their physical location in the game, and only collision test the bounds of the whole group. A quadtree does this, and can be used in 2D games to greatly speed up both collision detection and rendering.
Say your level is comprised of blocks:
To collision test the player against that level, you collision test each of the six blocks. As the level grows, this eats up a lot of processing power.
With a quadtree, you split the blocks up into groups of up to four per node:
Here the six blocks are put into three larger nodes. Notice that the size of the larger nodes can accommodate only four blocks each (hence the name "quad" tree). When collision testing, you first check the larger nodes, to see if a collision is found. If a collision is found, you go on to collision test just the blocks that are contained in that node.
If the player is not colliding with any of the larger nodes, you have reduced the total number of collision tests required from six to three.
We don't stop there though. Since each node of a quadtree holds up to four children, you should further break down your level into the next size larger nodes:
A quadtree can be broken up into as many levels as needed, so that each node only holds up to four children. Take a look at this level:
Mario is not colliding with any of the blocks in the level. Without the quadtree you might be checking every block individually. But with the quadtree you first check the largest nodes and find that no additional collision testing is needed (in this case).
Note that quadtrees introduce some overhead. If an object does collide with a block, you are now testing that block as well as all the incrementally larger nodes that the block is in. So, if your level only contains a few blocks, and a large object collides with all of them, the quadtree will increase the overall number of tests that need to be done. Though with normal-size levels, the reduction in collision testing nearly always makes up for the quadtree overhead.
Say your level is comprised of blocks:
To collision test the player against that level, you collision test each of the six blocks. As the level grows, this eats up a lot of processing power.
With a quadtree, you split the blocks up into groups of up to four per node:
Here the six blocks are put into three larger nodes. Notice that the size of the larger nodes can accommodate only four blocks each (hence the name "quad" tree). When collision testing, you first check the larger nodes, to see if a collision is found. If a collision is found, you go on to collision test just the blocks that are contained in that node.
If the player is not colliding with any of the larger nodes, you have reduced the total number of collision tests required from six to three.
We don't stop there though. Since each node of a quadtree holds up to four children, you should further break down your level into the next size larger nodes:
A quadtree can be broken up into as many levels as needed, so that each node only holds up to four children. Take a look at this level:
Mario is not colliding with any of the blocks in the level. Without the quadtree you might be checking every block individually. But with the quadtree you first check the largest nodes and find that no additional collision testing is needed (in this case).
Note that quadtrees introduce some overhead. If an object does collide with a block, you are now testing that block as well as all the incrementally larger nodes that the block is in. So, if your level only contains a few blocks, and a large object collides with all of them, the quadtree will increase the overall number of tests that need to be done. Though with normal-size levels, the reduction in collision testing nearly always makes up for the quadtree overhead.