collision detection with world
Basically the root node has a width and height equal to the max side(which is just big enough to contain your entire environment) Then each child node is half width and half height of the parent, which turns into 4 nodes for quadtree and 8 for octree and so on
You might want to look into a book on the subject, like Real-Time Collision Detection, by Christer Ericson.
Author
I know how the hierarchy works, but my problem is that the world isn't just flat, which wouldn't have been a problem then. And I need to create OBBs since you need to walk up and down etc. I'll take a look at the book, thanks for the tip!
Well you wouldn't even need to check if your player is colliding with all of the quad-trees bounding boxes. If your world is broken up into equal segments then the player position in itself will tell you what box it is in.
say if it was 10x10 grid (not taking height into account)
and your world would be say 500, 500.
First your check if the position is greater or lower then it could ever be.
If it's within acceptable bounds say player position 324, 243.
The X position in you 10x10 grid(each bounds 50x50) would be (int)(324/(width of a grid segment) so in this example it'd be (int)(324/50) = 6.48 but cast as an int so 6.
Y position would be the same just use the length instead of the width. (int)(243/50) = 4.86 = 4. Now your position in that grid would be 6,4 (and yes this works as zero indexed).
This could work on any level of the quad tree also. Just the width and length change. Also if it is a 3D area (with multiple making up a cube) then it'd be the same way to check the height.
say if it was 10x10 grid (not taking height into account)
and your world would be say 500, 500.
First your check if the position is greater or lower then it could ever be.
If it's within acceptable bounds say player position 324, 243.
The X position in you 10x10 grid(each bounds 50x50) would be (int)(324/(width of a grid segment) so in this example it'd be (int)(324/50) = 6.48 but cast as an int so 6.
Y position would be the same just use the length instead of the width. (int)(243/50) = 4.86 = 4. Now your position in that grid would be 6,4 (and yes this works as zero indexed).
This could work on any level of the quad tree also. Just the width and length change. Also if it is a 3D area (with multiple making up a cube) then it'd be the same way to check the height.
If you use a quadtree for a terrain with height, such as you are describing, it doesn't matter because you create 2d bounding boxes(x and z axis's) and just check ALL geometry in those boxes regardless of height. If you want to further it by height then you use an octree which uses x, y and z axis.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
