I can't really think of a particular topic to talk about with my engine here, so I'll just give you another progress update.
- Improved the netcode a lot. Not surprisingly, using only two computers to test netcode leaves a lot of bugs hidden. I gathered five of my friends to test out the game, and there were crashes and desync everywhere in a game that worked perfectly with only two people. I think I've worked those bugs out, but I won't be able to test that for a while.
- Animation! I've got an animation component in there now, and the player can play different animations on different parts of the body. Very useful for when you want to play a firing animation while running. Also, the player's torso now rotates based on how far they're looking up (previously, the whole mesh rotated).
- Rocket launcher! The mesh is incomplete at best, but it's there, and the rocket launcher itself is fully functional. The cool thing is that stuff like rocket jumping worked without any code explicitly for it.
- Visual effects! Head bob, camera shake, weapon bob, cool explosion effect!
- Other stuff I can't think of!
While it was depressing to see the netcode I was so proud of fall on its face with larger player counts, my friends still were having a lot of fun, despite the map being a test map and only a rocket launcher available. This is a good sign. Other than fixing bugs, of course, my next main goal is to get more weapons and some real maps in there. Then I can focus on improving the visuals. My engine could seriously use some lighting, and the player/weapon models I made, frankly, suck. So I still have a lot of work to do.
Wednesday, December 21, 2011
Thursday, October 6, 2011
Working with the 3DS Max SDK
I haven't had too much time to work on ProjectFPS specifically lately, due to work required by other projects. I did actually get around to writing a 3DS Max exporter for meshes and animations, however. I've taken the approach of writing the mesh data + vertex bone weights out to one file, with extension .msh, and skeleton data + animations out to another file, with extension .skl. 3DS Max, like a lot of 3D modeling programs, exports only one animation at a time, so I can't use the .skl file directly. Instead, I concatenate all animations for the skeleton into one, export that to .skl, and then put that file through an animation splitter I have to write, which will break it up into smaller animations and write it out to a separate file, which I will give extension .pfs. The mesh file, when loaded, will reference a .pfs skeleton that will be loaded along with it. This allows me to use different skins on the same skeleton, and to only have to do the animation splitting process once for every .skl file I create. Making assets isn't really my thing, so having a system like this is a big boon.
Now for a bit of a rant, if I may.
Once I figured it out (with a lot of help from video tutorials) 3DS Max itself was easy enough to use to create a rigged test mesh. The SDK, however, was much more painful to work with. It seemed like I had to grapple with it to get the data I needed. I guess, to an extent, that's unavoidable when working with a system that's written to support anything under the sun (the feature set, level of abstraction, and modularity is mind-bogglingly extensive). So it's natural that my needs are very specific, and represent only a small subset of what 3DS Max needs to do. However, considering how many games require writing an exporter (if you're writing your own asset pipeline, you HAVE to write an exporter for your modeler of choice), and the establishment of 3DS Max as an industry standard for game 3D modeling, I would expect more effort to be put into supporting developers who have to write them.
The main issue I had was lack of documentation. Yes, every function declaration was commented, but I would read the description for a function and still have no idea what it did. I punch some of the words I didn't understand into the documentation. Sometimes I'd get results, sometimes I'd just get reverted back to the C++ file-generated documentation. When I did get results, I often didn't understand what THAT page was talking about, either, or it didn't contain information relevant to my purposes. So I'm being lead on a wild goose chase all over the documentation just to find out what the heck that one function even did. My Google-fu also failed me in this regard, which puzzles me; you'd think that help would be all over the internet for something like this.
Then there were the gotchas and surprises. Surprises are never good when you're trying to work with an API. Often times I would write a function only to find that the API worked completely differently than I expected, and then I had to significantly rework my exporter to accommodate (I'm looking at you, keyframe exporting). Other times, it did things that I didn't expect with my data (I was stumped as to why my mesh, which consisted of two boxes, had so many faces and vertices until I found out it was converting my bones to triangle meshes too).
Then the random crashes and unexpected behavior. My program kept crashing whenever I tried to allocate memory, and crashed during random fwrite calls (which I later found allocate memory). The program cited heap corruption, but nothing else. Turns out the problem is that when building in Debug, you're using the debug C library while 3DS Max still uses the release version; these two allocate and free memory differently. The solution is to use a special Hybrid build, which uses the release library. The only reason I know that is because it was in a PDF found through some very lucky Google-fu, and that PDF was not written by Autodesk. For something as critical and hard to trace down as this, the SDK should have made this gotcha abundantly clear to me, but it didn't. Working with the Win32 interface in 3DS Max is also causing all sorts of problems for me, and to this day I have not been able to fix them. My money's on the existence of a similar gotcha. Sure, all the stuff in this and the previous paragraph make sense now, but to the programmer just getting familiar with the API, these kinds of things need to be properly explained.
The main saving grace I had in this was the two DevTV: Introduction to 3DS Max Programming videos. These videos walked you through the steps of creating a basic ASCII exporter. These were invaluable in the creation of my exporter, and I don't think I would have been able to do it without them. My final exporter design closely mimics the one in these videos. They walk you through step-by-step the extraction of the needed data, the concepts underlying the SDK, and any associated gotchas. The problems I had with coding my exporter started only once I wanted to do things the ASCII one didn't. I think the SDK's usability would benefit greatly from a larger pool of well-documented example plugins. XNA took this approach with its documentation, and it shows - it's very simple to figure out and adapt to your specific needs. The SDK's samples folder does contain a more comprehensive ASCII exporter than the one in the videos, but it's sparsely documented and hard to follow.
In short, the SDK is too hard to figure out for me to consider working extensively with it. I don't think the problem is due to bad design decisions or hack-and-slashed functionality; far from it. I simply feel that the developer is left hanging to figure things out on his own far too often.
Now for a bit of a rant, if I may.
Once I figured it out (with a lot of help from video tutorials) 3DS Max itself was easy enough to use to create a rigged test mesh. The SDK, however, was much more painful to work with. It seemed like I had to grapple with it to get the data I needed. I guess, to an extent, that's unavoidable when working with a system that's written to support anything under the sun (the feature set, level of abstraction, and modularity is mind-bogglingly extensive). So it's natural that my needs are very specific, and represent only a small subset of what 3DS Max needs to do. However, considering how many games require writing an exporter (if you're writing your own asset pipeline, you HAVE to write an exporter for your modeler of choice), and the establishment of 3DS Max as an industry standard for game 3D modeling, I would expect more effort to be put into supporting developers who have to write them.
The main issue I had was lack of documentation. Yes, every function declaration was commented, but I would read the description for a function and still have no idea what it did. I punch some of the words I didn't understand into the documentation. Sometimes I'd get results, sometimes I'd just get reverted back to the C++ file-generated documentation. When I did get results, I often didn't understand what THAT page was talking about, either, or it didn't contain information relevant to my purposes. So I'm being lead on a wild goose chase all over the documentation just to find out what the heck that one function even did. My Google-fu also failed me in this regard, which puzzles me; you'd think that help would be all over the internet for something like this.
Then there were the gotchas and surprises. Surprises are never good when you're trying to work with an API. Often times I would write a function only to find that the API worked completely differently than I expected, and then I had to significantly rework my exporter to accommodate (I'm looking at you, keyframe exporting). Other times, it did things that I didn't expect with my data (I was stumped as to why my mesh, which consisted of two boxes, had so many faces and vertices until I found out it was converting my bones to triangle meshes too).
Then the random crashes and unexpected behavior. My program kept crashing whenever I tried to allocate memory, and crashed during random fwrite calls (which I later found allocate memory). The program cited heap corruption, but nothing else. Turns out the problem is that when building in Debug, you're using the debug C library while 3DS Max still uses the release version; these two allocate and free memory differently. The solution is to use a special Hybrid build, which uses the release library. The only reason I know that is because it was in a PDF found through some very lucky Google-fu, and that PDF was not written by Autodesk. For something as critical and hard to trace down as this, the SDK should have made this gotcha abundantly clear to me, but it didn't. Working with the Win32 interface in 3DS Max is also causing all sorts of problems for me, and to this day I have not been able to fix them. My money's on the existence of a similar gotcha. Sure, all the stuff in this and the previous paragraph make sense now, but to the programmer just getting familiar with the API, these kinds of things need to be properly explained.
The main saving grace I had in this was the two DevTV: Introduction to 3DS Max Programming videos. These videos walked you through the steps of creating a basic ASCII exporter. These were invaluable in the creation of my exporter, and I don't think I would have been able to do it without them. My final exporter design closely mimics the one in these videos. They walk you through step-by-step the extraction of the needed data, the concepts underlying the SDK, and any associated gotchas. The problems I had with coding my exporter started only once I wanted to do things the ASCII one didn't. I think the SDK's usability would benefit greatly from a larger pool of well-documented example plugins. XNA took this approach with its documentation, and it shows - it's very simple to figure out and adapt to your specific needs. The SDK's samples folder does contain a more comprehensive ASCII exporter than the one in the videos, but it's sparsely documented and hard to follow.
In short, the SDK is too hard to figure out for me to consider working extensively with it. I don't think the problem is due to bad design decisions or hack-and-slashed functionality; far from it. I simply feel that the developer is left hanging to figure things out on his own far too often.
Wednesday, August 31, 2011
Getting game objects working over a network
First, a quick progress update on the project:
- I've got most of the game logic/high-level network code finished. There's still a kink or two I have to work out, and I need to implement a map rotation system, but everything that's needed for a good ol' deathmatch game is there. From here, it's mostly improving the look and feel of the game, and getting new weapons, maps, and stuff in.
- Still nothing in the way of animation, but I intend to change that soon.
- I've decided to give the game a wacky sort of theme. This achieves two goals. First, it makes the game fun to play for people of varying skill levels, one of my original goals in making this game. Second, it makes my game not "just another deathmatch shooter", and makes it different from all the Call of Duties, Halos, and Unreal Tournaments out there.
I'd like to describe my system for managing game object replication. In making any kind of network game, you'll need some way to instruct the client to create objects, destroy objects, and change the current state of objects. We also need to make sure that only certain game objects are replicated. For example, there's no need for the server to spawn little particle effects and replicate that to the client if it's not gameplay-critical. And the process of network replication should be as simple as possible. To solve all these problems, I created a component called NetRep (short for Network Replication).
Any object that can be replicated over the network will need a NetRep component. This component takes the current state of the object as input and produces what is called a "proxy" version of the object. A proxy is a stripped down version of the object, containing just enough information that the client can mimic the server's version. For example, when replicating a player, you can get away with just transmitting his position, velocity, look direction, health, current weapon, and a couple of state flags. That sounds like a lot, but this will be much smaller than the full blown Player! Since the client will only see these other players from the outside, you don't need to transmit everything.
If you add an object server-side to the Scene class, which I use for object management, it will check to see if the object has a NetRep component. If it does, it will automatically inform the server that this object needs to be replicated. The server will then tell the NetRep component to generate a GOCreateInfo structure. This is a superset of the proxy and contains additional information needed to recreate the object from scratch on the client, such as the object's class name. The server then sends all clients a MSG_CREATEOBJECT message, including the creation info. From then on, the server will continue to send clients a proxy of the object at regular intervals (I've found 50 ms to work well). Likewise, when the object is removed from the scene, a MSG_DELETEOBJECT message is sent to all clients.
NetRep contains a couple of default input fields, such as position, velocity, and health, but it also contains a user data field where you can specify your own custom state data. You can also set which input fields you're actually using, so if your object doesn't need its velocity replicated, you can leave it out of the proxy and reduce bandwidth usage.
Once the client receives a proxy of an object, it grabs the NetRep component of that object and calls ApplyProxy() on it. Depending on how it's configured, NetRep will then perform default proxy application, call a custom function specified by the object, or both.
This whole system allows objects to not have to worry about netcode (for the most part) when doing their stuff. For example, if my rocket launcher spawns a rocket, I don't need to keep track of the rocket or inform the server or anything. It's all done for me automatically. I just add it to the scene like it was a single-player game.
There is one aspect of netcode, however, that objects need to be aware of. They must be aware of which side of the network they exist on: server, client, or both (a listen server). This will affect their behavior. For example, firing a gun means very different things between client and server. Both will need to cast a ray, but the server will use it to determine damage, while the client is only concerned with sounds and pretty effects, like sparks and bullet holes. This is simply achieved by including a little field in the object that says which side of the network it's on. This field is set by Scene when the object is added to it.
- I've got most of the game logic/high-level network code finished. There's still a kink or two I have to work out, and I need to implement a map rotation system, but everything that's needed for a good ol' deathmatch game is there. From here, it's mostly improving the look and feel of the game, and getting new weapons, maps, and stuff in.
- Still nothing in the way of animation, but I intend to change that soon.
- I've decided to give the game a wacky sort of theme. This achieves two goals. First, it makes the game fun to play for people of varying skill levels, one of my original goals in making this game. Second, it makes my game not "just another deathmatch shooter", and makes it different from all the Call of Duties, Halos, and Unreal Tournaments out there.
I'd like to describe my system for managing game object replication. In making any kind of network game, you'll need some way to instruct the client to create objects, destroy objects, and change the current state of objects. We also need to make sure that only certain game objects are replicated. For example, there's no need for the server to spawn little particle effects and replicate that to the client if it's not gameplay-critical. And the process of network replication should be as simple as possible. To solve all these problems, I created a component called NetRep (short for Network Replication).
Any object that can be replicated over the network will need a NetRep component. This component takes the current state of the object as input and produces what is called a "proxy" version of the object. A proxy is a stripped down version of the object, containing just enough information that the client can mimic the server's version. For example, when replicating a player, you can get away with just transmitting his position, velocity, look direction, health, current weapon, and a couple of state flags. That sounds like a lot, but this will be much smaller than the full blown Player! Since the client will only see these other players from the outside, you don't need to transmit everything.
If you add an object server-side to the Scene class, which I use for object management, it will check to see if the object has a NetRep component. If it does, it will automatically inform the server that this object needs to be replicated. The server will then tell the NetRep component to generate a GOCreateInfo structure. This is a superset of the proxy and contains additional information needed to recreate the object from scratch on the client, such as the object's class name. The server then sends all clients a MSG_CREATEOBJECT message, including the creation info. From then on, the server will continue to send clients a proxy of the object at regular intervals (I've found 50 ms to work well). Likewise, when the object is removed from the scene, a MSG_DELETEOBJECT message is sent to all clients.
NetRep contains a couple of default input fields, such as position, velocity, and health, but it also contains a user data field where you can specify your own custom state data. You can also set which input fields you're actually using, so if your object doesn't need its velocity replicated, you can leave it out of the proxy and reduce bandwidth usage.
Once the client receives a proxy of an object, it grabs the NetRep component of that object and calls ApplyProxy() on it. Depending on how it's configured, NetRep will then perform default proxy application, call a custom function specified by the object, or both.
This whole system allows objects to not have to worry about netcode (for the most part) when doing their stuff. For example, if my rocket launcher spawns a rocket, I don't need to keep track of the rocket or inform the server or anything. It's all done for me automatically. I just add it to the scene like it was a single-player game.
There is one aspect of netcode, however, that objects need to be aware of. They must be aware of which side of the network they exist on: server, client, or both (a listen server). This will affect their behavior. For example, firing a gun means very different things between client and server. Both will need to cast a ray, but the server will use it to determine damage, while the client is only concerned with sounds and pretty effects, like sparks and bullet holes. This is simply achieved by including a little field in the object that says which side of the network it's on. This field is set by Scene when the object is added to it.
Tuesday, July 19, 2011
Wow, a month and a half since my last update. It hasn't been due to lack of work on the game, though.
I've been putting almost all of my effort into the code and almost none into the assets, so I still don't have much to show you. I can tell you where I currently am in the project, though
Up until recently, most of my work has been on a generalized engine that I can hopefully use for a variety of 3D games. Granted, it's not going to be the next Unreal engine, but most of the big stuff (object management, low-level network code, collision system, etc.) should be usable across a number of different games. At some point in the future, I'll have to see just how good a job I did. =P
Anyway, now I'm mostly working on stuff relating to a (still generalized) multiplayer FPS. This means network code, and a lot of it. My current goal is to get the game to be awesome over LAN, and at least decent over the Internet. The latter is actually the harder part, since now you have to deal with higher latencies and all sorts of bad connections. To that end, you have to put in a lot of code to smooth things out. The two big ones are interpolation and prediction.
Interpolation means smoothing out an object's transition between two states. There's not nearly enough bandwidth to send an object's state over the network every frame. Currently, I only send an object's state every 50 ms (that's 20 states per second). But if your game's running at 60 FPS, objects' movement will appear to be choppy. So you have to smooth it out. When a client receives an object's state, instead of immediately updating the object, it waits for the next state, then linearly moves between the two. Naturally, your code must also count on states never arriving, or arriving off-beat.
Prediction allows instant reaction to player input. You don't want to have to wait 200 ms after the player presses forward before they actually move forward. They want to move forward NOW. Prediction allows the player to see response to his actions before the server acknowledges it. This means that you're going to have times when the server and client disagree on what's happening. For example, the client may move forward normally when he presses forward, but the server comes up with a different figure because of that big ol' rocket that sent the player flying server-side. So you're going to need code that corrects prediction errors on the client based on states sent by the server. This correction code must also compensate for latency, since that will make the state the server sends reflect some point in the past.
So that and other high-level network stuff has been where most of my time has been going. I'm only now working on main game logic (like the rules of a Deathmatch game). This may seem like an awfully late point in the project to be implementing something like this, but it was necessary to achieve the kind of generalization I was looking for. What I mean by this is the separation (for the most part) of low-level network code, high-level network code, and game logic.
The low-level network code's only job is to send and receive messages, and maintain connections; it can therefore work with pretty much any game. The high-level network code's a little more specific - it contains code necessary to update the world of a multiplayer FPS. This means clients send their inputs to the server, and the server sends states to the clients here. Interpolation and prediction code also goes here. Finally, at the top we have game logic - code that (ideally) works only off the game state, and doesn't touch any network code. So if I wanted to add a CTF game type, I would only have to do three things: make a flag object, give players the ability to pick up flags, and make a new game logic module. None of that involves changing the network code. That's the ideal I'm shooting for.
Players can currently shoot and kill each other, and on the server side the score updates appropriately. I just have to replicate the changed score to clients, and add in some logic for ending the game, and I have a FPS deathmatch.
I've been putting almost all of my effort into the code and almost none into the assets, so I still don't have much to show you. I can tell you where I currently am in the project, though
Up until recently, most of my work has been on a generalized engine that I can hopefully use for a variety of 3D games. Granted, it's not going to be the next Unreal engine, but most of the big stuff (object management, low-level network code, collision system, etc.) should be usable across a number of different games. At some point in the future, I'll have to see just how good a job I did. =P
Anyway, now I'm mostly working on stuff relating to a (still generalized) multiplayer FPS. This means network code, and a lot of it. My current goal is to get the game to be awesome over LAN, and at least decent over the Internet. The latter is actually the harder part, since now you have to deal with higher latencies and all sorts of bad connections. To that end, you have to put in a lot of code to smooth things out. The two big ones are interpolation and prediction.
Interpolation means smoothing out an object's transition between two states. There's not nearly enough bandwidth to send an object's state over the network every frame. Currently, I only send an object's state every 50 ms (that's 20 states per second). But if your game's running at 60 FPS, objects' movement will appear to be choppy. So you have to smooth it out. When a client receives an object's state, instead of immediately updating the object, it waits for the next state, then linearly moves between the two. Naturally, your code must also count on states never arriving, or arriving off-beat.
Prediction allows instant reaction to player input. You don't want to have to wait 200 ms after the player presses forward before they actually move forward. They want to move forward NOW. Prediction allows the player to see response to his actions before the server acknowledges it. This means that you're going to have times when the server and client disagree on what's happening. For example, the client may move forward normally when he presses forward, but the server comes up with a different figure because of that big ol' rocket that sent the player flying server-side. So you're going to need code that corrects prediction errors on the client based on states sent by the server. This correction code must also compensate for latency, since that will make the state the server sends reflect some point in the past.
So that and other high-level network stuff has been where most of my time has been going. I'm only now working on main game logic (like the rules of a Deathmatch game). This may seem like an awfully late point in the project to be implementing something like this, but it was necessary to achieve the kind of generalization I was looking for. What I mean by this is the separation (for the most part) of low-level network code, high-level network code, and game logic.
The low-level network code's only job is to send and receive messages, and maintain connections; it can therefore work with pretty much any game. The high-level network code's a little more specific - it contains code necessary to update the world of a multiplayer FPS. This means clients send their inputs to the server, and the server sends states to the clients here. Interpolation and prediction code also goes here. Finally, at the top we have game logic - code that (ideally) works only off the game state, and doesn't touch any network code. So if I wanted to add a CTF game type, I would only have to do three things: make a flag object, give players the ability to pick up flags, and make a new game logic module. None of that involves changing the network code. That's the ideal I'm shooting for.
Players can currently shoot and kill each other, and on the server side the score updates appropriately. I just have to replicate the changed score to clients, and add in some logic for ending the game, and I have a FPS deathmatch.
Wednesday, June 1, 2011
Game Objects (Part 3)
So as mentioned, my laptop's hard drive remains broken and I haven't been able to get a new one yet. Fortunately, all the code for ProjectFPS remained perfectly intact, and I was able to get it off and continue where I left off.
My animation system has been put on hold for now. There are things I'd like to accomplish (such as more efficient resource memory usage, separation of skeletons and the meshes that skin them, and per-object callbacks) that just don't jive with the D3DX animation system, nor any X file exporters. In fact, the version of Blender I have doesn't even have an X file exporter, and when I threw in one written for an older version of Blender, meshes would not export correctly.
So I looked into the COLLADA format. I knew Blender had an exporter for it, and I had heard that 3D modeling programs like Maya and 3DSMax commonly used it to pass data from one program to another. I set out trying to use the OpenCOLLADA library to write a converter from COLLADA to a proprietary skeleton format and mesh format. It took me 2-3 days just to get the OpenCOLLADA part of the converter to compile and link, thanks to cryptic and nonsensical errors. Of course, when I tried using Visual Studio 2008 instead of 2010, these errors magically went away.
In my infinite wisdom, however, I had failed to do research on Blender's COLLADA exporter to see if it actually worked okay. Turns out it doesn't. My vertices had no weights on them at all (which you can't do skeletal animation without), and from what I've read on the web, animation export is kinda funky too. I could write my own Blender exporter, or fix the COLLADA one, or get a student version of 3DS Max. All these I either can't do right now or they require significant effort, and I felt that it just wasn't worth it yet, considering I still don't have much in terms of a game that people can play with each other.
So I've decided to work on something else: networking. You can have a multiplayer game without animation, but you can't have a multiplayer game without multiplayer. So far, I've got a server that multiple players can connect to. They can see each other and shoot the walls. As usual, a topic for another post. Now, back to game objects.
So as mentioned in the last post, the hierarchical model has its fair share of problems, mainly because of implication. If an object is able to do X, it is implied that it can also do Y and Z, which is often not the case, especially when you're defining new objects that weren't in the original design. What we need, then, is a way to precisely specify what objects can and can't do where the sheer variety of them defies hierarchical classification.
The key to doing this lies in converting what is called "is-a" relationships to "has-a" relationships. What this means is instead of saying Player is an AnimatedObject, you say he has a AnimationComponent. Thus, one could define a player like this instead:
class Player : public GameObject
{
void Update();
void Draw();
AnimationComponent m_Animation;
PhysicsComponent m_Physics;
NetworkReplicationComponent m_NetworkReplication;
// Other components, variables
};
Note that we inherit directly from GameObject and nothing else. That's because all the functionality we need has been put into these components, which act like plug-ins. We stick only necessary components into the object, and that gives it the functionality it needs, nothing more. So if we need a StatuePlayer class or something that can't animate, we do this:
class StatuePlayer : public GameObject
{
void Update();
void Draw();
PhysicsComponent m_Physics;
NetworkReplicationComponent m_NetworkReplication;
// Other components, variables
};
Nothing's changed, we're still inheriting from GameObject. We just omit the AnimationComponent. This system offers us a lot of convenience. Even two completely unrelated objects can have the same components, and thus do the same things. Building new objects is also easy, and thanks to the plug-in nature of components, code duplication becomes mostly unnecessary.
An object's updating might involve updating its components, changing their settings, etc., then acting off the results. So it would, for example, tell the animation component to update its current animation in Update(). Then, in Draw(), the object would grab the matrices generated by the component and use that to draw itself.
This doesn't mean that inheritance completely goes away, however. Like before, if we wanted to update everything in the scene, since they all still inherit from GameObject, we can have a list of GameObject pointers that we call Update() and Draw() on. And if you had, say, a WeaponInventory component, it could store a collection of Weapons, which all weapons would inherit from. Note, however, that this kind of inheritance is different - we're more working off what objects are, rather than what they can do. This kind of inheritance is typically very shallow.
Then there's the problem of inter-object relationships. Don't you hate that? The issue is that since implication is now gone, unless we have the object's specific type, we can't tell exactly what components it has. So you can't iterate over a collection of GameObjects and modify their physics, because not all of them will have it. There are multiple ways to tackle this problem, and some of them could be done at the same time.
One simple way is to put a query function in GameObject that all derived classes must overload. You give it a component name, and it either gives you back a component pointer or NULL. Simple, but slow, since the requested type must go through a switch statement or something to that effect every time. So to modify the physics of all relevant GameObjects, you might do this:
for (int i = 0; i < numObjects; i++)
{
PhysicsComponent* pPhysics = gameObjects[i].GetComponent(COMP_PHYSICS);
if (pPhysics) pPhysics->ChangeSomeSetting();
}
A more efficient but complex approach is to create lists of components for the more important component types. When a PhysicsComponent is created, then, it would register itself with the appropriate list. The code then becomes:
for (int i = 0; i < numPhysicsComps; i++)
{
physicsComps[i]->ChangeSomeSetting();
}
In my project, I use both approaches, depending on how much benefit I would get from the latter vs. the convenience of the former. Inter-component communication (e.g. between Physics and Transform) is a very similar problem, only now you have to be careful not to hurt the re-usability of the component in other kinds of objects.
And that's the basis of my game object design. Hopefully I didn't forget to say anything important. =P My next topic will probably be networking, since it has been the sole thing occupying my mind for weeks now. It also plays a big part in how you design your objects.
My animation system has been put on hold for now. There are things I'd like to accomplish (such as more efficient resource memory usage, separation of skeletons and the meshes that skin them, and per-object callbacks) that just don't jive with the D3DX animation system, nor any X file exporters. In fact, the version of Blender I have doesn't even have an X file exporter, and when I threw in one written for an older version of Blender, meshes would not export correctly.
So I looked into the COLLADA format. I knew Blender had an exporter for it, and I had heard that 3D modeling programs like Maya and 3DSMax commonly used it to pass data from one program to another. I set out trying to use the OpenCOLLADA library to write a converter from COLLADA to a proprietary skeleton format and mesh format. It took me 2-3 days just to get the OpenCOLLADA part of the converter to compile and link, thanks to cryptic and nonsensical errors. Of course, when I tried using Visual Studio 2008 instead of 2010, these errors magically went away.
In my infinite wisdom, however, I had failed to do research on Blender's COLLADA exporter to see if it actually worked okay. Turns out it doesn't. My vertices had no weights on them at all (which you can't do skeletal animation without), and from what I've read on the web, animation export is kinda funky too. I could write my own Blender exporter, or fix the COLLADA one, or get a student version of 3DS Max. All these I either can't do right now or they require significant effort, and I felt that it just wasn't worth it yet, considering I still don't have much in terms of a game that people can play with each other.
So I've decided to work on something else: networking. You can have a multiplayer game without animation, but you can't have a multiplayer game without multiplayer. So far, I've got a server that multiple players can connect to. They can see each other and shoot the walls. As usual, a topic for another post. Now, back to game objects.
So as mentioned in the last post, the hierarchical model has its fair share of problems, mainly because of implication. If an object is able to do X, it is implied that it can also do Y and Z, which is often not the case, especially when you're defining new objects that weren't in the original design. What we need, then, is a way to precisely specify what objects can and can't do where the sheer variety of them defies hierarchical classification.
The key to doing this lies in converting what is called "is-a" relationships to "has-a" relationships. What this means is instead of saying Player is an AnimatedObject, you say he has a AnimationComponent. Thus, one could define a player like this instead:
class Player : public GameObject
{
void Update();
void Draw();
AnimationComponent m_Animation;
PhysicsComponent m_Physics;
NetworkReplicationComponent m_NetworkReplication;
// Other components, variables
};
Note that we inherit directly from GameObject and nothing else. That's because all the functionality we need has been put into these components, which act like plug-ins. We stick only necessary components into the object, and that gives it the functionality it needs, nothing more. So if we need a StatuePlayer class or something that can't animate, we do this:
class StatuePlayer : public GameObject
{
void Update();
void Draw();
PhysicsComponent m_Physics;
NetworkReplicationComponent m_NetworkReplication;
// Other components, variables
};
Nothing's changed, we're still inheriting from GameObject. We just omit the AnimationComponent. This system offers us a lot of convenience. Even two completely unrelated objects can have the same components, and thus do the same things. Building new objects is also easy, and thanks to the plug-in nature of components, code duplication becomes mostly unnecessary.
An object's updating might involve updating its components, changing their settings, etc., then acting off the results. So it would, for example, tell the animation component to update its current animation in Update(). Then, in Draw(), the object would grab the matrices generated by the component and use that to draw itself.
This doesn't mean that inheritance completely goes away, however. Like before, if we wanted to update everything in the scene, since they all still inherit from GameObject, we can have a list of GameObject pointers that we call Update() and Draw() on. And if you had, say, a WeaponInventory component, it could store a collection of Weapons, which all weapons would inherit from. Note, however, that this kind of inheritance is different - we're more working off what objects are, rather than what they can do. This kind of inheritance is typically very shallow.
Then there's the problem of inter-object relationships. Don't you hate that? The issue is that since implication is now gone, unless we have the object's specific type, we can't tell exactly what components it has. So you can't iterate over a collection of GameObjects and modify their physics, because not all of them will have it. There are multiple ways to tackle this problem, and some of them could be done at the same time.
One simple way is to put a query function in GameObject that all derived classes must overload. You give it a component name, and it either gives you back a component pointer or NULL. Simple, but slow, since the requested type must go through a switch statement or something to that effect every time. So to modify the physics of all relevant GameObjects, you might do this:
for (int i = 0; i < numObjects; i++)
{
PhysicsComponent* pPhysics = gameObjects[i].GetComponent(COMP_PHYSICS);
if (pPhysics) pPhysics->ChangeSomeSetting();
}
A more efficient but complex approach is to create lists of components for the more important component types. When a PhysicsComponent is created, then, it would register itself with the appropriate list. The code then becomes:
for (int i = 0; i < numPhysicsComps; i++)
{
physicsComps[i]->ChangeSomeSetting();
}
In my project, I use both approaches, depending on how much benefit I would get from the latter vs. the convenience of the former. Inter-component communication (e.g. between Physics and Transform) is a very similar problem, only now you have to be careful not to hurt the re-usability of the component in other kinds of objects.
And that's the basis of my game object design. Hopefully I didn't forget to say anything important. =P My next topic will probably be networking, since it has been the sole thing occupying my mind for weeks now. It also plays a big part in how you design your objects.
Wednesday, May 11, 2011
Game objects, Part 2
Hardy Drivey sat on a desk.
Hardy Drivey had a big fall.
All the king's restarts and all the king's shouts
Couldn't put Hardy back together again.
So yeah, Floor 1, Laptop Hard Drive 0. Fortunately, it seems that all the updates I made to the code since my last SVN commit are intact. Specifically (among bugfixes), I had added sound to the engine. I had a surprisingly simple time with it, I thought adding sound would be a lot more complicated. No 3D positioning or anything yet, but from what I read in the documentation, that's not too hard either.
I had also started to work on animation, but I've sort of hit a brick wall due to lack of assets to test with. I don't have 3DS Max, and maybe I just suck with Blender, but the last time I tried to use it, I couldn't get anything to work correctly. The mesh would have holes in it only when exported, making a skeleton gave me trouble, etc... you can tell I'm not very good at this whole "asset" thing. I'll write about my plans with the animation system once I can get some stuff going there.
Anyway, I wanted to continue my discussion of game object basics. That problem I mentioned at the end of my last post about objects needing to know their position in a relationship isn't a big deal at all. I decided to add the object's scene handle, its object ID, and its bucket ID to GameObject's member variables. That lets me quickly figure out what bucket the child object is in and whether a bucket change is necessary. If it is, I tell Scene to change the child object's bucket, and Scene informs the child object of this change so it can move its children down too, and so on. Getting object handles where needed is also a lot simpler this way.
Now to move on to the structure of the game objects. The old way of doing it is through a inheritance hierarchy that's "hueg liek xbox". You start from very basic base classes and work your way up. So a player class's position in the hierarchy may look like this:
GameObject->MovableObject->RenderableObject->AnimatedObject->ControllableObject->Player
As one can guess, as we move down the hierarchy we gain more and more functionality, to the point that when we get to Player, we just have to implement player-specific stuff. Here we are saying that Player is controllable, and thus animated, and thus renderable, and thus movable. An enemy would work similarly:
GameObject->MovableObject->RenderableObject->AnimatedObject->Enemy
Like Player, Enemy inherits all this functionality without having to do anything. Since an Enemy is not controllable, we don't inherit from ControllableObject.
Obviously, polymorphism works wonders here. You also have the assurance that if an object is of type AnimatedObject, it is guaranteed that it is also movable and renderable. So what's the problem with this?
Imagine that you had laid out all the types of game objects you were going to need and came up with a hierarchy like the one above. You work on the project and get, say, 70% done. Your team's game designer comes busting through the door in his usual overdramatic style, and entrusts upon you a simple task: make a ControlCrate class for a crate that can be moved with the arrow keys. We know that crates do not need animation, but obviously it needs to be controllable. Now to just put that in the hierarchy... uh oh. Where do we put it?
In our hierarchy, ControllableObject inherits from AnimatedObject. If we want our crate to be controllable, we should inherit from ControllableObject, but that would mean we'd get animation stuff too, which we don't want. We gotta change our hierarchy around somehow. We could move ControllableObject back and get this:
GameObject->MovableObject->RenderableObject->ControllableObject->AnimatedObject
This seems to solve our problem, until we realize that now all animated objects are considered to be also controllable. In all likelihood, this is not true. A second option is to branch off from RenderableObject, so we'd get this:
GameObject->MovableObject->RenderableObject->AnimatedObject->ControllableObject
| ->NoAnimControllable->ControlCrate
So now we have two classes that inherit from RenderableObject, one that's animated and one that's not. Great, but now we have to copy a whole boatload of code from ControllableObject into NoAnimControllable. If you later change something in ControllableObject, I hope you remember to change it in NoAnimControllable too (spoiler: you probably won't). A third option is to just say "screw it" and let ControlCrate inherit from AnimatedObject too:
GameObject->MovableObject->RenderableObject->AnimatedObject->ControllableObject->ControlCrate
Just don't use the animation functions, and all is well, yes? Well, no. Cause now you've got animation-related variables taking up memory for a class that will never use them. This is what's referred to as the "blob effect". You get blob classes that can do everything, but never actually do everything. And what if your fellow coder Steve is working with this crate, sees that it inherits from AnimatedObject, and tries to animate it? Yeah, leave it to Steve to ruin everything.
Even if you're some kind of hierarchy ninja and get everything to work, keep in mind we may have hundreds of other game objects in that hierarchy. You're going to have to make sure every last one of them jives with your new way of doing things. And doing so will probably involve a LOT of code rewriting.
The alternative to hierarchies that I chose to use when defining game objects is that of a component-based system. I'll write more about this in my next post.
Hardy Drivey had a big fall.
All the king's restarts and all the king's shouts
Couldn't put Hardy back together again.
So yeah, Floor 1, Laptop Hard Drive 0. Fortunately, it seems that all the updates I made to the code since my last SVN commit are intact. Specifically (among bugfixes), I had added sound to the engine. I had a surprisingly simple time with it, I thought adding sound would be a lot more complicated. No 3D positioning or anything yet, but from what I read in the documentation, that's not too hard either.
I had also started to work on animation, but I've sort of hit a brick wall due to lack of assets to test with. I don't have 3DS Max, and maybe I just suck with Blender, but the last time I tried to use it, I couldn't get anything to work correctly. The mesh would have holes in it only when exported, making a skeleton gave me trouble, etc... you can tell I'm not very good at this whole "asset" thing. I'll write about my plans with the animation system once I can get some stuff going there.
Anyway, I wanted to continue my discussion of game object basics. That problem I mentioned at the end of my last post about objects needing to know their position in a relationship isn't a big deal at all. I decided to add the object's scene handle, its object ID, and its bucket ID to GameObject's member variables. That lets me quickly figure out what bucket the child object is in and whether a bucket change is necessary. If it is, I tell Scene to change the child object's bucket, and Scene informs the child object of this change so it can move its children down too, and so on. Getting object handles where needed is also a lot simpler this way.
Now to move on to the structure of the game objects. The old way of doing it is through a inheritance hierarchy that's "hueg liek xbox". You start from very basic base classes and work your way up. So a player class's position in the hierarchy may look like this:
GameObject->MovableObject->RenderableObject->AnimatedObject->ControllableObject->Player
As one can guess, as we move down the hierarchy we gain more and more functionality, to the point that when we get to Player, we just have to implement player-specific stuff. Here we are saying that Player is controllable, and thus animated, and thus renderable, and thus movable. An enemy would work similarly:
GameObject->MovableObject->RenderableObject->AnimatedObject->Enemy
Like Player, Enemy inherits all this functionality without having to do anything. Since an Enemy is not controllable, we don't inherit from ControllableObject.
Obviously, polymorphism works wonders here. You also have the assurance that if an object is of type AnimatedObject, it is guaranteed that it is also movable and renderable. So what's the problem with this?
Imagine that you had laid out all the types of game objects you were going to need and came up with a hierarchy like the one above. You work on the project and get, say, 70% done. Your team's game designer comes busting through the door in his usual overdramatic style, and entrusts upon you a simple task: make a ControlCrate class for a crate that can be moved with the arrow keys. We know that crates do not need animation, but obviously it needs to be controllable. Now to just put that in the hierarchy... uh oh. Where do we put it?
In our hierarchy, ControllableObject inherits from AnimatedObject. If we want our crate to be controllable, we should inherit from ControllableObject, but that would mean we'd get animation stuff too, which we don't want. We gotta change our hierarchy around somehow. We could move ControllableObject back and get this:
GameObject->MovableObject->RenderableObject->ControllableObject->AnimatedObject
This seems to solve our problem, until we realize that now all animated objects are considered to be also controllable. In all likelihood, this is not true. A second option is to branch off from RenderableObject, so we'd get this:
GameObject->MovableObject->RenderableObject->AnimatedObject->ControllableObject
| ->NoAnimControllable->ControlCrate
So now we have two classes that inherit from RenderableObject, one that's animated and one that's not. Great, but now we have to copy a whole boatload of code from ControllableObject into NoAnimControllable. If you later change something in ControllableObject, I hope you remember to change it in NoAnimControllable too (spoiler: you probably won't). A third option is to just say "screw it" and let ControlCrate inherit from AnimatedObject too:
GameObject->MovableObject->RenderableObject->AnimatedObject->ControllableObject->ControlCrate
Just don't use the animation functions, and all is well, yes? Well, no. Cause now you've got animation-related variables taking up memory for a class that will never use them. This is what's referred to as the "blob effect". You get blob classes that can do everything, but never actually do everything. And what if your fellow coder Steve is working with this crate, sees that it inherits from AnimatedObject, and tries to animate it? Yeah, leave it to Steve to ruin everything.
Even if you're some kind of hierarchy ninja and get everything to work, keep in mind we may have hundreds of other game objects in that hierarchy. You're going to have to make sure every last one of them jives with your new way of doing things. And doing so will probably involve a LOT of code rewriting.
The alternative to hierarchies that I chose to use when defining game objects is that of a component-based system. I'll write more about this in my next post.
Wednesday, April 20, 2011
Bucket-based object management
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.
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.
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.
Friday, March 25, 2011
FPS Player Physics
Physics, and in particular player physics, can make or break a game; the "feel" of the game is obviously directly tied to it. So I guess it's not unreasonable for one to spend weeks trying to get it to work "just right". Still... ugh.
There are two big considerations to make with physics: collision detection and collision response. Both gave me a lot of headaches, but here I'll just talk about the response. When dealing with player physics, the most common type of collision response is the sliding response. Boot up your favorite FPS and head straight for the nearest wall. You'll notice that as you hit the wall, you start to move along it. The more of an angle you approach the wall at, the faster you slide. To visualize this, imagine this picture is a top-down view of some game (velocities are not to scale).
You can see that the player approaches the wall on a diagonal, and once the wall is hit, the attempted velocity is adjusted to point right.
The awesome thing about it is that it's a very one-size-fits-almost-all response method. You can collide at any wall at any angle at any velocity and it will properly slide you without any special case code. It also works for hitting corners and ramps - again, without any special case code.
To explain this from a technical point of view, the slide is achieved by projecting the player's velocity from its original direction into one perpendicular with the wall. This is done using a collision normal, which your collision system should return as part of the collision information. A normal is a vector that essentially describes an orientation. In this case, a collision normal will describe which way the wall is facing. In this example, the wall is facing down (from our top-down view). Thus, the normal also faces down. To project the velocity, we do a dot product between the attempted velocity and the collision normal. This will tell us how far into the wall we would have penetrated. You then simply "push" the velocity out of the wall, along the collision normal, by this amount. You'll notice that if you take the attempted velocity in the above picture and push it out of the wall, the resulting direction is that of "Adjusted Velocity". The code would look like this:
// Project the velocity onto the wall's plane
distanceToPlane = D3DXVec3Dot(&velocity, &collisionNormal);
velocity -= (distanceToPlane * collisionNormal);
It's really that simple. If you work with the math you'll notice that as the angle you hit the wall changes (and thus, the direction of your velocity), the amount of velocity lost as a result of the collision also changes. If you hit a wall straight on, there'll be practically nothing left. If you're constantly applying gravity, this response type has the added bonus of making sure the player can't climb up slopes that are too steep. They'll go as far as their velocity takes them, then slide back down to the bottom.
You may have noticed that I said "one-size-fits-almost-all". That is because there are some unwanted side effects of this response type, almost all related to the handling of ground. As I said, applying gravity will make the player slide down steep slopes. It will also, however, make the player slide down shallow ones too, ones that they should normally be able to stand on. Unless your players are on rollerskates or something, this is probably not what you want. A second side effect is that you will go up shallow slopes slower than if you were on flat ground. This may be desirable, but in my particular case, it was not.
A third problem isn't particularly related to slide response, but is still critical to note. If you were standing on a ground slope and started moving down it, you probably want the player to smoothly glide down the slope. Instead, what happens is that you move forward into the air, and no collisions are detected until gravity catches up and makes you hit the slope. The next frame, you're back in the air again, as the force of gravity was reset upon collision. The result is that the player more bounces down shallow slopes than glides down them. Of course, this will feel awkward to the player, but it will also cause your player to be considered off the ground, and render him unable to jump.
Solving these problems is more complicated, and requires special-case code. Thus, the result is that you have one type of collision response for the ground, and slide response for everything else. The former is what was giving me the headaches. In a future post, I'll talk about some of the ways you can detect and handle ground collisions.
There are two big considerations to make with physics: collision detection and collision response. Both gave me a lot of headaches, but here I'll just talk about the response. When dealing with player physics, the most common type of collision response is the sliding response. Boot up your favorite FPS and head straight for the nearest wall. You'll notice that as you hit the wall, you start to move along it. The more of an angle you approach the wall at, the faster you slide. To visualize this, imagine this picture is a top-down view of some game (velocities are not to scale).
You can see that the player approaches the wall on a diagonal, and once the wall is hit, the attempted velocity is adjusted to point right.
The awesome thing about it is that it's a very one-size-fits-almost-all response method. You can collide at any wall at any angle at any velocity and it will properly slide you without any special case code. It also works for hitting corners and ramps - again, without any special case code.
To explain this from a technical point of view, the slide is achieved by projecting the player's velocity from its original direction into one perpendicular with the wall. This is done using a collision normal, which your collision system should return as part of the collision information. A normal is a vector that essentially describes an orientation. In this case, a collision normal will describe which way the wall is facing. In this example, the wall is facing down (from our top-down view). Thus, the normal also faces down. To project the velocity, we do a dot product between the attempted velocity and the collision normal. This will tell us how far into the wall we would have penetrated. You then simply "push" the velocity out of the wall, along the collision normal, by this amount. You'll notice that if you take the attempted velocity in the above picture and push it out of the wall, the resulting direction is that of "Adjusted Velocity". The code would look like this:
// Project the velocity onto the wall's plane
distanceToPlane = D3DXVec3Dot(&velocity, &collisionNormal);
velocity -= (distanceToPlane * collisionNormal);
It's really that simple. If you work with the math you'll notice that as the angle you hit the wall changes (and thus, the direction of your velocity), the amount of velocity lost as a result of the collision also changes. If you hit a wall straight on, there'll be practically nothing left. If you're constantly applying gravity, this response type has the added bonus of making sure the player can't climb up slopes that are too steep. They'll go as far as their velocity takes them, then slide back down to the bottom.
You may have noticed that I said "one-size-fits-almost-all". That is because there are some unwanted side effects of this response type, almost all related to the handling of ground. As I said, applying gravity will make the player slide down steep slopes. It will also, however, make the player slide down shallow ones too, ones that they should normally be able to stand on. Unless your players are on rollerskates or something, this is probably not what you want. A second side effect is that you will go up shallow slopes slower than if you were on flat ground. This may be desirable, but in my particular case, it was not.
A third problem isn't particularly related to slide response, but is still critical to note. If you were standing on a ground slope and started moving down it, you probably want the player to smoothly glide down the slope. Instead, what happens is that you move forward into the air, and no collisions are detected until gravity catches up and makes you hit the slope. The next frame, you're back in the air again, as the force of gravity was reset upon collision. The result is that the player more bounces down shallow slopes than glides down them. Of course, this will feel awkward to the player, but it will also cause your player to be considered off the ground, and render him unable to jump.
Solving these problems is more complicated, and requires special-case code. Thus, the result is that you have one type of collision response for the ground, and slide response for everything else. The former is what was giving me the headaches. In a future post, I'll talk about some of the ways you can detect and handle ground collisions.
Thursday, March 24, 2011
Welcome
This blog will be where I talk about my progress in game development, as well as any thoughts I have on game dev in general. At the time of writing this post, I currently have three projects under my belt and am working on a fourth.
My first project was an engine for top-down RPGs. This project never saw completion, but a lot of work went into it, and being my first foray into game programming, I learned volumes.
I'd like to show you a screenshot of a more complex level, but I don't know yet if I'm allowed to post screenshots of Game Institute levels. Joshua Allen, a friend of mine, will be making some levels of our own, and now that I've fixed player physics (more on that in another post) we should be able to move swiftly forward. I'll talk more about what I've got done so far in future posts.
My first project was an engine for top-down RPGs. This project never saw completion, but a lot of work went into it, and being my first foray into game programming, I learned volumes.
My next two projects were entries to a recurring contest called Game Challenges, on the Game Institute forums (I take online classes there). The first challenge was sound/music themed, so I made a game called Beat Down where you beat The Bad Guys up to music.
The second challenge required a multiplayer component, so I made a split-screen deathmatch shooter. This project was technically more ambitious than the previous two, as I tried to make the engine much more flexible. Perhaps too much so, as I ended up running out of time and having to rush a lot of things. Still, I'm proud of it.
My current project (tentatively called ProjectFPS) is my first real foray into 3D game development. It's starting off as another deathmatch shooter, but I intend to eventually make the engine flexible enough to support more unique gameplay. I've got a lot to say about this project in particular, so keep your eyes open for that.
Subscribe to:
Posts (Atom)