# AABB swept collision response with voxel world

I followed this tutorial: link and I was able to make it work with 3d voxel world collisions.

But the problem I have is with collision response. I want to make player slide against the wall if he is running against it, but instead he gets stuck at each voxel edge.

That is happening because I am getting normals with AABB swept test from voxels that are a part of the wall. (Yes, I am doing broadphase check first).

In the image above is 2d representation of my problem. Voxels are black rectangles, blue one is player, red is swept check area and green lines are normals.

Possible solutions I thought of are: - Merging voxels into bigger collision boxes based on neighbours, but I think that would cause other problems when holes appear and player size increases. - Ignore collision normal if there is neighbour voxel along side normal. This is what I have currently in my code and works fine for sliding against walls while on ground, but fails when falling against them: http://ideone.com/xdsr2d

Because there's many voxels in that are colliding and order of collisions (the order of voxels and normals that I receive after aabb swept test) is hardly predictable neither sollution seams to be good enough.

I would appreciate any help because I've been bashing my head around this problem for quite a while.

(Also if there's anything wrong with my question do tell, this is my first time post on gamedev.stackexchange)

TL;DR: process collisions Manhattan-distance style http://en.wiktionary.org/wiki/Manhattan_distance, each axis independently one-by-one (move in X, then move in Y, then in Z, rince and repeat) properly rounding each axis before processing the next.

AABB / Voxel collision systems work the same way old tile-based 2D games did, you add a 3rd dimension but otherwise are identical:

For simplicity let's assume a voxel is 1x1x1 and position is the corner toward negative infinity, you need to check movement against each axis independently and properly "round" each axis after colliding them (not round as in +/-0.5 but align them a tiny bit away from the AABB grid).

Do your collisions using integers for each axis. Example here is for X check for simplicity, this should be turned into a nice for-loop. I'm using floats here but ideally with voxel collision systems fixed-point math should be used instead for easy predictability.

const float SMALLER = (1.0f / 16.0f); // give a Retro-style 1-pixel smaller AABB in each directions on a 16x16 pixel tile scale to fit in holes (we use 1.0f for one tile / 16.0 "pixels")
const float EPSILON = (1.0f / 1024.0f); // a value that is small enough to not show vibration on screen when bumping against the walls but remember you only have 24 bits of precision with floats.
// NOTE: use binary sizes (incl fractions) as much as possible to help stave off float rounding errors.

if(move.x != 0){
int min_x = truncf(position.x + SMALLER);
int max_x = truncf(position.x + AABB_SIZE.x - SMALLER);
int min_y = truncf(position.y + SMALLER);
int max_y = truncf(position.y + AABB_SIZE.y - SMALLER);
int min_z = truncf(position.z + SMALLER);
int max_z = truncf(position.z + AABB_SIZE.z - SMALLER);

int start_x;
int end_x;
if(move.x > 0){
start_x = max_x;
end_x = truncf(position.x + AABB_SIZE.x + move.x - SMALLER);
} else {
start_x = min_x;
end_x = truncf(position.x + move.x + SMALLER);
}

for( pos_x = start_x to end_x ){
if(AnySolidVoxelsInArea(IntVector(pos_x, min_y, min_z), IntVector(pos_x, max_y, max_z))){
// align to surface (EPSILON pushes the character slightly away from the wall)
if(move.x > 0){
position.x = pos_x - AABB_SIZE.x + SMALLER - EPSILON;
} else {
position.x = pos_x - SMALLER + EPSILON;
}
move.x = 0;
break;
}
}
position.x += move.x;
}


repeat for Y and Z.

Otherwise you'll need to build a huge collision map made up of continuously linked planes from the voxel grid and properly slide along those connected planes.

• Would your solution work if your character is at 0,0, moving towards 5,5 and there is obstacle at 0,3 and 3,0? That is, your character should end up in 5,5. – user55564 Dec 7 '14 at 16:01
• The solution looks interesting. I'll try to see if it does fit my application and might implement it, but until that happens I'm not sure I can accept this as an asnwer. Big thanks for the detailed explanation :) – serengeor Dec 7 '14 at 19:01
• @user55564: It would work if you step by 1 in each axis then repeat this 5 times, like drawing a thick line in a 2D bitmap except in 3D. Octrees and/or empty/full tile grid can be used to speed up the collisions. – Stephane Hockenhull Dec 8 '14 at 3:35
• I recommend experimenting with 2D tile-based collision systems from the 1980s, 3D voxel AABB collisions works the same way. They're just 3D pixels. You'll find the exact same issues and solutions (plural). – Stephane Hockenhull Dec 8 '14 at 3:46
• @StephaneHockenhull What if now your character is at 0,0, moving towards 5,5 obstacle at 3,3? Seems like your suggestion only works well with low velocity. – user55564 Dec 8 '14 at 4:27