Third person game

Check it out here: https://kylenburke.github.io/

I’m excited to share with you all what I’ve been working on. I’m making a third person game and although the game right now is just a character you can walk around the level with, behind the scenes there’s a lot going on. That’s mostly thanks to the collision detection, as it can robustly handle pretty much any environment made of convex polytopes and/or single faces (because a face is still convex).

I can go into more depth if anyone is interested but essentially the collision detection engine uses a spatial partitioning tree (a KD tree) to retrieve the polytopes in close proximity to the player, this is the broad phase. From here a simple bounding box check between each polytope and the player’s collision hull is performed. Of the polytopes that pass that check, a narrow phase collision detection algorithm is used to determine with accuracy whether the polytope is actually colliding with the player’s hull. The algorithm I chose to implement for this is GJK (Gilbert Johnson Keerthi), because even though it’s much harder to implement than something like SAT (separating axis theorem), it’s extremely fast even for polytopes that have plenty of faces. Once a collision is detected, resolving it is a whole other problem. For this I implemented EPA (expanding polytope algorithm) which is nice because it’s also very efficient and goes hand in hand with GJK.

So yeah this has been quite the project and there’s still some more work to do with velocity response but I’m glad to share with you the current state of it.

11 Likes

Woah! This is awesome awesome work. I am just wondering: in the final product, do you intend to move the collision computations inside a web worker?

It’s an interesting idea but I haven’t thought about it. I might see if I can further down the road like if I start to run into performance problems.

Interestingly, I personally have trouble managing collisions.

Yeah it’s pretty complex. Even with these great resources on GJK and EPA it still took me a very long time to get working right. The theory behind these are harder to understand then some other near phase collision algorithms (like SAT) but it’s really not that bad. It’s the implementation that can be a real challenge, but if you’re determined, have enough time and understand vector math, you can definitely do it.

1 Like