# 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.

## 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 on other sites

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 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.

1. 1
2. 2
Rutin
17
3. 3
4. 4
5. 5

• 9
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633717
• Total Posts
3013512
×