Crush! Breakdown Part 2 - Collision World
In part one of the Crush! breakdown I outlined the scene graph used to transform and render game entities, as well as some of the controller classes used to manipulate nodes within the scene. Entities are created by attaching a combination of components to a node, one of which is the collision component - used to make the nodes react to external forces and resolve collisions between the bodies. My instinct for this kind of thing is usually to reach for a library such as chipmunk or box2d, but experience has taught me that this is often overkill for a small project, and will probably not yield great results if the game isn't inherently physics based (such as Angry Birds for example). On top of this I'm always willing to investigate new areas of programming, so giving the subject of physics and collision handling some serious study was an idea which appealed to me. To prevent presenting myself with a daunting scope I tried to reduce the amount of complexity as much as possible by looking carefully at what would actually be needed. After some cogitation I decided that all I needed were rectangular bodies with no rotation which reduced the scope dramatically when considering what would be needed for collision detection. Normally I would give body properties mass so that each body's acceleration could be calculated by the current force acting upon it, using Newton's second law of motion: force = mass * acceleration. Even this could be reduced so that a collision body only needed a velocity vector, a position, and a bounding box.
struct CollisionBody
{
vector2 m_velocity;
vector2 m_position;
floatRect m_boundingBox;
}
Each frame the body's position is updated by adding the current velocity to it. The velocity is adjusted by either applying an external force (by adding another vector to the velocity), or as a result of a collision. Collision bodies exist within a CollisionWorld class, which is responsible for creating bodies, detecting collisions between them, and applying any resulting forces. The CollisionWorld class also acts as one of the controller classes, and so the instance lives alongside the other controllers in the GameState class. Apart from the factory functions of the CollisionWorld class, the beef of the code exists inside:
CollisionWorld::update(float dt)
{
//test which bodies intersect and mark as collision pair
m_collisions.clear();
for(const auto& bodyA : m_bodies)
{
for(const auto& bodyB : m_bodies)
{
if(bodyA.get() != bodyB.get())
{
if(bodyA->m_boundingBox.intersects(bodyB->m_boundingBox))
{
m_collisions.insert(std::minmax(bodyA.get(), bodyB.get()));
}
}
}
}
//for each collision pair calculate manifold and resolve collision
for(const auto& pair : m_collisions)
{
auto manifold = getManifold(pair);
pair.second->resolve(manifold);
manifold.z -= manifold.z;
pair.first->resolve(manifold);
}
//apply gravity to each body and perform a physics step
for(auto& body : m_bodies)
{
body->applyGravity();
body->step(dt);
}
}
The update function is performed in to three main steps. First each body is tested against the others for intersection using its bounding box. If there is an intersection the pair of bodies are inserted into a std::set using std::minmax() which makes sure that each pair is inserted only once. Potentially this step could be optimised with some kind of spatial partitioning to make sure bodies are only tested against other nearby bodies, but for a small game it wasn't needed, and I omitted it for the sake of simplicity.
The second step is to calculate the collision manifold of each intersecting pair. The manifold contains a normalised vector perpendicular to the intersected surface, and a value stating the depth of intersection. This is usually the minimum it takes to resolve a collision between two objects - and in rectangular-only collision is vastly simplified by the fact that there can only be one of four possible normal vectors for each side of the rectangle, reducing the complexity of manifold calculation dramatically. In my calculation function I took advantage of the fact SFML's rectangle class returns the intersection area as a new rectangle, and you can see the full implementation here. Handily I could fit the two component normal vector along with the penetration depth into a single sf::Vector3, which made it an easy value to pass around. If you're interested in manifold generation for more complex interactions, there is an interesting article here which I found worth reading. The last step of the CollisionWorld update function applies a pre-defined gravity force to each body (the gravity value is passed to the CollisionWorld constructor), and executes each body's step() function.
Each body has two important functions, resolve() and step(). The resolve() function is used to decide how the body should react to the collision manifold data. As each body type needs to react slightly differently this is where behaviour customisation is applied. Each body has a currently active state defining its behaviour at that point in time. I took this idea from the state pattern (again from Game Programming Patterns), and created a BodyBehaviour class from which body type specialisations are inherited. This allows collisions to resolve themselves in specific ways, such as water being absorbent, or the ground being solid - as well as giving bodies the opportunity to raise body specific events. When a player body is destroyed then a PlayerDied event can be raised and so on. Physics values such as gravity and friction can also be intercepted by the active behaviour and modified if necessary, velocity vectors reflected about the manifold normal data or penetration values negated.
The body step() function then applies any changes made by the resolve() function by integrating the current time step with the body's velocity, and then moving the body. It also does some simple bounds checking and moves any bodies which may have tunneled out of the play area to a reasonable place at the top of the world. If the body is attached to a node in the scene graph then that node's position is then updated in the scene. Here is a video of the initial physics setup:
The red blocks are solid bodies, green are enemies, and blue is the player.
This is a very simplified overview of the collision system in Crush!, admittedly, but it's very difficult to go very far into detail in a single post. Crush! is open source, however, and the full collision code can be seen here.
struct CollisionBody
{
vector2 m_velocity;
vector2 m_position;
floatRect m_boundingBox;
}
Each frame the body's position is updated by adding the current velocity to it. The velocity is adjusted by either applying an external force (by adding another vector to the velocity), or as a result of a collision. Collision bodies exist within a CollisionWorld class, which is responsible for creating bodies, detecting collisions between them, and applying any resulting forces. The CollisionWorld class also acts as one of the controller classes, and so the instance lives alongside the other controllers in the GameState class. Apart from the factory functions of the CollisionWorld class, the beef of the code exists inside:
CollisionWorld::update(float dt)
{
//test which bodies intersect and mark as collision pair
m_collisions.clear();
for(const auto& bodyA : m_bodies)
{
for(const auto& bodyB : m_bodies)
{
if(bodyA.get() != bodyB.get())
{
if(bodyA->m_boundingBox.intersects(bodyB->m_boundingBox))
{
m_collisions.insert(std::minmax(bodyA.get(), bodyB.get()));
}
}
}
}
//for each collision pair calculate manifold and resolve collision
for(const auto& pair : m_collisions)
{
auto manifold = getManifold(pair);
pair.second->resolve(manifold);
manifold.z -= manifold.z;
pair.first->resolve(manifold);
}
//apply gravity to each body and perform a physics step
for(auto& body : m_bodies)
{
body->applyGravity();
body->step(dt);
}
}
The update function is performed in to three main steps. First each body is tested against the others for intersection using its bounding box. If there is an intersection the pair of bodies are inserted into a std::set using std::minmax() which makes sure that each pair is inserted only once. Potentially this step could be optimised with some kind of spatial partitioning to make sure bodies are only tested against other nearby bodies, but for a small game it wasn't needed, and I omitted it for the sake of simplicity.
The second step is to calculate the collision manifold of each intersecting pair. The manifold contains a normalised vector perpendicular to the intersected surface, and a value stating the depth of intersection. This is usually the minimum it takes to resolve a collision between two objects - and in rectangular-only collision is vastly simplified by the fact that there can only be one of four possible normal vectors for each side of the rectangle, reducing the complexity of manifold calculation dramatically. In my calculation function I took advantage of the fact SFML's rectangle class returns the intersection area as a new rectangle, and you can see the full implementation here. Handily I could fit the two component normal vector along with the penetration depth into a single sf::Vector3, which made it an easy value to pass around. If you're interested in manifold generation for more complex interactions, there is an interesting article here which I found worth reading. The last step of the CollisionWorld update function applies a pre-defined gravity force to each body (the gravity value is passed to the CollisionWorld constructor), and executes each body's step() function.
Each body has two important functions, resolve() and step(). The resolve() function is used to decide how the body should react to the collision manifold data. As each body type needs to react slightly differently this is where behaviour customisation is applied. Each body has a currently active state defining its behaviour at that point in time. I took this idea from the state pattern (again from Game Programming Patterns), and created a BodyBehaviour class from which body type specialisations are inherited. This allows collisions to resolve themselves in specific ways, such as water being absorbent, or the ground being solid - as well as giving bodies the opportunity to raise body specific events. When a player body is destroyed then a PlayerDied event can be raised and so on. Physics values such as gravity and friction can also be intercepted by the active behaviour and modified if necessary, velocity vectors reflected about the manifold normal data or penetration values negated.
The body step() function then applies any changes made by the resolve() function by integrating the current time step with the body's velocity, and then moving the body. It also does some simple bounds checking and moves any bodies which may have tunneled out of the play area to a reasonable place at the top of the world. If the body is attached to a node in the scene graph then that node's position is then updated in the scene. Here is a video of the initial physics setup:
The red blocks are solid bodies, green are enemies, and blue is the player.
This is a very simplified overview of the collision system in Crush!, admittedly, but it's very difficult to go very far into detail in a single post. Crush! is open source, however, and the full collision code can be seen here.
Comments
Post a Comment