Til Dawn
Table of Contents:
- Overview
- Spatial Partitioning
- Grid System
- Collisions
- Collision Tree
- Artificial Intelligence
- Screenshots
Overview:
Til Dawn is a group project I became a member of in June of 2010. The team consists of 14 people: 8 programmers, 3 artists, 3 internal producers. The game is a Third Person Shooter where you play as Dietrich, a vampire who is hunting lesser degenerate animalistic vampires that are plaguing a town, which serves as your main source of food.
Back to Top
Spatial Partitioning:
A partner and I worked on the game's spatial partitioning. Til Dawn uses a squard grid Bounding Volume Hierarchy (BVH) that cuts the static level up into square grid portions. When the player needs to check collisions against a triangle, the CPartitionManager class returns a vector of triangles within the square the player is in, along the the 8 surrounding neighboring grid squares. Right now we're only using a sample level, but we've been able to cut the amount of triangles we're testing from 12,000 down to around 1,000.
The CPartitionManager class we wrote, once initialized, first checks to see if a partition file already exists. If the file exists AND the version number of the file is synchronized with the game's current partition version, the game will load that partition file, thus saving expensive loading time. However, if the file does not exist or the file is not the correct version number, the CPartitionManager will recalculate and recreate the BVH Grid and partition file.
The reason we do this is to allow our artists to change the level and static objects in the level without hindering or breaking our system. Anytime a change is made to the level, we simply update the version number. The ultimate goal of our CPartitionManager is that right before our game is released to the public, we will build a final partition file, and just ship the partition file with the game.
Back to Top
Grid System:
Our game's partitioning system ran into a problem today, and due to working with that problem, it has been changed.
Our game is partitioned using a 2D grid system that overlooks the world from a top-down view.
Here's an example world shown from the top-down view.
Here's the world broken into the grid system.
Our world's triangles use to be split up using 2 checks. The first split is determined by seeing if any of the triangle's vertices are within the grid.
However, this will not cover all situations,...
... So we had another check after that to see if any of the grid's corners were within the triangle.
And for awhile, this system worked great in our game. However, recently we discovered a special situation that slips through the partition system...
As you can see in the above situation,... no vertex of the triangle is in the grid, and no corner of the grid is within the triangle... So our character was running through walls in our game!
So we revamped the partition system. Now there's only 1 check, it's much faster than any other the other checks, and it works for all situations.
We flatten every triangle in the world by setting it's Y to 0 (rather, just ignoring the Y completely), and then do a 2D Line to Box intersection. This covers all situations.
Back to Top
Collisions:
Collisions is something I've slowly been forming a specialty in, or rather have just been getting really good at doing. In this game, 4 people have worked on the collisions, myself included. Currently, since we haven't gotten all of the models and the final level into our game, I can't claim that collisions are 100% finished. However, I will say that they are ready for testing.
Fortunately, our game's characters do not jump. This allows the collision in our game during WALKING to be very, very easy. For the movement of characters in our game, our game utilizes Ground Clamping, via Ray to Triangle intersection. For the Wall collisions (ie: Player walks into the wall of a house) we use a Sphere to Plane check. So if the player clamps to the ground AND he's not too close to a wall, he can walk wherever he wants.
Back to Top
Collision Tree
For the Collision of the Player and Enemies in the game, we implemented a collision tree hierarchy, made up of spheres. The player/enemy is first surrounded with an overall outersphere that encompasses the entire mesh/model. After that a sphere is generated around every joint on the mesh that encompasses all vertices related to that joint. Then from there, every joint sphere is broken down either recursively or a set amount of times (depending on what you pass into my SplitNode() function). If you choose to split the spheres recursively, they will split until the radius of the new sphere hasn't changed very much from the parent sphere. Usually if the child sphere radius is at least three-quarters the size of the parent sphere, the recursive splitting will stop.
Every frame when collisions are checked, the outermost sphere of the creature is checked against the other collision object. If a collision has been detected, then further testing on the child nodes is done. If collisions return true all the way down at the deepest nodes, a collision has occurred. The spheres are stored at the bind pose, so in order to get the spheres in the correct spot during an animation, you first have to take the influencing Joint Matrix and multiply it by the transpose of the inverse bind pose matrix. Then you transform the sphere position by the resulting matrix. After that, you have to transform the sphere position by the object's matrix.
Here's two pictures that show the collision tree on an enemy being rendered.
Entire Collision Tree of Spheres Rendered:
Deepest Nodes of Collision Tree of Spheres Rendered:
Back to Top
Artificial Intelligence:
Although I cannot claim to be currently spearheading the Artificial Intelligence in our game, I can say that I've done a little bit of work on it. We were having an issue with the monsters of the game not properly flocking towards the player, in that the monsters would travel towards the player, but they wouldn't rotate to face the direction they were traveling in.
So the way I was able to help in this was that I suggested that because we have a movement direction and the player's Z Axis, that we should find the angle between these 2 normalized vectors and rotate the player on his Y Axis based on that angle. The solution came out quite nicely.
Back to Top
Screen Shots:
Thumbnails - Click to Enlarge:
Back to Top