Jump to content
  • Advertisement
Sign in to follow this  
Frogleap

3D AABB test, find closest available space/location to given location.

This topic is 819 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

So the point/task is "somehow" to determin where i could move AABB safely (without intersections) and close as possible to given location (point).

Usually it will be some point on the surface and most likely where will be space upward (but not always) in real scenario i want to implement teleportation of a unit to a given point. And also one important thing, this movement should be biased toward unit's (AABB) current position ie constrained by distance. All tests are AABB vs AABB

 

My question is, what efficient approaches exist to solve such kind of a problem? And in general the direction is should looking to.

Share this post


Link to post
Share on other sites
Advertisement

I don't know a highly efficient way to do this, although I'm very certain that there will be. However, the general process for testing a location to see if a defined AABB vs other AABB's could fit without any intersections isn't too difficult.

 

First, have an AABB defined that you want to use to test if you can teleport to a location (i.e. the size of the unit). Now move that AABB, or create a copy of it, to the desired location you want that unit to teleport to and perform an intersection test with other AABB's in the area. If this returns that no intersections where found you know that you can teleport that unit to that location.

 

If you have found an intersection, run some tests offset from the desired location in a different direction (i.e. above, below, left and right) to see if there is somewhere nearby to teleport to, although I'm sure there are better ways to do this sort of test. Maybe using some form of binary search like a KD-Tree or QuadTree to perform a fast lookup of other units in the area before doing the AABB intersection tests?

 

As for if the surface at the desired location is not flat and facing upwards, such as a ramp, or an object that is rotated look into oriented bounding boxes (OBB).

 

This might be useful: http://www.gamasutra.com/view/feature/131833/when_two_hearts_collide_.php

Share this post


Link to post
Share on other sites

Thank you! it's mostly the same i thought myself. and so the most important/interesting part is

run some tests offset from the desired location in a different direction (i.e. above, below, left and right)

to know/use some specific pattern for these tests.

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!