Hi!
In Vertical-Slide update, we are bringing changes to character movement. The collision detection was reworked to smooth out motion in arenas and remove annoying hiccups during fast-paced action. This allowed us to boost vertical sliding – feature, that started as a bug. For full changelog, scroll down below.
Today we’ve brought a detailed description for you who are interested in technical details, engine or gamedev programming. We think it is important to share the knowledge and discuss it – either someone may learn from our successes and mistakes, or quite oppositely they can point out imperfections we missed.
Why custom physics?
11th Dream simulation runs on our limited collection of physics related functions. Everyone with a game-dev experience would ask, why did we decide to skip existing third-party physics engines and rely on our own.
When the development started, all the movement and collision systems were rather simple. Static objects were using axis-aligned boxes for their collision geometry and characters were represented as 3D points. Terrain was a simple bitmap of heights. Projectiles were moving slowly enough to represent them as points, too. For these primitives, importing tens of thousands of lines of code seemed unreasonable.
As we progressed with prototyping, we needed to develop some collision queries for non-player characters (NPC). To confirm that NPC is in line-of-sight, raycasts were introduced. Later on, we realized that making collision boxes by hand slows us down and that it is a tedious job. It felt natural to add triangle mesh as a new type of collider to speed up map creation. Character representation was changed to a bounding box.
The point is probably clear. When we started, the physics scope was too small to use a third party engine. For today’s state, we would choose it right away, but our code (which has grown slowly over time) is already in place.
Algorithm
It is quite easy to find collision algorithms online, but much harder to discover their use in character motion. Therefore, we do not describe here the details how to compute tri-vs-box collision or build a collision hierarchy (but we provide some links below this article).
Our character is represented by an axis-aligned bounding box. When the simulation ticks, the character tries to move to a new position. We perform collision detection in two steps.
Resolve support
Legs of in-game character are bounded by an additional box which is used to determine whether the character is grounded (supported). Boxcast is performed and the topmost contact point sets the new elevation. Note that this affects only y-position of the character to prevent unwanted sliding on slightest slopes!
After the character is moved, we perform a second boxcast, this time with full character box, to check whether we ended up in free space. If this is true, the algorithm ends here. Otherwise we need to continue to next step.
Other collision detection
Now the character is in trouble, so we make use of the box cast. Each collected contact point contains position, resolution normal and penetration depth. The position describes where the contact happened, the resolution normal tells us which direction to move away from collision and penetration depth tells us how far.
However, we cannot simply pick first contact point, move the character and pretend that we are done. Some of reported contact points can be still inside of the character’s box! This is exactly the mistake we did in the previous version. We must pick a contact point such as:
- penetration depth is minimal,
- all the other contact points are moved out after correction.
Afterwards, we repeat the algorithm and resolve support once more. In some cases it is possible that no solution is found even after few iterations and then the character must be moved to last recorded safe position, otherwise it can end up inside something.
Vertical sliding
Being able to slide up when pushing against the obstacles, that is something we introduced by mistake. But it felt so good! Later we discovered that it was (of course) the support resolution which caused this funny mechanic. With today’s update, we reforged it from a bug to consistent behavior.
The implementation was in the end very simple: Is the character touching anything? Yes? Good, you can slide up!
Full changelog
The updated version is now available on Steam, bringing to you:
- Collision system reworked
- Vertical sliding reworked
- Added decal effects when sliding up
- Fixed issues in AI navigation, preventing NPCs were getting stuck
- Fixed: Timing of shooting sounds
- Fixed: Late announcement of First Blood
- Fixed: Resetting settings did not reset BW mode
- Tweaked: Difficulty of Taking Apart decreased
- Tweaked: Friendly bot behavior in Taking Apart
- Tweaked: Projectile impulse zero in inverted gravity
- Tweaked: Projectile speed affected by character evilness
See you in the arena!
Best,
Michal
11thdreamgame.bluepulsar.cz
Follow us on twitter or instagram and ask us anything on our discord server. We are also happy to invite you to join our new mailing list, so you stop missing all those 11th updates!
Big thanks goes to Daniel Ilha for reviewing this blog post.
Links
- Ericson, Christer. Real-Time Collision Detection. 2004. ISBN 978-1558607323.
- Collection of collision detection algorithms at the finest level.
- Gabor Szauer. Game Physics Cookbook. 2017. ASIN B01MDLX5PH.
- Collection of collision detection algorithms at the finest level.
- kdrnic. Triangle-Box SAT test in Javascript. https://github.com/kdrnic/TriangleBox.js
- Sample implementation of tri-box SAT test in Javascript. Different language than we use and that’s sometimes better, it forces to think about the problem, not just copy blocks of code.
- Wikipedia. Bounding Volume Hierarchy. https://en.wikipedia.org/wiki/Bounding_volume_hierarchy
- BVH is one of the options how to speed up collision queries. 11th Dream uses BVH for organizing static objects.