AABB's and Their Use

Hey there!

I’m just doing a bit of brainstorming here. Let’s say I want to make a door “threshold” and I’d want the player to get a message "Entering ___ " and “Leaving ___” based on whether or not they cross that threshold entering the building, or leaving. The way I’m currently doing it is having a runnable check every half second (10 ticks) if any player is within radius of every location’s center, thus basically saying if the player is “inside” this area and they’re “new” to it, send a message.

I was thinking a more convenient way might be to assign every block making up the area’s outline an AABB. Now, is there an event that automatically fires when one AABB collides with another, or would I be left having to essentially do the same thing as above, basically just having a runnable check if any AABBs have collided?

Thanks! :smiley:

There isn’t any event for collisions with user defined AABBs since the game doesn’t know about them. It only checks collisions with AABBs it knows about, which are the entity and block ones. A check every tick or so (maybe every 4 ticks) is probably your best bet.

You can optimize the collision checks by culling to only the AABBs within the same chunks as the player. You do this by converting the player AABB corners to the chunk coordinates (for efficiency you would operate on the ints instead of using the vector objects, and use >> 4 to convert to chunk space).

You then use a map of int pairs that represent coordinates of a chunk (stored as longs with the upper 32 bits being the x coordinate and the lower 32 the y coordinate) to a list of AABBs intersecting with the chunk. For extra efficiency this should use a fastutil Long2ObjectMap.

This way you can cheaply narrow the intersection checks to only a few chunks (up to 4 if the player is at corner of a chunk). The list of AABBs in the chunk should be small, so you can simply iterate against them.

Just make sure you properly assign an AABB to multiple chunks if it overlaps more than one. To check which chunks an AABB belongs to, convert its corners to chunk coords and add those chunks, plus any chunks located between the corners. This should be done once on start up or when a new AABB is added.

There’s also some potential for doing this in a separate thread, by feeding the player coordinates for a tick to a queue that is processed in parallel, but I doubt it would be necessary.

1 Like

Thanks for the info! I’ll definitely have to read through this a few more times to fully understand what you’re saying though xD

Perhaps an easier way: What if I just give every “area” one big AABB encompassing the whole thing? Then just check for collision. The only question I’d have there is, does collision only happen on the “edges” of the AABB or all through it? Meaning, would the collision only happen when a player walks across the edge or while the player is walking around inside the AABB?

@DDoS Ingenious approach!

@Jimmy The AABB class has contains methods to check whether the provided position is encompassed in the AABB.

I agree the @DDoS’s approach is genious. haha. Although it’s currently over my head, I’m gonna keep reading through it and see if I can piece the code together.

However if I just went with one AABB per area, that contains method could certainly accomplish what I’m looking do to (I think).

What @DDoS suggest, is, that it may be expensive to loop through all of the AABBs every 10 ticks, so later, you might want to consider optimizing the code to make the lookup of AABBs faster.

The way we would do this, is basically make a Map<Chunk, Set<AABB>> where each chunk would point to a set of AABBs within the Chunk. Then, every 10 ticks, you iterate only through those AABB depending on what Chunk the player is in.
There is a slight problem, though, and that is, that having a Chunk as the key might not work properly, so instead, we take the location of the chunk and create a key from it.
That would be done this way:

Vector3i chunkPosition = chunk.getPosition();
long key = (0xFFFFFFFFL & chunkPosition.getX()) << 32 + (0xFFFFFFFFL & chunkPosition.getZ());

You would also need to figure out the algorithm of registering the AABBs in the Map<Long, Set<AABB>>, you somehow need to iterate through all of the Chunk positions.
To get the chunk position from a world position, you’d use

Vector3i chunkPosition = Vector3i.from(worldPosition.getX() >> 4, 0, worldPosition.getZ() >> 4)

Since an AABB is defined by two positions; the lowest one and the highest one, you can convert them to the chunk position this way and then iterate through all the chunks in between them.

@Limeth Thanks for the explanation! That makes more sense now. Do you think it would be considerably worse practice to just assign every “area” its own AABB encompassing the whole thing rather than assigning every block that makes up the area’s outline its own AABB like I had mentioned in the first post?

I think it’s the optimal solution, can’t quite imagine how it would work with the outline.

Awesome. Well, this is definitely something to work off of. Thank you both!

@Limeth Quick question! So you said that I could get the chunk a certain “normal”/“world” position is in by Vector3i chunkPosition = Vector3i.from(worldPosition.getX() >> 4, 0, worldPosition.getZ() >> 4), correct?

So if I had an example like this: Screenshot - 9ceb098ef883aefbd62a1a9aa29e03de - Gyazo, where the AABB is in 2 different chunks (the AABB being represented by the shaded area), I could get both of those chunks by each of the corresponding points, (8,0) and (24,16)? I wouldn’t need to make my own custom method of finding a chunk for a “split” AABB?

Thanks for the help!

Correct. Just make sure it even works when it spans over 3 or more chunks on one axis.

@Limeth Oh, that’s true. So I’d probably want to get 2 chunks and then iterate through all the chunks in the world and add the chunks between the “start” and “end” chunk?

for(int x = lowChunk.getX(); x <= highChunk.getX(); x++) {
    for(int z = lowChunk.getZ(); z <= highChunk.getZ(); z++) {
        // this executes for every chunk in between of lowChunk and highChunk, including them
    }
}
1 Like

Brilliant! Thank you!

@Limeth I’d just like the check one more time xD Is this how you would approach it?

public class LocationUtils {

public static List<Vector3i> getChunksBetween(Vector3i start, Vector3i end) {
    List<Vector3i> give = new ArrayList<>();

    if (start.getX() < end.getX()) {
        for (int x = start.getX(); x <= end.getX(); x++) {
            for (int z = start.getZ(); z <= end.getZ(); z++) {
                Vector3i result = chunkPositionFromWorldPosition(new Vector3d(x, 0, z));

                if (!give.contains(result)) {
                    give.add(result);
                }
            }
        }
    }

    return give;
}

public static long chunkPositionToLong(Vector3i position) {
    return (0xFFFFFFFFL & position.getX()) << 32 + (0xFFFFFFFFL & position.getZ());
}

public static Vector3i chunkPositionFromWorldPosition(Vector3d position) {
    return Vector3i.from((int) position.getX() >> 4, 0, (int) position.getZ() >> 4);
}

}

Thanks again for all the help! :smiley:

Edit: perhaps I should remove that first if (start.getX() < end.getX()) and just assume that I send the correct “order”.

There’s an implementation of the chunk-to-world-conversion in the API: ChunkLayout. I was suggesting doing it manually to avoid creating objects, if you’re looking for the best performance.