After much work, I finally got PVS (Potential Visibility Set) culling working in the engine, so now I'm turning to game logic matters. I've been thinking about how best to manage game objects and the relationships between them. As one can imagine, it's not easy, but then again, what is?
In Game Challenge 18 (that 2D shooter thingy), my game object management was kind of hard to follow and disorganized. The game logic had two lists: one for players, one for all other game objects. Except not really. Any bullets spawned by firing weapons would get added there, but the weapons themselves were completely managed by the player (in fact, the game logic had no idea of their existence). So if you wanted to get the weapon or some info about it, you had to hunt down its owner. And you better hope the player properly manages the weapon's lifetime. I didn't have too many different kinds of game objects, but I imagine if I added more it would get even more convoluted.
So, this time around I decided to centralize things better. All game objects will be managed by the Scene class. This way, it's easy to get access to everything that needs updating or interacting with, and game objects aren't dependent on any particular class to call on their services. For example, weapons no longer need players to call Update() on them.
This does, however, bring up the problem of lifetime management and pointer validation. For example, let's say Player A was tracking Player B's health. Player A could store Player B's position in the game object list, and use it to call some function of Player B to get his health. Then Player B leaves the game. The game logic removes Player B from the list and frees his memory. That position in the list is then used to store another game object. What's going to happen when Player A tries to get Player B's health next frame? Unless you have something in place to counteract this problem, the answer is "who knows"?
One good way to solve this is through the use of handles. Instead of passing around game object pointers or positions in the list, give them handles instead. Now, if Player A wants to access Player B, he sends his request to the Scene class, passing in the handle. The Scene class will then be able to check if Player B still exists, and return NULL if he doesn't.
So I've made a structure that looks like this:
class ObjectHandle
{
unsigned long objectID;
unsigned long allocationID;
};
and a Scene method called GetGameObject(), which takes a handle and returns a game object pointer. The objectID is used as an index to the array. If there's no object there, it will be NULL at that location. Otherwise, there will be a valid game object at that location.
But what if the game object at that slot had been deleted, and the slot used to store another game object? You'd be getting a pointer to the wrong object! Here's where the allocationID variable comes in. When a game object gets added to the array, it gets a number that uniquely identifies that game object. If that object gets deleted and replaced with another one, it will have a different allocation ID assigned to it. Therefore, GetGameObject() will also compare the handle's allocation ID with that of the object in the slot. If they don't match, the original game object here has been replaced with another one, and NULL is returned to the caller.
The whole idea of centralizing game object management raises issues, however, when game objects' Update() functions are dependent on the results of other game objects' Update() functions. For example, imagine you had four soldiers riding in a vehicle, and they were all carrying weapons. You can't determine the position of the weapons until you know the position of the soldiers. And you can't do THAT until you know the position of the vehicle. If you do it in an arbitrary order, you may get the order (Weapon, Vehicle, Soldier), for example. With this order, the weapon would be updating based on data that's a frame old! The result would be the weapon's position lagging behind everything else by one frame. In order to get the proper behavior, we need (Vehicle, Soldier, Weapon). But how do we enforce this order?
One way to do it is to force update order at the Scene class level, based on type. The Scene will first call Update() on all the vehicles only, then all the soldiers only, then all the weapons only. This works for simpler games with only a few types of objects, but quickly gets very messy in more complex games. Why? Because now the Scene class not only needs to be aware of every type of game object, but iterate through each group separately! If you had 50 different kinds of game objects, your Scene would need 50 for loops just to update everything every frame! Not pretty.
An alternative (and more flexible) way is to sort objects into a small number of "buckets" (borrowing the term from a book called Game Engine Architecture). A bucket is essentially a list of game objects. The Scene::AddGameObject() function takes an optional parameter that specifies what bucket to add the object to. If you need to, you can later change the bucket with Scene::ChangeBucket(). Updating everything is simply a matter of iterating through each bucket and calling Update().
Why is this better than the type-based approach? Because the Scene class no longer needs to be aware of an object's type; it just blindly adds it to the bucket. You can get away with a small number of buckets, too (I'm starting with 5). The reason is that most objects aren't dependent on the updates of others. The weapon a player's holding isn't dependent on the rubber ducky another player is holding, so they can coexist in the same bucket. And I can't imagine an inter-object relationship more than 5 levels deep, can you? The disadvantage, however, is that game objects need to be aware of their position in inter-object relationships. If there's a weapon in the first bucket and a player picks it up, the player will need to explicitly move the weapon to the second bucket to preserve proper update order.
There's a lot more I want to say about how I'm doing game objects, but I'll close this post for now.
Wednesday, April 20, 2011
Friday, April 1, 2011
FPS Player Physics, Part 2
This continues the discussion of player physics from my last post.
So, as mentioned in my last post, we must handle ground polygons differently than wall and ceiling polygons. But how do we define ground polygons? One possible way is to specify which polygons/brushes are ground in whatever level editor you have, provided your editor supports it. This would be good if you can't clearly define rules of what is ground. It'd be a burden on your level designers, though, so avoid it if you can.
A much simpler way is to define ground polygons as any polygon tilted at an angle of X degrees or less from straight up (I tentatively chose X to be 45 degrees). If we consider the 2D case, it'd play out like the below diagram.
But how can we tell what angle a polygon is tilted at? Here's where the ever-useful dot product comes into play. We can dot product the polygon's normal and the vector (0, 1, 0), which is straight up. The dot product of any two vectors tells us the cosine of the angle between them, scaled by the length of the two vectors. So it looks like this:
A dot B = (cos theta)(length of A)(length of B)
Theta is the angle between the two vectors. However, the polygon's normal is by its very nature unit length (length = 1). And the length of (0, 1, 0) is obviously also 1. So when you're dot producting two unit length vectors, it simplifies down to this:
A dot B = cos theta
If both vectors face the same direction, the angle between them will be 0. So we substitute 0 for theta, and find:
A dot B = cos 0 = 1
For a polygon tilted 45 degrees, we substitute 45 for theta. The cosine of 45 is around 0.707. If you think about this, this means that we can see whether a polygon is considered to be ground by seeing whether its dot product is between 1 and 0.707 (or whatever the cosine of your chosen angle is).
float dotProduct = D3DXVec3Dot(&collisionNormal, D3DXVECTOR3(0, 1, 0));
if (dotProduct < 1.0f && dotProduct > 0.707f) bGroundPolygon = true;
else bGroundPolygon = false;
On a side note, there are some optimizations we can make to this. First off, we know that if our two vectors are unit length, the dot product will always be 1 or less, because cosine is never larger than 1. So that makes our first test unnecessary. Second, we don't need to do the full dot product. Why? Because the dot product is calculated like this:
A dot B = (A.x * B.x) + (A.y * B.y) + (A.z * B.z)
If we substitute (0, 1, 0) in for vector B, we get:
A dot B = (A.x * 0) + (A.y * 1) + (A.z * 0)
= 0 + A.y + 0
= A.y
So all we really need to do is test the Y component of the collision normal against 0.707. We end up with this code:
if (collisionNormal.y > 0.707f) bGroundPolygon = true;
else bGroundPolygon = false;
We've discussed in the last post that non-ground polygons should be handled through the slide response. How you handle ground polygons depends on the feel you're aiming for. For my project, I made a checklist of desired effects:
- The player should be able to stand on the ground without sliding down. Similarly, any movement along the ground polygon should not cause him to slide down.
- The player should be able to move up, down, and along the polygon at the same speed as if he were on flat ground. Jump height should also act the same.
- There should be no "bouncing effects" moving up or down the polygon.
In other words, ground polygons should act as if they were flat, except they also change the player's height. To address this, I considered the flat ground case, where the player is moving along flat ground and submits a velocity into the collision system. The collision normal would be (0, 1, 0), so if we apply the slide response, Y velocity (usually gravity) is nullified by the collision with the flat polygon, while XZ remains unaffected. The problem is that not all ground polygons will have that normal. If the X or Z components of the normal are anything other than 0, the player's XZ velocity will be affected by the slide response, which we don't want.
Therefore, we have to emulate flat ground behavior on non-flat ground polygons. To do this, we cannot use the slide response. Instead, I "move" the player along the full extent of their XZ velocity. I then cast a ray straight upwards and find where it intersects with the polygon's plane. I use this to calculate a new Y velocity for the player, such that the velocity's path no longer collides with the polygon, but moves parallel to it. The code looks like this:
// Get the player's XZ velocity
XZVelocity = velocity;
XZVelocity.y = 0;
// If you were to move by the XZ velocity, and then straight up, find where you would intersect // the plane. This is a simplified ray/plane intersection test
rayOrigin = intersectionPoint + XZVelocity;
numer = D3DXVec3Dot(&intersectionPoint, &-collisionNormal);
denom = collisionNormal.y;
// Our ray is (0, 1, 0), so we can just use the ray delta scalar as the Y value
newIntersectionPoint = rayOrigin;
newIntersectionPoint.y += numer / denom;
// Get our new velocity by subtracting the two intersection points
velocity = newIntersectionPoint - intersectionPoint;
I won't explain the specifics of the ray/plane test here, but you should be able to see what we're doing here. It's like we moved the player by his XZ velocity, then pushed him upward until he was no longer intersecting. The reason we don't just do that instead of changing the velocity is that there might be some other obstruction up there, and we might miss it if we change the player's position.
We've solved a number of problems with this method, and have narrowed the list down to:
- Jump height should act the same as if he were on flat ground.
- There should be no "bouncing effects" moving up or down the polygon.
The former problem is an easy fix. It's caused by the player's Y velocity being not equal to zero when moving up or down polygons. When the player jumps, a strong upward Y velocity is applied. Any currently existing Y velocity will increase or reduce the jump height, which I did not want. Therefore, after all collisions have been resolved, I set the player's Y velocity to 0 if they are on the ground (i.e. they collided with a ground polygon this frame).
The latter problem is tricker, because it's not exactly a problem of collision; it's a problem of no collision. To understand what I mean, imagine a player running down a slope:
What we notice is that the player is allowed to waltz right off the ground and into the air. The force of gravity isn't strong enough to keep him on the ground, so he stays in the air until gravity accumulates enough to pull him back down. The player's Y velocity is then set to 0 again, so the process starts again. The result is that the player more bounces down the slope than glides down. Worse, the player is considered to be off the ground, so he won't be able to jump.
But we can't adjust our collision response code, because there is no collision. Instead, we are forced to wait until after the collision phase. Then we can do a downward ray cast. Imagine taking the player's position and shooting a ray a short distance downwards. We then see if this ray intersects anything. If it does, we snap the player to it.
castOrigin = position;
castDelta = D3DXVECTOR3(0, -m_Ellipsoid.radius.y - 10.0f, 0);
if (pCollisionSystem->CastRay(castOrigin, castDelta, &intersectionInfo))
{
if (intersectionInfo.normal > 0.707f)
{
m_Position = intersectionInfo.intersectionPoint;
m_Position.y += 1e-3f + m_Ellipsoid.radius.y;
SetOnGround(true);
}
}
And that's the core of my collision response code. If you have any questions, comments, whatever, feel free to leave a comment.
So, as mentioned in my last post, we must handle ground polygons differently than wall and ceiling polygons. But how do we define ground polygons? One possible way is to specify which polygons/brushes are ground in whatever level editor you have, provided your editor supports it. This would be good if you can't clearly define rules of what is ground. It'd be a burden on your level designers, though, so avoid it if you can.
A much simpler way is to define ground polygons as any polygon tilted at an angle of X degrees or less from straight up (I tentatively chose X to be 45 degrees). If we consider the 2D case, it'd play out like the below diagram.
A dot B = (cos theta)(length of A)(length of B)
Theta is the angle between the two vectors. However, the polygon's normal is by its very nature unit length (length = 1). And the length of (0, 1, 0) is obviously also 1. So when you're dot producting two unit length vectors, it simplifies down to this:
A dot B = cos theta
If both vectors face the same direction, the angle between them will be 0. So we substitute 0 for theta, and find:
A dot B = cos 0 = 1
For a polygon tilted 45 degrees, we substitute 45 for theta. The cosine of 45 is around 0.707. If you think about this, this means that we can see whether a polygon is considered to be ground by seeing whether its dot product is between 1 and 0.707 (or whatever the cosine of your chosen angle is).
float dotProduct = D3DXVec3Dot(&collisionNormal, D3DXVECTOR3(0, 1, 0));
if (dotProduct < 1.0f && dotProduct > 0.707f) bGroundPolygon = true;
else bGroundPolygon = false;
On a side note, there are some optimizations we can make to this. First off, we know that if our two vectors are unit length, the dot product will always be 1 or less, because cosine is never larger than 1. So that makes our first test unnecessary. Second, we don't need to do the full dot product. Why? Because the dot product is calculated like this:
A dot B = (A.x * B.x) + (A.y * B.y) + (A.z * B.z)
If we substitute (0, 1, 0) in for vector B, we get:
A dot B = (A.x * 0) + (A.y * 1) + (A.z * 0)
= 0 + A.y + 0
= A.y
So all we really need to do is test the Y component of the collision normal against 0.707. We end up with this code:
if (collisionNormal.y > 0.707f) bGroundPolygon = true;
else bGroundPolygon = false;
We've discussed in the last post that non-ground polygons should be handled through the slide response. How you handle ground polygons depends on the feel you're aiming for. For my project, I made a checklist of desired effects:
- The player should be able to stand on the ground without sliding down. Similarly, any movement along the ground polygon should not cause him to slide down.
- The player should be able to move up, down, and along the polygon at the same speed as if he were on flat ground. Jump height should also act the same.
- There should be no "bouncing effects" moving up or down the polygon.
In other words, ground polygons should act as if they were flat, except they also change the player's height. To address this, I considered the flat ground case, where the player is moving along flat ground and submits a velocity into the collision system. The collision normal would be (0, 1, 0), so if we apply the slide response, Y velocity (usually gravity) is nullified by the collision with the flat polygon, while XZ remains unaffected. The problem is that not all ground polygons will have that normal. If the X or Z components of the normal are anything other than 0, the player's XZ velocity will be affected by the slide response, which we don't want.
// Get the player's XZ velocity
XZVelocity = velocity;
XZVelocity.y = 0;
// If you were to move by the XZ velocity, and then straight up, find where you would intersect // the plane. This is a simplified ray/plane intersection test
rayOrigin = intersectionPoint + XZVelocity;
numer = D3DXVec3Dot(&intersectionPoint, &-collisionNormal);
denom = collisionNormal.y;
// Our ray is (0, 1, 0), so we can just use the ray delta scalar as the Y value
newIntersectionPoint = rayOrigin;
newIntersectionPoint.y += numer / denom;
// Get our new velocity by subtracting the two intersection points
velocity = newIntersectionPoint - intersectionPoint;
I won't explain the specifics of the ray/plane test here, but you should be able to see what we're doing here. It's like we moved the player by his XZ velocity, then pushed him upward until he was no longer intersecting. The reason we don't just do that instead of changing the velocity is that there might be some other obstruction up there, and we might miss it if we change the player's position.
We've solved a number of problems with this method, and have narrowed the list down to:
- Jump height should act the same as if he were on flat ground.
- There should be no "bouncing effects" moving up or down the polygon.
The former problem is an easy fix. It's caused by the player's Y velocity being not equal to zero when moving up or down polygons. When the player jumps, a strong upward Y velocity is applied. Any currently existing Y velocity will increase or reduce the jump height, which I did not want. Therefore, after all collisions have been resolved, I set the player's Y velocity to 0 if they are on the ground (i.e. they collided with a ground polygon this frame).
The latter problem is tricker, because it's not exactly a problem of collision; it's a problem of no collision. To understand what I mean, imagine a player running down a slope:
But we can't adjust our collision response code, because there is no collision. Instead, we are forced to wait until after the collision phase. Then we can do a downward ray cast. Imagine taking the player's position and shooting a ray a short distance downwards. We then see if this ray intersects anything. If it does, we snap the player to it.
castOrigin = position;
castDelta = D3DXVECTOR3(0, -m_Ellipsoid.radius.y - 10.0f, 0);
if (pCollisionSystem->CastRay(castOrigin, castDelta, &intersectionInfo))
{
if (intersectionInfo.normal > 0.707f)
{
m_Position = intersectionInfo.intersectionPoint;
m_Position.y += 1e-3f + m_Ellipsoid.radius.y;
SetOnGround(true);
}
}
And that's the core of my collision response code. If you have any questions, comments, whatever, feel free to leave a comment.
Subscribe to:
Posts (Atom)