Описание коллайдера игрока: комбинированный подход к обработке коллизий
Для представления коллайдера игрока в играх часто используют капсулы, однако сколько бы я ни пытался реализовать алгоритм столкновения капсулы с треугольником (Capsule vs Triangle), результат всегда получался громоздким и не таким лаконичным, как при использовании сфер. Но всё-таки мне было важно проработать код коллизий игрока максимально качественно, потому что я считаю, что коллизии — это одна из самых важных вещей в игре, плохая реализация которых может в любой момент испортить погружение.
Решено использовать сферы
После экспериментов с различными подходами, я пришёл к решению: коллайдер игрока будет состоять из трёх сфер, и для каждой из них будет применяться свой алгоритм:
- Алгоритм А — дискретное обнаружение пересечения сферы с геометрией (Discrete collision detection)
- Алгоритм Б — предсказание когда сфера ударится о геометрию (Continuous collision detection)
Расположение и предназначение сфер
Сфера в голове игрока (алгоритм А):
В её центре находится камера. Её задача — не позволять камере проваливаться в текстуры (например, в стены или потолок).Сфера в теле (алгоритм Б):
Основная сфера, отвечающая за движение. Она позволяет игроку скользить вдоль поверхностей и предотвращает клиппинг сквозь геометрию, с какой бы скоростью игрок не двигался.Сфера в ногах (алгоритм А):
Сфера в ногах следит за тем, чтобы игрок нигде не застревал и у него всегда была возможность двигаться.
Дополнительный элемент: Луч из ног
На самом деле этот луч исходит приблизительно из уровня коленей. Он мониторит уровень земли под ногами, не давая игроку упасть под карту, и даёт возможность беспрепятственно ходить по ступенькам. Он так же может быть полезен, если в будущем мне потребуется определять на какой поверхности стоит игрок в данный момент. Для него я написал специализированный алгоритм рейкастинга, оптимизированный с учетом того, что луч направлен строго вниз по оси Y.
Алгоритм рейкастинга для луча направленного строго вниз по оси Y
BOOL DownwardRayVsTriangle(Point ray_origin, Triangle t, float *out_distance)
{
// Calculate edges
Vector ab = Vector_Sub(t.b, t.a);
Vector ac = Vector_Sub(t.c, t.a);
// determinant = dot(ab, p)
float det = ab.x * -ac.z + ab.z * ac.x;
if (det > 0.0f) {
return FALSE; // triangle is degenerate or backfacing
}
// u = dot(s, p) * inv_det
float inv_det = 1.0f / det;
Vector s = Vector_Sub(ray_origin, t.a);
float u = (s.x * -ac.z + s.z * ac.x) * inv_det;
if (u < 0.0f || u > 1.0f) {
return FALSE;
}
// q = cross(s, ab)
Vector q = Vector_Cross(s, ab);
float v = -q.y * inv_det;
if (v < 0.0f || (u + v) > 1.0f) {
return FALSE;
}
// t = dot(ac, q)
*out_distance = Vector_Dot(ac, q) * inv_det;
return *out_distance >= 0.0f;
}
Сферы в голове и ногах позволяют компенсировать неточности алгоритма Б
Плюс ко всему стоит отметить, что есть сценарии, с которыми алгоритм Б не способен справиться. Например, если игрок падает вдоль стены, то алгоритм Б может ошибочно посчитать, что столкновения не произойдёт (из-за параллельного движения). Может возникнуть ситуация, когда сфера окажется внутри геометрии и алгоритм Б не сможет определить коллизию. Но дискретные сферы в голове и ногах подстраховывают от таких сценариев.
Реализация в коде
Псевдокод моей реализации этой системы:
BOOL void Player_MoveAndCollide(Entity *player, Vector movement)
{
//
// Apply movement and check for collisions along velocity
//
Vector movement_remaining = movement;
for (int i = 0; i < 2; ++i) { // max bounces = 2
float movement_distance = Vector_Length(movement_remaining);
if (movement_distance <= COLLISION_EPSILON) {
break; // no more movement needed
}
Vector movement_direction = Vector_Normalize(movement_remaining);
const Sphere spheres[] = {
(Sphere){ Player_GetHeadPosition(player), PLAYER_RADIUS },
(Sphere){ Player_GetFootPosition(player), PLAYER_RADIUS }
};
CollisionResult collision = FindSweptCollision(spheres, ARRAYSIZE(spheres), movement_direction, movement_distance);
if (collision.hit == FALSE) {
// No collision: move freely along full velocity
Player_ApplyMovement(player, movement_remaining);
break;
}
// Move up to collision point (with small offset to prevent sticking)
float safe_distance = fmaxf(0.0f, collision.distance - COLLISION_CONTACT_OFFSET);
Vector safe_movement = Vector_Mul(movement_direction, safe_distance);
Player_ApplyMovement(player, safe_movement);
// Remove Y component to prevent player from sinking into a narrowing space
Vector slide_normal = (Vector){ collision.normal.x, 0.0f, collision.normal.z };
slide_normal = Vector_Normalize(slide_normal);
// Slide along wall/floor by projecting movement vector on plane normal
float slide_amount = Vector_Dot(movement_remaining, slide_normal);
movement_remaining = Vector_Sub(movement_remaining, Vector_Mul(slide_normal, slide_amount));
}
//
// Apply gravity and check for ground collision
//
static float player_ground_level = 0.0f;
static float player_vertical_velocity = 0.0f;
// Find ground level
Point ground_check_origin = (Point){
player->x,
player->y + PLAYER_STEP_HEIGHT,
player->z
};
float ground_dist;
if (FindGroundCollision(ground_check_origin, &ground_dist)) {
player_ground_level = (ground_check_origin.y - ground_dist) + COLLISION_CONTACT_OFFSET; // calculate a new ground level
}
// Apply gravity
player_vertical_velocity -= 1.0f; // apply gravity
player->y += player_vertical_velocity * time_delta;
// Prevent falling through the ground
if (player->y < player_ground_level) {
player->y = player_ground_level;
player_vertical_velocity = 0; // reset velocity
}
//
// Verify that player is not stuck
//
Capsule capsule = {
.p1 = Player_GetFootPosition(player),
.p2 = Player_GetHeadPosition(player),
.radius = PLAYER_RADIUS
};
CollisionResult collision = FindPenetratingCollision(capsule);
if (collision.hit) {
Vector push = Vector_Mul(collision.normal, collision.distance);
Player_ApplyMovement(player, push);
}
}
Такой гибридный подход показал высокую производительность и стабильность. Я планирую использовать эту систему для коллизий игрока в своём проекте, в то время как для физики твердых тел мне приглянулся метод SDF (Signed Distance Field) Collision Detection, но об этом в следующей заметке.