tag:blogger.com,1999:blog-61843833195500357532024-03-27T23:29:30.452-06:00Game Programming and DevelopmentA blog by a professional game developer, about game programming and development.
My posts will range in comments from beginners to game development to those at a more advanced level.Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.comBlogger53125tag:blogger.com,1999:blog-6184383319550035753.post-29963727529785044082013-04-05T17:36:00.002-06:002013-04-05T22:55:17.652-06:00Setting up a game update loop in-sync with renderingOne thing that just about every game ends up needing is a way to update the game in-step with the devices v-sync. Some games even take it a step further and update their rendering system separate from their game world, so the game world and rendering can update independently. For now we'll keep it simple and just talk about setting up an update loop that remains in-sync with rendering.<br />
<br />
First, you want to keep your frame updates within reasonable limits, relative to the device's refresh rate. And like V-sync, you also only want to update with time changes that are multiples of the refresh rate. First we'll set up a few variables to hold some of that data.<br />
<pre class="brush: cpp">static const float s_device_refresh = 60.f;
static const float s_device_quarter_refresh = s_device_refresh / 4.f;
static const float s_min_framerate = s_device_quarter_refresh;
static const float s_max_frametime = 1 / s_min_framerate;
static const float s_target_framerate = s_device_refresh;
static const float s_min_frametime = 1 / s_target_framerate;
</pre>
<br />
Note that I'm not actually reading in the device's refresh rates in this post, I'm assuming a refresh rate of 60 fps. In real-world use you'll need to grab the refresh rate from the device and store it for use. And we will just use a quarter of the refresh rate as the minimum update rate that we'll accept, which is 15 fps in this example.<br />
<br />
And we'll create a couple of variables to hold how much time since we last allowed the game to update, and the total time elapsed since the program started.<br />
<pre class="brush: cpp">static float s_time_buffer = 0.f;
static float s_actual_time_elapsed = 0.f;
</pre>
<br />
Let's setup a simulated update function. The update function is the one you would end up calling whenever we calculate that it will line up with the device's refresh. All we do in this example is show how much time the update method would be given to update the game, how much actual time has passed since the program started, and what frame the device would be on by this point.<br />
<pre class="brush: cpp">void update(const float time_delta, const float game_time)
{
std::cout << "Update, time_delta: " << time_delta << ", total time: " << game_time << ", frame #: "
<< static_cast<int>(game_time / (1 / s_device_refresh)) << std::endl << std::endl;
}
</pre>
Now, for the bread and butter, we need a method that processes how much time has elapsed since the OS last let our program update, and can take that time and figure out if we need an update, and how much time that update should be allowed to simulate. <br />
<pre class="brush: cpp">void process_update_needed(const float time_delta)
{
s_time_buffer += time_delta;
s_actual_time_elapsed += time_delta;
std::cout << "Processing update, time_delta: " << time_delta << ", time accumulated: " << s_time_buffer << std::endl;
float time_this_update = 0.f;
while ( s_time_buffer >= s_min_frametime )
{
s_time_buffer -= s_min_frametime;
time_this_update += s_min_frametime;
}
while ( time_this_update > 0.f )
{
if ( time_this_update >= s_max_frametime )
{
time_this_update -= s_max_frametime;
update(s_max_frametime, s_actual_time_elapsed);
}
else
{
update(time_this_update, s_actual_time_elapsed);
time_this_update = 0.f;
}
}
}
</pre>
We update s_time_buffer, which holds how much time we have stored up. Here we're also keeping track of the total time elapsed (s_actual_time_elapsed). We create a float to store how much time we're going to send to our 'update' function. Now, what the condition for the while loop is doing is, if the amount of time we've accumulated is greater than or equal to 1/60th of a second (since we're assuming 60 fps) then we remove 1/60th of a second from the time buffer and add it to the amount of time we'll be sending to the update method. The next while loop, if there is any time to be send to the update method, will check to see if the amount of time we're sending to the update method is greater than the maximum frame time. If the time is greater than the maximum frame time, then we just send the maximum frame time for this update and then we subtract that amount from the time remaining to be sent to update. Once the time remaining is less than the maximum frame time then we just send the rest. <br />
<br />
<br />
<b>There are a couple of major considerations to make when updating your game:</b><br />
<ol>
<li>Do you want predictable time slices for every receiver of update calls?</li>
<li>If your update calls are expensive, do you really want to call them more than once per frame? (This can lead to a well-of-despair problem, which we'll talk about later as well)</li>
</ol>
The example above will split of the time into slices that are multiples of the refresh rate, and call update for every slice. This ensures that receivers of the update method get time slices that are always multiples of the refresh rate, never less than the refresh rate, and never greater than the max time amount that you've defined. Why is having a multiple of the refresh rate important? If you're moving anything on the screen, it will look smoothest if it moves at the same rate at all times.<br />
<br />
<h4>
Why a timestep that is a multiple of the screen refresh rate?</h4>
Let's imagine a dot moving across the screen, we'll just talk about it's X position, assuming 0 is the left side of the screen, and 100 is the right side of the screen. The dot moves at 100 units per second, so it should cross the screen in 1 second. Now lets look at the numbers, comparing time elapsed with the times that the screen has actually rendered. <br />
<pre class="brush: cpp">---------------------------------------------------------------------------------
Time (ms) | Frame (60fps) | Dot pos (actual time) | Dot pos (refresh times) |
----------+---------------+-------------------------+---------------------------|
0 | 0 | 0 | 0 |
10 | 0 | 1 | 0 |
21 | 1 | 2.1 | 1.67 |
33.3 | 2 | 3.33 | 3.33 |
43 | 2 | 4.3 | 3.33 |
54 | 3 | 5.4 | 5.0 |
66.6 | 4 | 6.66 | 6.66 |
---------------------------------------------------------------------------------
</pre>
<br />
In the above table you can see what kind of results we get if don't use fixed time steps that are multiples of the refresh rate. The numbers on the left represent non-fixed times that would be passed to your update method. The second column shows you what frame the game would be on at those times. The third column shows the X position where you would be rendering the dot on the screen on that frame, and the fourth column shows where you actually want to be rendering the dot on the screen if you the smooth constant speed the player is expecting to see. So, if you want to get rid of the visual jitteriness, the key is to update only one frames that you'll be rendering on, and to update at a rate that matches the last time that you rendered. The big caveat with this is that you need to make sure that the time your frames are taking to process is fairly consistent. If you wait until a specific time so that you can update in-sync with the monitor refresh rate and then your update takes much longer than average, your update will actually push back the render to the next frame, and you'll end up with jitteriness anyway. So one of your end goals for your game should be a fairly consistent framerate.<br />
<br />
<h4>
Avoid the well-of-despair problem</h4>
The well-of-despair problem is when your time accumulates, and requires more fixed timestep updates to get rid of. The extra update calls end up increasing the amount of time your frame takes, which in turn makes your time accumulate to larger values. And thus the cycle continues until your framerate is hosed completely.<br />
<br />
There are a couple of ways to get around the problem, both have their own issues though.<br />
<br />
<b>Option 1.) Lie about time</b><br />
If the accumulated time exceeds a certain threshold then you can just send the update method a certain maximum value. This will result in your game moving in slow-motion. I'm sure you've seen this in certain games in the past, at times when a lot is going on and the device can't keep up. That is why that happens in those games. Here's an updated 'process_update_needed' function that handles the well-of-despair problem by lying about time. If our 'time_this_update' was 0.12f, and our s_max_time_threshold is 0.1f, then we'll be updating only 0.1f, causing the game to visually slow down by about 18%.<br />
<pre class="brush: cpp">static const float s_max_time_threshold = s_device_refresh / 6.f;
void process_update_needed(const float time_delta)
{
s_time_buffer += time_delta;
s_actual_time_elapsed += time_delta;
std::cout << "Processing update, time_delta: " << time_delta << ", time accumulated: " << s_time_buffer << std::endl;
float time_this_update = 0.f;
while ( s_time_buffer >= s_min_frametime )
{
s_time_buffer -= s_min_frametime;
time_this_update += s_min_frametime;
}
if ( time_this_update > s_max_time_threshold )
{
// We'll split the large amount of time into at least 2 updates to
// keep the update time steps from being too large.
update( s_max_time_threshold / 2, s_actual_time_elapsed );
update( s_max_time_threshold / 2, s_actual_time_elapsed );
}
else
{
while ( time_this_update > 0.f )
{
if ( time_this_update >= s_max_frametime )
{
time_this_update -= s_max_frametime;
update(s_max_frametime, s_actual_time_elapsed);
}
else
{
update(time_this_update, s_actual_time_elapsed);
time_this_update = 0.f;
}
}
}
}
</pre>
<br />
<b>Option 2.)</b><b> Don't used fixed timesteps once you exceed the maximum time threshold, just pass the actual time. This can result in extremely large timesteps in some cases, which can cause bugs.</b><br />
<br />
<pre class="brush: cpp">void process_update_needed(const float time_delta)
{
s_time_buffer += time_delta;
s_actual_time_elapsed += time_delta;
std::cout << "Processing update, time_delta: " << time_delta << ", time accumulated: " << s_time_buffer << std::endl;
float time_this_update = 0.f;
while ( s_time_buffer >= s_min_frametime )
{
s_time_buffer -= s_min_frametime;
time_this_update += s_min_frametime;
}
if ( time_this_update > s_max_time_threshold )
{
update( time_this_update, s_actual_time_elapsed );
}
else
{
while ( time_this_update > 0.f )
{
if ( time_this_update >= s_max_frametime )
{
time_this_update -= s_max_frametime;
update(s_max_frametime, s_actual_time_elapsed);
}
else
{
update(time_this_update, s_actual_time_elapsed);
time_this_update = 0.f;
}
}
}
}
</pre>
<br />
The reason the above method can cause bugs is due to the potential for a large time step. For example let's say your player's character is running and trying to jump over a gate that is rising up to block him. If the timesteps were small enough the gate would rise up before the player got to it and the player would be blocked by it. Now let's say you game has a hitch that causes it to freeze for a full second, and when the game resumes it passes that full second timestep to your player and the player jumps a second of distance through the air. There are ways to tackle this problem, but this is just one example of something you would need to handle with large timesteps. If you can stick to more updates at a smaller timestep, or allowing the game to slow down a bit, then you avoid those problems, as a tradeoff for the slowdown you'll get.<br />
<br />
Alright, we're almost done. We want a way to test our code, here's the main() function to do that for you:<br />
<pre class="brush: cpp">#include <ctime>
int main(int argc, const char * argv[])
{
// Randomize with time as a seed
std::srand( static_cast<unsigned int>(std::time(0)) );
static const float min_frametime = 0.01f; // 100 fps
static const float max_frametime = 0.04f; // 25 fps
for ( int i = 0; i < 30; ++i )
{
float rand_frametime = min_frametime + static_cast<float>(std::rand()) / (static_cast<float>( RAND_MAX / (max_frametime - min_frametime) ));
process_update_needed( rand_frametime );
}
return 0;
}
</pre>
<br />
Here's the full source code for the version that allows the game to slow down to avoid the well-of-despair problem.<br />
<pre class="brush: cpp">#include <iostream>
#include <ctime>
static float s_time_buffer = 0.f;
static float s_actual_time_elapsed = 0.f;
static const float s_device_refresh = 60.f;
static const float s_device_quarter_refresh = s_device_refresh / 4.f;
static const float s_min_framerate = s_device_quarter_refresh;
static const float s_max_frametime = 1 / s_min_framerate;
static const float s_target_framerate = s_device_refresh;
static const float s_min_frametime = 1 / s_target_framerate;
static const float s_max_time_threshold = s_device_refresh / 6.f;
void update(const float time_delta, const float game_time)
{
std::cout << "Update, time_delta: " << time_delta << ", total time: " << game_time << ", frame #: "
<< static_cast<int>(game_time / (1 / s_device_refresh)) << std::endl << std::endl;
}
void process_update_needed(const float time_delta)
{
s_time_buffer += time_delta;
s_actual_time_elapsed += time_delta;
std::cout << "Processing update, time_delta: " << time_delta << ", time accumulated: " << s_time_buffer << std::endl;
float time_this_update = 0.f;
while ( s_time_buffer >= s_min_frametime )
{
s_time_buffer -= s_min_frametime;
time_this_update += s_min_frametime;
}
if ( time_this_update > s_max_time_threshold )
{
// We'll split the large amount of time into at least 2 updates to
// keep the update time steps from being too large.
update( s_max_time_threshold / 2, s_actual_time_elapsed );
update( s_max_time_threshold / 2, s_actual_time_elapsed );
}
else
{
while ( time_this_update > 0.f )
{
if ( time_this_update >= s_max_frametime )
{
time_this_update -= s_max_frametime;
update(s_max_frametime, s_actual_time_elapsed);
}
else
{
update(time_this_update, s_actual_time_elapsed);
time_this_update = 0.f;
}
}
}
}
int main(int argc, const char * argv[])
{
// Randomize with time as a seed
std::srand( static_cast<unsigned int>(std::time(0)) );
static const float min_frametime = 0.01f; // 100 fps
static const float max_frametime = 0.04f; // 25 fps
for ( int i = 0; i < 30; ++i )
{
float rand_frametime = min_frametime + static_cast<float>(std::rand()) / (static_cast<float>( RAND_MAX / (max_frametime - min_frametime) ));
process_update_needed( rand_frametime );
}
return 0;
}
</pre>
Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com11tag:blogger.com,1999:blog-6184383319550035753.post-72248035511572934722013-04-01T20:08:00.000-06:002013-04-01T21:30:26.080-06:00Simple Gravity for your 3D gameBeginners out there are often making a really simple game and don't always need a physics engine. If you want to try out some basic gravity for your game, then something like this might work for you.<br />
<br />
Any object in your 3D world is going to need a 3D position (a point, often represented by a vector class). Applying gravity to your 3D objects is actually really simple, assuming you're not trying planetary physics around a sphere (or a gravity well of some kind). Each frame during an update cycle you just add gravity to the velocity of your objects. And later in the update cycle you move all of your objects based on their velocity. Here's some C++ pseudocode of how this might work:<br />
<br />
<pre class="brush: cpp">#include <vector>
class Object
{
public:
Object();
Vector3 m_position;
Vector3 m_velocity;
Matrix3 m_rotation;
float m_elasticity;
};
class SceneManager
{
public:
void update(float timeDelta);
private:
std::vector<Object> m_objects;
}
void SceneManager::update(float timeDelta)
{
// Be careful here, I'll explain why after the code snippet
for ( unsigned int i = 0; i < m_objects.size(); ++i )
{
applyGravity(m_objects[i]);
updatePosition(m_objects[i]);
}
}
void applyGravity(float timeDelta, Object& obj)
{
static Vector3 gravity(0.0f, -9.8f, 0.0f);
// Factor time when adding gravity, because 9.8m/s is a speed, and speed requires time
obj.m_velocity += (timeDelta * gravity);
}
void updatePosition(Object& obj)
{
obj.m_position += obj.m_velocity;
}
</pre>
Be careful when looping through your game's object list and making changes, if your change of position does something like cause a collision with another object, and you are handling that immediately, you could wind up making changes to your list of objects while you're in the middle of iterating through them.
The above sample will work, but if your 'applyGravity' and 'updatePosition' methods don't end up getting inlined then you're going to be incurring two function calls for every object in your scene. If those methods don't get inlined then I would recommend passing your entire list of objects that you want updated to the function and let the function loop through them and make the updates. It would like something like this:
<pre class="brush: cpp">void SceneManager::update(float timeDelta)
{
applyGravity(m_objects);
updatePosition(m_objects);
}
void applyGravity(float timeDelta, std::vector<Object>& objs)
{
// A hard-coded gravity, you might want to have this somewhere convenient
// where it can be changed at run-time. Depends on what you're trying to do.
static const Vector3 gravity(0.0f, -9.8f, 0.0f);
const float gravityThisFrame = (timeDelta * gravity);
for ( unsigned int i = 0; i < objs.size(); ++i )
{
objs[i].m_velocity += gravityThisFrame;
}
}
void updatePosition(std::vector<Object>& objs)
{
for ( unsigned int i = 0; i < objs.size(); ++i )
{
objs[i].m_position += objs[i].m_velocity;
}
}
</pre>
Once you have gravity your next concern will probably be some kind of collision detection with the ground. How you do that will be determined by your game, but once you've detected a collision with the ground, a simple way to handle the bounce is to flip the velocity and reduce it by some amount. The more you reduce the velocity the less bouncy your object is.
<pre class="brush: cpp">void handleGroundCollision(Object& obj)
{
objs[i].m_velocity.y *= -objs[i].m_elasticity.y;
}
</pre>The above method assumes your gravity is in the direction of the -Y axis. If you have a gravity going in a different direction then you may need to do a bit more of a complex calculation to bounce your object. The following method will handle basic collisions with any stationary object. In this case you need to pass the normal of the surface the object is hitting, if that is flat ground and your 'up' axis is +Y then the surface normal is Vector3(0.0f, 1.0f, 0.0f). Make sure your surface normal is normalized/unitized before using it in this method.
<pre class="brush: cpp">void Vector3::reflect( const Vector3& normal, float elasticity )
{
const float dotProductTimesTwo = Dot(normal) * 2.0f;
x -= dotProductTimesTwo * normal.x * elasticity;
y -= dotProductTimesTwo * normal.y * elasticity;
z -= dotProductTimesTwo * normal.z * elasticity;
}
// Or if you don't have your own Vector class, use this:
void reflect( Vector3& velocity, const Vector3& normal, float elasticity )
{
const float dotProductTimesTwo = Dot(normal) * 2.0f;
velocity -= ((dotProductTimesTwo * normal) * elasticity);
}
</pre><br />
Setting your object's elasticity to 0.0f would mean that it would not bounce at all. A value of 1.0f would mean a perfect bounce, which would have no loss of energy on the bounce. Any value higher than 1.0f would cause the ball to move with a higher velocity than when it bounced. Usually you're going to want something between 0.0f and 1.0f, feel free to experiment with it a bit.<br />
<br />
One more optimization consideration to make with this. If you have a lot of objects it can become more and more expensive to loop through them all each frame. If you separate your object list, or have another one for only the objects that can be moved or affected by gravity, then that will limit how many objects you're having to loop through each frame. Additionally if you have some more advanced detection methods you may know when an object is at rest due to it sitting on top of another object, if that is the case you may not need to apply gravity to it. Be careful with that optimization though, if gets tricky if you start mucking around with the direction of gravity.Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com2tag:blogger.com,1999:blog-6184383319550035753.post-82515354537335054352013-03-27T17:32:00.000-06:002013-05-22T23:08:39.533-06:00Code structure: Cleanliness and efficiencyThere are many ways to help make your code more readable, less bug-prone, and even more efficient. These are ignored by so many people whose code I've seen that I've decided to post about it. To many of you this stuff may be considered common sense, and that's a good thing.<br />
<br />
<h4>
Early out with conditionals when appropriate. This prevents your conditionals from nesting.</h4>
<br />
<b><span style="color: red;">Bad:</span></b><br />
<pre class="brush: cpp">void processMapNodes()
{
if ( !map.hasBeenProcessed() )
{
map.process();
// Other stuff here
map.setProcessed(true);
}
}
</pre>
<span style="color: lime;"><b>Good:</b></span><br />
<pre class="brush: cpp">void processMapNodes()
{
if ( map.hasBeenProcessed() )
{
return;
}
map.process();
// Other stuff here
map.setProcessed(true);
}
</pre>
<br />
<h4>
Early out with for loops. If you have to loop to find something, break out as soon as you've found it.</h4>
<br />
<span style="color: red;"><b>Bad:</b></span><br />
<pre class="brush: cpp">void removeMapNodeByName(const std::string& name)
{
for ( int i = 0; i < map_nodes.size(); ++i )
{
if ( map_nodes[i].getName() == name )
{
// Possibly some stuff here
map_nodes.erase( map_nodes.begin() + i );
}
}
}
</pre>
<b><span style="color: yellow;">Better:</span></b><br />
<pre class="brush: cpp">void removeMapNodeByName(const std::string& name)
{
for ( int i = 0; i < map_nodes.size(); ++i )
{
if ( map_nodes[i].getName() == name )
{
// Possibly some stuff here
map_nodes.erase( map_nodes.begin() + i );
// We've found what we're looking for, so we break and stop looping
break;
}
}
}
</pre>
<b><span style="color: lime;">Best:</span></b> (Use a conditional to continue as soon as possible)<br />
<pre class="brush: cpp">void removeMapNodeByName(const std::string& name)
{
for ( int i = 0; i < map_nodes.size(); ++i )
{
if ( map_nodes[i].getName() != name )
{
continue;
}
// Possibly some stuff here
map_nodes.erase( map_nodes.begin() + i );
break;
}
}
</pre>
<br />
Some of these examples are just to give you an idea of how to break out of code as soon as possible, but sometimes you can get even more efficient. In the example above we're simply going through a vector of data and looking for a match and then removing it. If what you're doing is really that trivial then you can use the standard library remove_if algorithm to do that for you. There are good examples of that, <a href="http://stackoverflow.com/a/7958447">here</a>, and <a href="http://www.cplusplus.com/reference/algorithm/remove_if/">here</a>.<br />
<br />
<h4>
Don't nest your conditionals unnecessarily</h4>
<br />
<b><span style="color: red;">Bad:</span></b> Here we have nested conditionals, it starts to get messy<br />
<pre class="brush: cpp">void foo(Bar* pBar)
{
if ( pBar )
{
if ( pBar->hasData() )
{
Data* pData = pBar->getData();
for ( int i = 0; i < pData->size(); ++i )
{
if ( pData[i].needsProcessing() )
{
pData[i].process();
}
}
}
}
}
</pre>
<span style="color: lime; font-weight: bold;">Good:</span> We unnest our if statements and leave the for loop as soon as possible.<br />
<pre class="brush: cpp">void foo(Bar* pBar)
{
if ( !pBar || !pBar->hasData() )
{
return;
}
Data* pData = pBar->getData();
for ( int i = 0; i < pData->size(); ++i )
{
if ( !pData[i].needsProcessing() )
{
continue;
}
// Do a bunch of stuff here
pData[i].process();
}
}
</pre>
<br />
<h4>
Create data only once it's needed</h4>
<b style="color: red;">Bad: </b>We're creating 'node_pos' at a point before we might exit the function early. This is wasteful and unnecessary.<br />
<pre class="brush: cpp">void moveToMapNode(const std::string& name)
{
Vector3 node_pos;
if ( map_nodes.empty() )
{
return;
}
for ( int i = 0; i < map_nodes.size(); ++i )
{
if ( map_nodes[i].getName() != name )
{
continue;
}
node_pos = map_nodes[i].getPosition();
break;
}
player.setPosition( node_pos );
}
</pre>
<b><span style="color: yellow;">Better:</span></b> We create node_pos after any point were we could leave the function early, so we're never creating it when it might not be needed. <br />
<pre class="brush: cpp">void moveToMapNode(const std::string& name)
{
if ( map_nodes.empty() )
{
return;
}
Vector3 node_pos;
for ( int i = 0; i < map_nodes.size(); ++i )
{
if ( map_nodes[i].getName() != name )
{
continue;
}
node_pos = map_nodes[i].getPosition();
break;
}
player.setPosition( node_pos );
}
</pre>
<b><span style="color: lime;">Best:</span></b> We don't need to create a named variable 'node_pos', and it doesn't need to be used in as large of a scope as it was, we can use the position we get directly within the for loop. <br />
<pre class="brush: cpp">void moveToMapNode(const std::string& name)
{
if ( map_nodes.empty() )
{
return;
}
for ( int i = 0; i < map_nodes.size(); ++i )
{
if ( map_nodes[i].getName() != name )
{
continue;
}
// This is still fairly clear, even though we have a function call within a function call.
// I wouldn't recommend nesting function calls any deeper than this, or debugging them
// and their return values can get messy if you end up with any bugs.
player.setPosition( map_nodes[i].getPosition() );
break;
}
}
</pre>
<h4>
Sort your conditionals such that the cheapest ones are evaluated first, or the one most likely to evaluate positively is evaluated first.</h4>
<b><span style="color: red;">Bad:</span></b> We're calling the more expensive function first. Both functions in the conditional must be true for us to continue, so we should be calling the cheap function first, and if it returns false there is no need to call the expensive function. <br />
<pre class="brush: cpp">void someFcn()
{
if ( isExpensiveFcnTrue() && isCheapFcnTrue() )
{
// Do stuff here
}
}
</pre>
<b><span style="color: lime;">Good:</span></b> We're calling the least expensive function first.<br />
<pre class="brush: cpp">void someFcn()
{
if ( isCheapFcnTrue() && isExpensiveFcnTrue() )
{
// Do stuff here
}
}</pre>
<b><span style="color: red;">Bad:</span></b> We're placing the cheaper methods first, however, if they're functions that are true most of the time then we're still likely to have to evaluate all of the functions, even the expensive one that is usually false. <br />
<pre class="brush: cpp">void someFcn()
{
if ( cheapFcnThatUsuallyReturnsTrue()
&& someOtherCheapFcnThatsUsuallyTrue()
&& moderatelyExpensiveButUsuallyFalse() )
{
// Do stuff here
}
}
</pre>
<b><span style="color: lime;">Good:</span></b> We call the more expensive method first, because it usually returns false, allowing us to skip the calls to the less expensive functions that usually return true. Basically your goal is to pay the lowest overall cost in your conditional statement, sometimes that will be calling cheaper methods first to avoid having to call expensive ones, if all of the functions stand similar chances of returning positive values, and sometimes you'll want to call more expensive ones first if it means you can save yourself numerous calls to other methods afterward. You'll need to make a judgement call based on the expense of the methods and what allows you to bail out as early as possible. <br />
<pre class="brush: cpp">void someFcn()
{
if ( moderatelyExpensiveButUsuallyFalse()
&& cheapFcnThatUsuallyReturnsTrue()
&& someOtherCheapFcnThatsUsuallyTrue() )
{
// Do stuff here
}
}
</pre>
If you're using || in your conditional, then you want to evaluate to true as soon as you can in your conditional, if you have && then you want to evaluate to false as soon as possible. Whatever the logic you're using, you want to do the least amount of work as possible to terminate the conditional check early and/or cheaply. This isn't only the most efficient, but it can make it easier to debug as you're not having to step through as much code when you exit early.<br />
<br />
<h4>
Cache results from an expensive algorithm or method that you might be calling more than once.</h4>
The compiler cannot optimize out multiple calls to the same function, unless those functions are purely constant expressions, so it's up to you to do it.<br />
<br />
<b><span style="color: red;">Bad:</span></b> Here we're calling numCompletedNodes() more than once.<br />
<pre class="brush: cpp">void displayCompletedNodeCount()
{
// Let's pretend that 'numCompletedNodes()' has a big O of N*log(n) each time it's called.
// If the player has completed any nodes in the map
if ( numCompletedNodes() > 0 )
{
// We update the UI to display the number of completed nodes
ui_interface->updateNodeCount( numCompletedNodes() );
}
}
</pre>
<br />
<b><span style="color: yellow;">Better:</span></b> We cache the number of nodes so we don't have to call the function each time we use it.<br />
<pre class="brush: cpp">void displayCompletedNodeCount()
{
// Let's pretend that 'numCompletedNodes()' has a big O of N*log(n) each time it's called.
const unsigned int num_completed_nodes = numCompletedNodes();
// If the player has completed any nodes in the map
if ( num_completed_nodes > 0 )
{
// We update the UI to display the number of completed nodes
ui_interface->updateNodeCount( num_completed_nodes );
}
}</pre>
<br />
<b><span style="color: lime;">Best:</span></b> If you really want to be more efficient, in this example it would probably be best to make sure that the numCompletedNodes() function is cheaper to call. Just from the example we can probably assume that it has to go through the map of nodes and calculate for each one if the player has completed it. That is probably information that could be stored on each node, which would bring the big O down to O(n). And you could go further and have a variable that keeps track of the completed node count as it changes, and then it would bring the cost down to O(1) (constant).Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com25tag:blogger.com,1999:blog-6184383319550035753.post-76229044423115728242013-03-26T17:12:00.000-06:002013-03-26T17:37:51.962-06:00Djikstra's Algorithm: Finding the Shortest PathFor those that are unfamiliar, <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm" target="_blank">Djikstra's Algorithm</a> is used to find the guaranteed shortest path between two points in a graph (as opposed to A* which will take an educated guess, but is more efficient). For the second time in as many years I've found myself needing a shortest path algorithm in a game project. The last one that I wrote was before my blog existed and I never published it, and since then I've lost access to the code base it was published in. This time I'm a bit more pressed for time and didn't want to write my own from scratch so I decided to grab one from online and fix it up a bit.<br />
<div><br />
</div><div>Here's the original that I found: <a href="http://www.reviewmylife.co.uk/blog/2008/07/15/dijkstras-algorithm-code-in-c/">http://www.reviewmylife.co.uk/blog/2008/07/15/dijkstras-algorithm-code-in-c/</a></div><div><br />
</div><div>It has several issues with it that I needed to solve:</div><div><ul><li>The algorithm itself and several methods related to it were not encapsulated, which is messy. At the least they should be in their own file.</li>
<li>Any nodes and edges that were created had to be deleted by the user otherwise the program would leak memory.</li>
<li>The code assumes all edges were bi-directional, I need to handle the possibility of a directional edge.</li>
<li>Querying the node graph would remove the nodes from the graph, making it so that if you wanted to query again you had to recreate the graph.</li>
<li>The code didn't handle the case in which there wasn't a possible path between two nodes</li>
<li>There were several inefficiencies.</li>
</ul><div>The changes I made were:</div></div><div><ul><li>Encapsulated the algorithm, and the containers for the nodes and edges into a Graph class.</li>
<li>The Graph class destructor made sure to clean up the nodes and edges to prevent memory leaks.</li>
<li>Made edges directional while still allowing for bi-directional connections.</li>
<li>Allowing the Graph class to not remove nodes while calculating the shortest path, so the user can query the graph as often as they'd like without recreating it.</li>
<li>Made a user-friendly method to allow the user to get a path between any two nodes.</li>
<li>Corrected inefficiencies.</li>
</ul><div>For the code containing all of my changes, (<a href="https://sites.google.com/site/nicsgamedev/Djikstras.zip?attredirects=0&d=1" target="_blank">click here</a>). I go over the changes in more detail at the end of this post.</div></div><div><br />
</div><div>In the example code, here is the graph:</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhkrtRaQi2LSrifArec5lSShImSCuu-YnIBjbkOUa3CawREStt3RPTApKdAcpSPX-w4LMTUBtW2HZ4D1KLhqcZ8P1H6qt-Qu60IXM4Wgc7-liul6dW38kveRmo5paJu4oZKj7T39PJ6tEQ/s1600/graph.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="434" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhkrtRaQi2LSrifArec5lSShImSCuu-YnIBjbkOUa3CawREStt3RPTApKdAcpSPX-w4LMTUBtW2HZ4D1KLhqcZ8P1H6qt-Qu60IXM4Wgc7-liul6dW38kveRmo5paJu4oZKj7T39PJ6tEQ/s640/graph.jpg" width="640" /></a></div><div class="separator" style="clear: both; text-align: center;"><br />
</div><div>Notice that the edges between A and B, and E and F, are uni-directional, you cannot move from B to A, or F to E. In a shortest path algorithm, each node connection (edge) has a weight rather than a distance, this is because we're really not looking for the path of least distance, but the path that can be traversed the fastest, so we may want to factor in things along the path that may slow down the traveller. For example, the connection between B and E, and B and D are of different distances, but both have a weight of 4. Maybe the path between B and E is a smooth concrete path, but from B to D is a swampy path that is hard to traverse.</div><div><br />
</div><div>Given the weights that we've given to each edge, denoted by the numbers near each edge, the shortest path from A to F is: A->B->E->F. Because some edges are uni-directional, the shortest path from F to A is: F->D->B->E->C->A (in fact, that's the only path from F to A). We can also start on nodes besides A and F. For example, the shortest path from C to D is: C->E->F->D.</div><div><br />
</div><div>Below here you'll find the code, organized into main.cpp and three classes. Graph is the class that contains the algorithm and stores Nodes and Edges. And a class for Node, and a class for Edge.</div><div><br />
</div><div>First let's look at main.cpp so we can see how the graph is created and utilized:</div><div><br />
</div><pre class="brush: cpp">#include <iostream>
#include "graph.h"
#include "node.h"
// NOTE: Credit for the original code for this implementation of
// Djikstra's Algorithm goes to:
// http://www.reviewmylife.co.uk/blog/2008/07/15/dijkstras-algorithm-code-in-c/
// I've modified it to suit my needs.
void outputPath(std::vector<node> path)
{
for ( long i = (path.size() - 1); i >= 0; --i )
{
std::cout << path[i]->getID() << " ";
}
std::cout << std::endl;
}
int main(int argc, const char * argv[])
{
Graph graph;
// Create and name our nodes
Node* a = graph.createNode('a');
Node* b = graph.createNode('b');
Node* c = graph.createNode('c');
Node* d = graph.createNode('d');
Node* e = graph.createNode('e');
Node* f = graph.createNode('f');
// Create some edges
graph.createEdge(a, b, 5);
graph.createEdge(a, c, 4);
graph.createEdge(b, d, 4);
graph.createEdge(b, e, 4);
graph.createEdge(c, e, 6);
graph.createEdge(d, f, 3);
graph.createEdge(e, f, 2);
// Create some edges so we can get from 'f' to 'a'
graph.createEdge(f, d, 3);
graph.createEdge(d, b, 4);
graph.createEdge(e, c, 6);
graph.createEdge(c, a, 4);
std::vector<node> path;
// Go from 'c' to 'f'
graph.getPathFromStartNodeToFinishNode(c, f, path);
outputPath(path);
// Go from 'a' to 'f'
graph.getPathFromStartNodeToFinishNode(a, f, path);
outputPath(path);
// Go from 'f' to 'a'
graph.getPathFromStartNodeToFinishNode(f, a, path);
outputPath(path);
return 0;
}
</pre><br />
And below you'll find the three class .h/.cpp files.<br />
<br />
<b>graph.h</b><br />
<pre class="brush: cpp">#pragma once
#include <vector>
class Node;
class Edge;
class Graph
{
public:
Graph() {}
~Graph();
Node* createNode(char id);
Edge* createEdge(Node* node1, Node* node2, const int weight);
void removeEdge(Edge* edge);
void getPathFromStartNodeToFinishNode(Node* node1, Node* node2, std::vector<node>& path);
private:
void processGraph();
Node* extractSmallest(std::vector<node>& nodes);
private:
std::vector<node> m_nodes;
std::vector<edge> m_edges;
};
</pre><br />
<b>graph.cpp</b><br />
<pre class="brush: cpp">#include "graph.h"
#include "node.h"
#include "edge.h"
#include <iostream>
Graph::~Graph()
{
for ( int i = 0; i < m_nodes.size(); ++i )
{
delete m_nodes[i];
}
for ( int i = 0; i < m_edges.size(); ++i )
{
delete m_edges[i];
}
}
Node* Graph::createNode(char id)
{
Node* new_node = new Node(id);
m_nodes.push_back(new_node);
return new_node;
}
Edge* Graph::createEdge(Node* node1, Node* node2, const int weight)
{
// Yes, we intentionally reverse the node order here
Edge* new_edge = new Edge(node2, node1, weight);
m_edges.push_back(new_edge);
return new_edge;
}
void Graph::removeEdge(Edge* edge)
{
std::vector<edge>::iterator it = m_edges.begin();
for ( ; it < m_edges.end(); ++it)
{
if (*it == edge)
{
m_edges.erase(it);
return;
}
}
}
void Graph::getPathFromStartNodeToFinishNode(Node* start, Node* finish, std::vector<node>& path)
{
path.clear();
// Clear any existing node information
for ( int i = 0; i < m_nodes.size(); ++i )
{
m_nodes[i]->setDistanceFromStart(INT_MAX);
m_nodes[i]->setPreviousNode(NULL);
}
start->setDistanceFromStart(0);
processGraph();
Node* previous = finish;
while (previous)
{
path.push_back(previous);
previous = previous->getPreviousNode();
}
if ( path.size() == 1 )
{
path.clear();
}
}
void Graph::processGraph()
{
// Create a copy of the nodes.
std::vector<node> nodes = m_nodes;
while (nodes.size() > 0)
{
Node* smallest = extractSmallest(nodes);
std::vector<node> out_nodes;
smallest->adjacentRemainingNodes(nodes, m_edges, out_nodes);
const size_t size = out_nodes.size();
for (int i = 0; i < size; ++i)
{
Node* adjacent = out_nodes[i];
const int distance_to_node = adjacent->distanceToNode(m_edges, smallest);
if ( distance_to_node == -1 )
{
continue;
}
const int total_distance = distance_to_node + smallest->getDistanceFromStart();
if ( total_distance < adjacent->getDistanceFromStart() )
{
adjacent->setDistanceFromStart(total_distance);
adjacent->setPreviousNode(smallest);
}
}
}
}
Node* Graph::extractSmallest(std::vector&ltnode&gt& nodes)
{
if ( nodes.empty() )
{
return NULL;
}
int smallest_position = 0;
Node* smallest = nodes[0];
for ( int i = 1; i < nodes.size(); ++i )
{
Node* current = nodes[i];
if ( current->getDistanceFromStart() < smallest->getDistanceFromStart() )
{
smallest = current;
smallest_position = i;
}
}
nodes.erase(nodes.begin() + smallest_position);
return smallest;
}
</pre><br />
<b>node.h</b><br />
<pre class="brush: cpp">#pragma once
#include <vector>
class Edge;
class Node
{
public:
Node(char id) :
id(id)
, m_previous(NULL)
, m_distance_from_start(INT_MAX)
{
}
char getID() const { return id; }
void setPreviousNode(Node* node) { m_previous = node; }
Node* getPreviousNode() const { return m_previous; }
void setDistanceFromStart(int distance) { m_distance_from_start = distance; }
int getDistanceFromStart() const { return m_distance_from_start; }
Node* extractSmallest(std::vector<node>& nodes);
void adjacentRemainingNodes(const std::vector<node>& nodes, const std::vector<edge>& edges,
std::vector<node>& out_nodes) const;
int distanceToNode(const std::vector<edge>& edges, const Node* other_node) const;
bool contains(const std::vector<node>& nodes, const Node* node) const;
private:
char id;
Node* m_previous;
int m_distance_from_start;
};
</pre><br />
<br />
<br />
<b>node.cpp</b><br />
<pre class="brush: cpp">#include "node.h"
#include "edge.h"
void Node::adjacentRemainingNodes(const std::vector<node>& nodes, const std::vector<edge>& edges,
std::vector<node>& out_nodes) const
{
const size_t size = edges.size();
for(int i = 0; i < size; ++i)
{
const Edge* edge = edges[i];
Node* adjacent = NULL;
if (edge->first() == this)
{
adjacent = edge->second();
}
else if (edge->second() == this)
{
adjacent = edge->first();
}
if (adjacent && contains(nodes, adjacent))
{
out_nodes.push_back(adjacent);
}
}
}
int Node::distanceToNode(const std::vector<edge>& edges, const Node* other_node) const
{
const size_t size = edges.size();
for(int i = 0; i < size; ++i)
{
const Edge* edge = edges[i];
if ( edge->connects(this, other_node) )
{
return edge->getDistance();
}
}
// Happens if two nodes do not connect or the connection is directed in the opposite direction
return -1;
}
bool Node::contains(const std::vector<node>& nodes, const Node* node) const
{
for(int i = 0; i < nodes.size(); ++i)
{
if (node == nodes[i])
{
return true;
}
}
return false;
}
</pre><br />
<b>edge.h </b><br />
<pre class="brush: cpp">#pragma once
#include <vector>
class Node;
class Edge
{
public:
Edge(Node* node1, Node* node2, int distance) :
m_node1(node1)
, m_node2(node2)
, m_distance(distance)
{
// Assert that node1 and node2 aren't null and that distance is a positive value
}
Node* first() const { return m_node1; }
Node* second() const { return m_node2; }
int getDistance() const { return m_distance; }
bool connects(const Node* node1, const Node* node2) const;
private:
Node* m_node1;
Node* m_node2;
int m_distance;
};
</pre><br />
<b>edge.cpp </b><br />
<pre class="brush: cpp">#include "edge.h"
#include "node.h"
bool Edge::connects(const Node* node1, const Node* node2) const
{
return ( (node1 == m_node1) && (node2 == m_node2) );
}</pre><br />
<h3>The Changes</h3><b>The Graph class destructor made sure to clean up the nodes and edges to prevent memory leaks.</b><br />
The original required you to keep track of all of your own pointers to nodes and edges and delete them.<br />
<br />
<pre class="brush: cpp">Graph::~Graph()
{
for ( int i = 0; i < m_nodes.size(); ++i )
{
delete m_nodes[i];
}
for ( int i = 0; i < m_edges.size(); ++i )
{
delete m_edges[i];
}
}
</pre><br />
<b>Made edges directional while still allowing for bi-directional connections.</b><br />
The original 'connects' method checked if the edge went in either direction, which made it so you could not have uni-directional edges.<br />
<br />
<pre class="brush: cpp">#include "edge.h"
#include "node.h"
bool Edge::connects(const Node* node1, const Node* node2) const
{
return ( (node1 == m_node1) && (node2 == m_node2) );
}
</pre><br />
And here we handle the case where we don't get a valid distance from a distance check, which can happen if there is no possible path.<br />
<pre class="brush: cpp">void Graph::processGraph()
{
// Create a copy of the nodes.
std::vector<Node*> nodes = m_nodes;
while (nodes.size() > 0)
{
Node* smallest = extractSmallest(nodes);
std::vector<node> out_nodes;
smallest->adjacentRemainingNodes(nodes, m_edges, out_nodes);
const size_t size = out_nodes.size();
for (int i = 0; i < size; ++i)
{
Node* adjacent = out_nodes[i];
// We get the distance, if it's -1 then we know there is no possible path between the two nodes
const int distance_to_node = adjacent->distanceToNode(m_edges, smallest);
if ( distance_to_node == -1 )
{
continue;
}
const int total_distance = distance_to_node + smallest->getDistanceFromStart();
if ( total_distance < adjacent->getDistanceFromStart() )
{
adjacent->setDistanceFromStart(total_distance);
adjacent->setPreviousNode(smallest);
}
}
}
}
</node></pre><br />
<b>Allowing the Graph class to not remove nodes while calculating the shortest path, so the user can query the graph as often as they'd like without recreating it.</b><br />
The key change from the original is that we make a copy of the list of nodes. The copies list is then whittled away by this function and then goes out of scope, the original would alter the 'm_nodes' list, thus requiring the user to recreate it after each time they queried for a new path.<br />
<br />
<pre class="brush: cpp">void Graph::processGraph()
{
// Create a copy of the nodes.
std::vector<node> nodes = m_nodes;
// ... Rest of function ...
}
</pre><br />
<b>Made a user-friendly method to allow the user to get a path between any two nodes.</b><br />
The original required you to recreate the entire graph, and then manually set the distance on the start node to 0, and then run the algorithm. I don't have the graph nodes deleted after they process so here I clear out changes the nodes might be storing, then set the distance on the start node, then iterate through the nodes and save out the path. If the path only ends up with the last node in it then we know that there is no path to the start node.<br />
<br />
<pre class="brush: cpp">void Graph::getPathFromStartNodeToFinishNode(Node* start, Node* finish, std::vector<node>& path)
{
path.clear();
// Clear any existing node information
for ( int i = 0; i < m_nodes.size(); ++i )
{
m_nodes[i]->setDistanceFromStart(INT_MAX);
m_nodes[i]->setPreviousNode(NULL);
}
start->setDistanceFromStart(0);
processGraph();
Node* previous = finish;
while (previous)
{
path.push_back(previous);
previous = previous->getPreviousNode();
}
if ( path.size() == 1 )
{
path.clear();
}
}
</pre><br />
<b>Corrected inefficiencies</b><br />
There were several places in the original code sample that included the use of std::vector's 'at' method. This method is around 5-10x slower than using the [] operator. 'at' performs a range check, which is unnecessary if your code is setup to prevent indices from going out of range. Additionally there were places where entire containers were being created on the heap (using 'new'), and then deleted within the same scope. These have been changed to use the stack instead, which is generally much more efficient.<br />
<br />
As an example, here was the original method:<br />
<pre class="brush: cpp">void Dijkstras()
{
while (nodes.size() > 0)
{
Node* smallest = ExtractSmallest(nodes);
vector<node>* adjacentNodes =
AdjacentRemainingNodes(smallest);
const int size = adjacentNodes->size();
for (int i=0; i<size; ++i)
{
Node* adjacent = adjacentNodes->at(i);
int distance = Distance(smallest, adjacent) + smallest->distanceFromStart;
if (distance < adjacent->distanceFromStart)
{
adjacent->distanceFromStart = distance;
adjacent->previous = smallest;
}
}
delete adjacentNodes;
}
}
</pre><br />
And here you can see that we're creating a vector on the stack and passing it by reference to the 'adjacentRemainingNodes' method. Because it's not being created on the heap we also don't have to worry about deleting a pointer that was created by another method:<br />
<br />
<pre class="brush: cpp">void Graph::processGraph()
{
// Create a copy of the nodes.
std::vector<Node*> nodes = m_nodes;
while (nodes.size() > 0)
{
Node* smallest = extractSmallest(nodes);
std::vector<node> out_nodes;
smallest->adjacentRemainingNodes(nodes, m_edges, out_nodes);
const size_t size = out_nodes.size();
for (int i = 0; i < size; ++i)
{
Node* adjacent = out_nodes[i];
const int distance_to_node = adjacent->distanceToNode(m_edges, smallest);
if ( distance_to_node == -1 )
{
continue;
}
const int total_distance = distance_to_node + smallest->getDistanceFromStart();
if ( total_distance < adjacent->getDistanceFromStart() )
{
adjacent->setDistanceFromStart(total_distance);
adjacent->setPreviousNode(smallest);
}
}
}
}
</pre>Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com3tag:blogger.com,1999:blog-6184383319550035753.post-60453413356247573732013-03-07T08:31:00.000-07:002013-03-08T23:00:12.758-07:00Why always-on DRM is bad, and companies using it should feel bad<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj5sGqbaaOnfeuAFRLDdwbwhYI_mWRNhUrioCvi-FRMtF0-YN9nl8lSnW92nQCaTSOP3_-wbP2EJUJfxuxuhANIlHRyiliWwmrBSviRlYNKBvPifkdFy5vupgIYf4cGQKZtJPVTBOG1fvE/s1600/simcity_issues.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em; text-align: center;"><img border="0" height="255" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj5sGqbaaOnfeuAFRLDdwbwhYI_mWRNhUrioCvi-FRMtF0-YN9nl8lSnW92nQCaTSOP3_-wbP2EJUJfxuxuhANIlHRyiliWwmrBSviRlYNKBvPifkdFy5vupgIYf4cGQKZtJPVTBOG1fvE/s400/simcity_issues.png" width="400" /></a>Always-on DRM means that a video game requires a constant Internet connection to be able to play. The reason companies use it is that it is currently the best means of preventing piracy. By placing a large amount of the game's logic on the servers, they can insure that pirates cannot simply crack the game overnight, anyone that wanted to crack the game would have to write their own version of the server's logic and build it into the client, and on top of that they would have to strip the existing client of all of the calls to the server for that logic.<br />
<br />
<span style="font-size: large;">Ok, but why is this bad?</span><br />
<br />
- <b>The company can patch your single player game at any time.</b> You just wanted to sit down and play for 15-20 minutes? Sorry, you'll need to download this patch real quick. And "real quick" completely depends on how bogged-down their patching servers are. Besides that fact, they're patching your single player game, let that sink in for a minute. What if you already liked the game exactly how it is? Too bad, you have to accept the patch to play. Anytime there are patches there is also a potential for new bugs, I've seen games get much worse after a patch.<br />
<br />
- <b>You have to have an Internet connection.</b> For some people this truly isn't an issue, but others may not have a decent Internet connection, or they may have bandwidth caps. What if you want to play the game while on a trip, or in the airplane? Tough cookies.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
- <b>You cannot play when their servers are down.</b> Even if your Internet connection is reliable, the EA servers aren't, and when they're not working properly you may not be able to play at all. You will have a game that you paid for, and you cannot play a single-player experience because of some server issues 800 miles away. Or maybe you can play, but your city that is saved on their servers becomes corrupted, and you have to roll it back. Someday the servers will be shut down, and when that day comes you'll no longer be able to play Sim City 5, you'll never get to play it again. You can go back and play Sim City 1 still, but not 5. Some people play old games and aren't comfortable with their $60 being for a temporary experience with a game.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg0AKb4WRbTPYacV4f2j-KAE6O9qrHAE8hA0rDL1Hr-cQbbVJGMRFdjpoVcHMTZbkwrOIRkwL8oBLvKRSEjtk95ALpS-wCfiZpmhaWM9llqB01p5nD2HXf6ilDXAQp1YygNfvHfF_CANBI/s1600/simcity_issues2.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="225" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg0AKb4WRbTPYacV4f2j-KAE6O9qrHAE8hA0rDL1Hr-cQbbVJGMRFdjpoVcHMTZbkwrOIRkwL8oBLvKRSEjtk95ALpS-wCfiZpmhaWM9llqB01p5nD2HXf6ilDXAQp1YygNfvHfF_CANBI/s400/simcity_issues2.png" width="400" /></a></div>
- <b>You cannot play if your account gets banned.</b> EA is notorious for banning players accounts due to stuff like a forum post that they don't approve of. I understand EA potentially banning them from the forum, but they also ban the player's Origin account entirely, which blocks them from playing any games on Origin. I'm not sure how this is even legal, but I'm betting EA covered their asses in the EULA for stuff like this.<br />
<br />
- <b>Servers cannot handle the same computational load per player.</b> There's a lot of logic going on at any given time in a city, and the more logic the server wants to handle the more CPU power EA's servers are going to need. EA will only have a finite amount of CPU power to give to each player, so they'll either need more servers, which will cost them money, or they'll need to scale down how much CPU power the game needs. Why is this bad for you? This is the reason why SimCity 5 does not allow large cities, the computations that the server would have to do would become exponentially larger as the cities grew, and so rather than cut down on the simulation level to allow for a larger city, they chose to cut down on the city size itself. Had the game been running on your CPU instead of theirs this likely would not have been as much of an issue.<br />
<br />
-<b> Finite content due to server space.</b> Because the plots of land are server-side, they take up space on the servers. If they allowed every player to deform their own terrain, they would have unique plots of land on a per-player basis, which would take up more space and could potentially cause issues with the simulation on their end. So because the game runs on their servers, you cannot have deformable terrain. SimCity 2000, which ran on DOS 5.x before Windows 95 was even released, almost 20 years ago, will allow you to deform terrain, but SimCity 5, which runs on a computer in your home that is several hundred times more powerful, does not.<br />
<br />
<div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEigpg9BrBkr_up-NO2Rk1bpdkNgHlJcQd-BqxtszxK7qOL-eMJyiT7Rpb1JZEz4z3JbHdFYNU-00MpiRtnAO1LElOkFSOyDe7OmJ62UExRWFgACs7bngXBlJAuzcZLXAfoAqAHipRl2FSE/s1600/simcity_issues3.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="225" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEigpg9BrBkr_up-NO2Rk1bpdkNgHlJcQd-BqxtszxK7qOL-eMJyiT7Rpb1JZEz4z3JbHdFYNU-00MpiRtnAO1LElOkFSOyDe7OmJ62UExRWFgACs7bngXBlJAuzcZLXAfoAqAHipRl2FSE/s400/simcity_issues3.png" width="400" /></a></div>
<b>- You cannot save your city locally.</b> Some people like to save their city, make a copy and then burn it to the ground, or watch Godzilla tear it down. Then they have a copy where they can reload the city and all is well again, and good fun was had. But you cannot save versions of your cities on the cloud in the new SimCity. Also, the servers are having all kinds of issues with losing progress on people's cities, if those people could have save copies locally this wouldn't really be an issue.<br />
<br /></div>
<div>
I understand why companies use DRM, but there is a point when they take it too far and it negatively affects the experience for the customer. In this case EA screwed up large parts of a great game franchise in order to save a few bucks. I'm curious how much it will even save them in the long run as they have to maintain and run servers 24/7 during the life of the game.</div>
<div>
<br /></div>
<div>
Here's how I would've implemented the DRM. Single-player mode would be entirely offline, so you have no required connection to play the game. Single-player cities can never communicate with cities your friends have made, if you want that you have to play online. If you play online you get the exact experience that EA created with the current game, all the connectivity with your friends' cities, or the cities of complete strangers. This means the customer gets the best of both worlds. We're talking about a better game experience, and the publisher has denied the customer this experience because they want to make an extra buck.</div>
<div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<b>My experience with SimCity 5 so far:</b></div>
<div>
<ul>
<li>Didn't purchase the game on day 1 because I knew it would be a disaster. And it was indeed a disaster, most people couldn't play.</li>
<li>Purchased the game on day 2. Installed the game. After the game installed it ran an update and said the game was ready.</li>
<li>I run the game's launcher and it then downloads another update. After this update completes it says to relaunch the game.</li>
<li>I click the relaunch button and the launcher crashes. I run the game's launcher again, and it downloads another update. Again it says to relaunch the launcher.</li>
<li>I once again click the relaunch button, and the launcher crashes again.</li>
<li>I run the launcher again and the game finally says that I can play my single-player game that I have a physical copy of.</li>
<li>All of the servers for North America are full, so I connect to a European server.</li>
<li>I wanted to join with a friend's private region, however SimCity cannot see any of my friends from Origin, and they couldn't see me either, so I cannot play the game with my friends.</li>
<li>I decided to try making my own region. When attempting this I got an error saying I could not create my own region right now. Tried this every 5 minutes for the next two hours.</li>
<li>Finally it let me create a region, and now I have to pick a plot of land within the region to create a city. I chose my plot of land and now I get an error saying I cannot create a city right now, and that I should try again later. Tried this every 5 minutes for another two hours.</li>
<li>I finally gave up after a total of 6 hours with the game. I spent those 6 hours entirely within the game's menus.</li>
<li>I wake up the next morning and try again. This time when the game starts up it takes me straight to a tutorial mode, I cannot skip this tutorial.</li>
<li>The tutorial loads up a small city, and then the city sits there doing nothing, I cannot click on any of the UI for the city and I have no prompts telling me what I should do. Hitting escape does nothing to get me out of the tutorial. I do have some UI at the top of my screen that I can use to go back to the main menu or to quit. I go back to the main menu, which then sends me back into the tutorial, which still does not work. So I quit again.</li>
<li>2 hours later I try again. I start up the game, and this time the tutorial is gone. I check my friend's list, and that is still empty. I try creating my own city again, and I'm back to not being able to create my own region.</li>
</ul>
<div>
In summary, I can't play multi-player, I can't play single player, and it's day 3 since the game was released. I'd consider this to be a failure of a game launch. If I cannot play the game on day 5 I will be demanding a refund from EA. And I'm not likely to purchase any of their games again anytime soon, I cannot support a company that puts a little bit of money above the importance of their customer. There are plenty of companies out there doing just fine without always-online DRM, so until it is problem-free it really shouldn't be used.</div>
</div>
Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com3tag:blogger.com,1999:blog-6184383319550035753.post-31956179305521316182013-02-25T23:28:00.002-07:002013-03-26T16:42:35.546-06:00Simple terrain smoothingAfter creating or importing terrain you may find it to be too steep or jagged. Part of this depends on how your terrain system is written, but it also depends on the resolution of the terrain and terrain you're importing.<br />
<br />
Let's image the grid below signifies sections of our terrain, with the numbers representing elevation. We can see there are two peaks that are 20 meters tall, surrounded immediately by flat terrain that is 0 meters tall. So we basically have two very steep and pointy peaks that are 20 meters high.<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEicNgOA9g3ZM6BSt6C8-zykBjYINP4d8jIdM2xgj2JCabeEhTz4VSqdljYJlYkJYKmc_APNyNRL3VLUYIw3gHrqPpYdRsWqa1u-yMKbPe-LDEFh8EYBeYrMFva-Fj61Y1BvnQP4UuYOigM/s1600/4x4gridA.jpg" imageanchor="1" style="clear: left; display: inline !important; margin-bottom: 1em; margin-right: 1em; text-align: center;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEicNgOA9g3ZM6BSt6C8-zykBjYINP4d8jIdM2xgj2JCabeEhTz4VSqdljYJlYkJYKmc_APNyNRL3VLUYIw3gHrqPpYdRsWqa1u-yMKbPe-LDEFh8EYBeYrMFva-Fj61Y1BvnQP4UuYOigM/s320/4x4gridA.jpg" width="320" /></a><br />
<br />
To smooth the section represented here in blue, we total up all of the heights in the red squares (which gives us 20), and we divide by the number of red squares (there are 8 squares, so 20 / 8 = 2.5), and we average that result and the height of the blue square together. (20 + 2.5) / 2 = 11.25. We now have our new smoothed value, and we replace the blue square with that value.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjyYI7fWomd1IQDx2IkSDws1vBmScJQkm4b9-CAN8Ru6tuZ3w3QtS_pC7HW5KhnyC2OJeSbKeresGdD_Ler_LAagXBwykLx5WI7mw8T-Ld0KqQlZt4Rc34zmZI-hXZ-Id_fcZlGu514QhU/s1600/4x4gridB.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjyYI7fWomd1IQDx2IkSDws1vBmScJQkm4b9-CAN8Ru6tuZ3w3QtS_pC7HW5KhnyC2OJeSbKeresGdD_Ler_LAagXBwykLx5WI7mw8T-Ld0KqQlZt4Rc34zmZI-hXZ-Id_fcZlGu514QhU/s320/4x4gridB.jpg" width="320" /></a></div><br />
<div class="separator" style="clear: both; text-align: center;"></div><div style="text-align: left;">Here we can see the results after smoothing out just the one square in the example above.<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiGEtPJ2YOGgjsdvQ2-9KR-2gMoHLsIU0rwNoE50Du8Tr11vSb93d13b-RjHE6QQbFjqcELOLZkzRKhbtbnG6R_CYPX9FHmO0kd4nWhq1lSly-UGSjIh1y4yxsDcvMKCHZewbOmfes1vZw/s1600/4x4gridC.jpg" imageanchor="1" style="clear: left; display: inline !important; margin-bottom: 1em; margin-right: 1em; text-align: center;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiGEtPJ2YOGgjsdvQ2-9KR-2gMoHLsIU0rwNoE50Du8Tr11vSb93d13b-RjHE6QQbFjqcELOLZkzRKhbtbnG6R_CYPX9FHmO0kd4nWhq1lSly-UGSjIh1y4yxsDcvMKCHZewbOmfes1vZw/s320/4x4gridC.jpg" width="320" /></a></div><br />
<br />
Here's what we get when we run the algorithm against every square in the grid.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXE3pj69GbwxIExZjVlHRqMUBnT5ku5S04kCxDavxVxV1riabaLvxeDYBQXfDiSJOCplA4KKY3XGATGVLJsHjbw4EEnZBIH6aVBmesufpuV1lzdxvhm75LjLxBUKXS8M2ALdqb-uqmiLo/s1600/4x4gridD.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXE3pj69GbwxIExZjVlHRqMUBnT5ku5S04kCxDavxVxV1riabaLvxeDYBQXfDiSJOCplA4KKY3XGATGVLJsHjbw4EEnZBIH6aVBmesufpuV1lzdxvhm75LjLxBUKXS8M2ALdqb-uqmiLo/s320/4x4gridD.jpg" width="320" /></a></div><br />
<div class="separator" style="clear: both; text-align: center;"><br />
</div>Here's the algorithm:<br />
<pre class="brush: cpp">public void SmoothTerrain(int Passes)
{
float[,] newHeightData;
while (Passes > 0)
{
Passes--;
// Note: MapWidth and MapHeight should be equal and power-of-two values
newHeightData = new float[MapWidth, MapHeight];
for (int x = 0; x < MapWidth; x++)
{
for (int y = 0; y < MapHeight; y++)
{
int adjacentSections = 0;
float sectionsTotal = 0.0f;
if ((x - 1) > 0) // Check to left
{
sectionsTotal += HeightData[x - 1, y];
adjacentSections++;
if ((y - 1) > 0) // Check up and to the left
{
sectionsTotal += HeightData[x - 1, y - 1];
adjacentSections++;
}
if ((y + 1) < MapHeight) // Check down and to the left
{
sectionsTotal += HeightData[x - 1, y + 1];
adjacentSections++;
}
}
if ((x + 1) < MapWidth) // Check to right
{
sectionsTotal += HeightData[x + 1, y];
adjacentSections++;
if ((y - 1) > 0) // Check up and to the right
{
sectionsTotal += HeightData[x + 1, y - 1];
adjacentSections++;
}
if ((y + 1) < MapHeight) // Check down and to the right
{
sectionsTotal += HeightData[x + 1, y + 1];
adjacentSections++;
}
}
if ((y - 1) > 0) // Check above
{
sectionsTotal += HeightData[x, y - 1];
adjacentSections++;
}
if ((y + 1) < MapHeight) // Check below
{
sectionsTotal += HeightData[x, y + 1];
adjacentSections++;
}
newHeightData[x, y] = (HeightData[x, y] + (sectionsTotal / adjacentSections)) * 0.5f;
}
}
// Overwrite the HeightData info with our new smoothed info
for (int x = 0; x < MapWidth; x++)
{
for (int y = 0; y < MapHeight; y++)
{
HeightData[x, y] = newHeightData[x, y];
}
}
}
}</pre><br />
<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; margin-right: 1em; text-align: left;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgrtDS7zAFQJWjfgyMvbymVo_HXbmIJLzMjy_aAT474ib8y2nHQj_v8834slYxBDLYEviZwKcmKTEH8MF4E3hbN6r5HrAoekSLQWiLtzOyYWWIG6ic03Hag2hErCW9bvfivbU-MaMizGEA/s1600/smoothing0passes.jpg" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto; text-align: center;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgrtDS7zAFQJWjfgyMvbymVo_HXbmIJLzMjy_aAT474ib8y2nHQj_v8834slYxBDLYEviZwKcmKTEH8MF4E3hbN6r5HrAoekSLQWiLtzOyYWWIG6ic03Hag2hErCW9bvfivbU-MaMizGEA/s400/smoothing0passes.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><span style="font-size: xx-small; text-align: start;">Here's some purposely jagged terrain, without any smoothing</span></td></tr>
</tbody></table><br />
<br />
<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEis5m2ggOV40l1pzjNLFmlG69M_lMBNXJA1DaHAkkmzx8SU7eWVN1MJXkzsRYl3e0OiQM7rs4cNsa7Aeep99uQlmMxKhCuUB-VKCeOQmprjo7ZZKoiErOi827_IX2NC0_6Z9oi5lWUPQ5E/s1600/smoothing1passes.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em; text-align: center;"><br />
</a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEis5m2ggOV40l1pzjNLFmlG69M_lMBNXJA1DaHAkkmzx8SU7eWVN1MJXkzsRYl3e0OiQM7rs4cNsa7Aeep99uQlmMxKhCuUB-VKCeOQmprjo7ZZKoiErOi827_IX2NC0_6Z9oi5lWUPQ5E/s1600/smoothing1passes.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em; text-align: center;"><br />
</a><br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; margin-right: 1em; text-align: left;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEis5m2ggOV40l1pzjNLFmlG69M_lMBNXJA1DaHAkkmzx8SU7eWVN1MJXkzsRYl3e0OiQM7rs4cNsa7Aeep99uQlmMxKhCuUB-VKCeOQmprjo7ZZKoiErOi827_IX2NC0_6Z9oi5lWUPQ5E/s1600/smoothing1passes.jpg" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEis5m2ggOV40l1pzjNLFmlG69M_lMBNXJA1DaHAkkmzx8SU7eWVN1MJXkzsRYl3e0OiQM7rs4cNsa7Aeep99uQlmMxKhCuUB-VKCeOQmprjo7ZZKoiErOi827_IX2NC0_6Z9oi5lWUPQ5E/s400/smoothing1passes.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Terrain after one smoothing pass</td></tr>
</tbody></table><br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; margin-right: 1em; text-align: left;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhwS6gO7nqSlhl6uBGbJPhqX9JJqTLYrt5lhsDYKD02dXqrMp9ikEFA8Eqbr1g50FEVGwgHjBTrdnIBMKHXsOG95N_AEEvK6ew8t51vZHF9JmJRlid-ZbBrHrIZ7LpiOhFcIJkNgdlin9U/s1600/smoothing5passes.jpg" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhwS6gO7nqSlhl6uBGbJPhqX9JJqTLYrt5lhsDYKD02dXqrMp9ikEFA8Eqbr1g50FEVGwgHjBTrdnIBMKHXsOG95N_AEEvK6ew8t51vZHF9JmJRlid-ZbBrHrIZ7LpiOhFcIJkNgdlin9U/s400/smoothing5passes.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">After five smoothing passes</td></tr>
</tbody></table><br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; margin-right: 1em; text-align: left;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgj3Qic7CHKR3ya0Ssn5jr9irxNKl5vXyQ7qR7FTba3qOFaBDsWGn92i75z7yB1JoL2ztncHKhriNYTB04B5hw_wlHoRNEu4tgRNP02byuHHYaU0aFsNAZbRBxkJ46j0o4ymxtvHfDAuTo/s1600/smoothing50passes.jpg" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgj3Qic7CHKR3ya0Ssn5jr9irxNKl5vXyQ7qR7FTba3qOFaBDsWGn92i75z7yB1JoL2ztncHKhriNYTB04B5hw_wlHoRNEu4tgRNP02byuHHYaU0aFsNAZbRBxkJ46j0o4ymxtvHfDAuTo/s400/smoothing50passes.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">After 50 smoothing passes. 20 passes would probably have been fine</td></tr>
</tbody></table><br />
<div class="separator" style="clear: both; text-align: center;"><br />
</div><br />
<div class="separator" style="clear: both; text-align: center;"><br />
</div><br />
<div class="separator" style="clear: both; text-align: center;"><br />
</div>Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com5tag:blogger.com,1999:blog-6184383319550035753.post-81356917673482100432013-02-25T22:42:00.001-07:002013-03-09T13:14:44.600-07:00The bounce-pad hack in LEGO Universe<div class="separator" style="clear: both; text-align: left;">
The bounce-pads (also known as "bouncers") in LEGO Universe were a means of travel, when you stepped on them they sent you to a specific location in the map, usually somewhere nearby that you could not otherwise reach. Bounce-pads were one of the first gameplay elements created during the production of the game (almost 3 years before the game released), and had no real issues during the entire production run or alpha/beta testing, so we were all somewhat surprised to run into a huge bug on the very first day the game opened up to the public.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
The whole company gathered in the gym around some big screen TVs so we could watch the game go live for the first time. We watched a few people get in the game and play for a short time and then we all scattered back to our desks so we could login and play the game ourselves. No sooner than had I created my first character I had a person from the live service team at my desk describing to me a serious bug. Apparently there were a large number of players that were stuck in the very first area of the game called "The Venture Explorer", a small spaceship that served as an introduction level to teach players them the basics. About two thirds of the way through the map there is a spot where you must quickbuild your first LEGO model, a bounce-pad, and afterwards you step on it and it bounces you to the next NPC to give you your next mission. It seemed that about 1 in 100 players would build the bounce-pad but could not step on it to get bounced, so they had no way to get to NPC to get the next mission. </div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhv7pdB22ApJUMdTq_ynPvQYa9H6WnEk6WsVR2aMaYtBX9gs5QKjT3QAVs1YHRWis3EPvGsj7BqkKvMvrQWzR2m8tL-nSylZXXC5_-OwAwfqwDz-RcYo4HhKp3WqEpusziTqTnbxPoTBWY/s1600/bouncepad.gif" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em; text-align: center;"><img border="0" height="256" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhv7pdB22ApJUMdTq_ynPvQYa9H6WnEk6WsVR2aMaYtBX9gs5QKjT3QAVs1YHRWis3EPvGsj7BqkKvMvrQWzR2m8tL-nSylZXXC5_-OwAwfqwDz-RcYo4HhKp3WqEpusziTqTnbxPoTBWY/s400/bouncepad.gif" width="400" /></a>We had some in-game GMs talking with some of the players having this problem, and apparently they could see the bounce-pad but they couldn't step on it. The part of the code responsible for bouncing the player was the bounce-pad code that would set the player's velocity when the physics system told it that the player collided with the bounce-pad. Somewhere in that flow something was broken, and I wanted to find out what it was. We had nobody in the office that was experiencing this bug, none of our testers had seen it at any point during production either. Because we couldn't reproduce this in-house my next thought was to see what information I could get from the clients that were seeing the bug. As a gameplay programmer I didn't really know the details of what kinds of reporting and tools the live team had setup with the game to be able to get me information about this problem. As it turns out, there was almost nothing.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
The client version of the game was setup to generate log messages for any errors, and there's a good chance the log file might tell me if something was amiss, like maybe the physics for the bounce-pad was failing to load, or if something was going wrong in the collision check. Sadly, the live team never got around to setting up a way for the clients to be able to send us their logs, or for a GM to be able to send a message to the client's program and have it return the logs to us. At the time they said something about possible legal reasons for us not getting information about them sent automatically to us, which seemed a bit ridiculous since the information didn't contain any account information besides the name of their in-game character, and a 32-bit account ID, which even if it got into the wrong hands is worthless. Anyway, getting any information from the client was impossible at the time.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Server log files were one thing I did have access to, unfortunately this was a client issue since not everyone was seeing it, and since the functionality to make the player bounce was entirely client-side, with only some server-side monitoring to check for cheating.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
My next idea was to use some in-game tools that I had written during development, that created huge amounts of data about any object in the world. I was hoping I could use this tool to see if there might be any issues with the bounce-pad itself that the tool could find. The tool would analyze thousands of points of data on an object (at run-time) and check for any inconsistencies and report them back. This tool was not built into the version of the client that players used, so I would need to build an internal version of the client and log-in with it, additionally the server would not return the requested information unless you were using a GM account, for security reasons. It took awhile but finally I was given a temporary GM account to be able to analyze the problem, and still we were able to find nothing, mostly because the client information about the object was based on my client, which was working fine.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
After about a day of sifting through logs and using tools to try and find any issues I could find nothing, and in the mean time GMs were having to sit in the game and teleport these players to the NPC so they could get their missions. The pressure was on to find a solution, but the only information I had to go on was that a small percentage of players were seeing a problem, and because this appeared to be a client-side problem and there was no system to get client logs back to me, there was nothing I could put in the game to get me any information about the problem. The reason this problem was on me was because I had written the bounce-pad system, the system that now appeared to be broken.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
I enlisted the help of a couple fellow gameplay programmers to try and see what we could do to reproduce the problem in-house. We tried removing the physics asset from the computer to see how the game would react, and when starting the game the patching system would see the missing asset and simply download it again. There were code paths that could be hit if a physics file failed to load, so we put in some code to force the physics asset to fail to load, and in that case the game put in a fallback physics shape (a 1x1x1 cube), and even though that wasn't the proper shape it was still enough the player could touch it and the system would respond and bounce them, so that was a no-go. We checked to see if maybe the collision could be succeeding and somehow the bounce-pad code was failing to translate that into a bounce, but we couldn't see any point of failure, or a way to force it to fail.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
So here we are with a problem we cannot produce, and a system we can't seem to make fail, and no way to get any information from the players that were seeing the problem. Leaving the bug as-is was unacceptable, as it would mean a lot of lost customers or the expense of GMs permanently stationed near the broken bounce-pad to teleport players. So the solution, was a hack.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
During early development of LEGO Universe, almost all gameplay was entirely server-based. Things like attacking, picking up power-ups on the ground, and using bounce-pads were done entirely on the server and then the server would inform the client of the event. This was very secure but it resulted in laggy gameplay, which didn't work well for an action game like LEGO Universe. Along with other systems the bounce-pads were made so that the client-side object did the bouncing of the player, and simply told the server what it had done so that the server could check for any possible cheating or hacking. So, remembering that it used to work on the server years ago, and that the bounce-pads were still properly loading on the server, the solution presented itself. I put in code on the server so that if the player stood on a bounce-pad for more than half of a second and did not get a message from the client's bounce-pad that they've bounced, that it would assume the bounce-pad on the client was broken and bounce the player from the server. The result was that for those 1 in 100 players seeing the problem, that one bounce-pad on the first level would feel a little bit laggy but it would work. We also setup some server-side logging for any time the server-side bounce-pad needed to take over, and we found that we were only ever seeing the logging for that one bounce-pad in the first level of the game. For some reason that we never tracked down, it was only ever that one asset that exhibited this problem in the game, there was never another problem related to the physics for an asset not properly loading. </div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
We did make the assumption that the physics were likely failing somehow on those clients, because the only way we weren't able to bounce on the client was if a physics collision message was never sent to the bouncer, so I do feel some comfort in that the system I wrote may not have been the problem, it just affected my system. Even though as a team we take responsibility for the entire product, rather than saying "this is my code, that is your code", it's still feels good when you've written a system that works well, so you never want to see it break down and fail. It remains the biggest hack that I've ever made to a released product, but I don't feel bad about it, I feel like I made the best of the situation with what I was given, and in the end the players never knew the difference. </div>
Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com6tag:blogger.com,1999:blog-6184383319550035753.post-91504273132315575582012-07-03T13:15:00.003-06:002012-07-03T13:16:42.391-06:00Changing the name of an XCode projectA hit a small snag today when trying to rename an XCode project.<br />
<b><u>Pro tip:</u></b> Don't change the name of your XCode project from anywhere outside of XCode.<br />
<br />
Apparently XCode has some magic behind the scenes when it renames a project, which probably changes some references to the project internally. If you rename your project file from outside of XCode you will no longer be able to run your project.<br />
<br />
To rename the project from within XCode, simply click on the project from the file view in the XCode IDE, and it will allow you to change the name, and additionally will give you the option to save a snapshot of the change in case you want to roll back.Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0tag:blogger.com,1999:blog-6184383319550035753.post-833492288199274802012-06-08T22:56:00.002-06:002012-06-08T22:57:15.146-06:00Performance function/scope timers, for WindowsIn my <a href="http://nic-gamedev.blogspot.com/2012/06/high-performance-functionscope-timers.html">last post</a> I showed you have to create an easy-to-use timer for Mac OSX programs that would calculate the time it took a function or scope to execute. Here's the Windows version I promised.<br />
<br />
Here's the main.cpp:<br />
<pre class="brush: cpp">// main.cpp
#include <iostream>
#include "PerfTimer.h"
void someFcn()
{
CreateFcnTimer;
for (unsigned int i = 0; i < 10000000; ++i )
{
int j = 5;
++j;
}
}
int main(int argc, const char * argv[])
{
{
ScopeTimer("MyCustomScope");
someFcn();
}
return 0;
}
</pre><br />
And here's the timer class itself.<br />
<pre class="brush: cpp">// PerfTimer.h
#pragma once
#include <iostream>
#include <windows.h>
class PerfTimer
{
public:
PerfTimer(const char* timerName)
{
m_name = std::string(timerName);
QueryPerformanceFrequency(&m_frequency);
// Start the timer
QueryPerformanceCounter(&m_startTime);
}
~PerfTimer()
{
LARGE_INTEGER endTime;
QueryPerformanceCounter(&endTime);
// Output timer duration in milliseconds
std::cout << m_name.c_str() << ": " << ((endTime.QuadPart - m_startTime.QuadPart) * 1000.0 / m_frequency.QuadPart) << std::endl;
}
private:
LARGE_INTEGER m_startTime;
LARGE_INTEGER m_frequency;
std::string m_name;
};
#ifndef SHIPPING_BUILD
#define CreateFcnTimer PerfTimer __FUNCTION__timer(__FUNCTION__)
// The 'x' in 'xtimer' is replaced by whatever string is passed into the scope timer
// but the quotations are removed. So if the calling code is ScopeTimer("stuff")
// then 'xtimer' becomes 'timerstuff'. This makes sure every timer name is unique
// within the scoe it is used.
#define ScopeTimer(x) PerfTimer xtimer(x)
#else
// The timers can be shut off in shipping builds by replacing their standard
// macros with these.
#define CreateFcnTimer ((void)0)
#define ScopeTimer(x) ((void)0)
#endif
</pre>
<br />
The only difference between this Windows version and the Mac version is that you need to include Windows.h, and you have to query the frequency using QueryPerformanceFrequency, and factor the frequency into your calculations.Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0tag:blogger.com,1999:blog-6184383319550035753.post-59131218844672596922012-06-08T01:01:00.000-06:002013-05-22T23:02:18.582-06:00High performance function/scope timers, and some more macro love (Mac OS X)<b>Looking for a Windows version of this timer? It's in the following post, <a href="http://nic-gamedev.blogspot.com/2012/06/performance-functionscope-timers-for.html" target="_blank">click here</a> to go to it.</b><br />
<br />
In my <a href="http://nic-gamedev.blogspot.com/2012/06/c-macros-arent-completely-evil-i.html" target="_blank">last post</a> I talked about the fact that macros aren't always evil, and that reminded me of a function/scope timer I made for LEGO Universe, which took advantage of some fun macros. So today I'll show you how to create that timer.<br />
<br />
This timer outputs its elapsed time whenever it leaves scope, so by using one at the beginning of your functions your can output how long a function call takes. Or you can use one anywhere else where a scope if defined.<br />
<br />
Below is the main.cpp:<br />
<br />
<pre class="brush: cpp">// main.cpp
#include <iostream>
#include <math.h>
#include "PerfTimer.h"
void someFcn()
{
CreateFcnTimer;
// someFcn timer is now in scope
for (unsigned int i = 0; i < 10000000; ++i )
{
int j = sqrt(5);
++j;
}
}
int main(int argc, const char * argv[])
{
{
ScopeTimer("MyCustomScope");
// MyCustomScope timer is now in scope
someFcn();
// someFcn timer created by 'CreateFcnTimer' is now out of scope
}
// MyCustomScope timer is now out of scope
return 0;
}
</pre>
<br />
Inside of <span style="font-family: 'Courier New', Courier, monospace;">someFcn()</span>you see a simple macro call: <span style="font-family: 'Courier New', Courier, monospace;">CreateFcnTimer; </span><br />
This macro creates a timer for us that will automatically output the name of the function and the time it took to execute it, it prints this information when the timer goes out of scope, which is immediately after the function is done executing.<br />
<br />
Inside of <span style="font-family: 'Courier New', Courier, monospace;">main()</span>you see a set of brackets used to create a scope, and within that scope we call a macro named <span style="font-family: 'Courier New', Courier, monospace;">ScopeTimer</span>, and this time we give it whatever name we'd like, in this case it's "MyCustomScope". This timer goes out of scope when the scope that we defined with the brackets ends. You can use this technique to subdivide larger sections of code and time how long they take to execute.<br />
<br />
The output from this program, when I ran it on my iMac was:<br />
<br />
<div class="p1">
<b><span style="font-family: 'Courier New', Courier, monospace;">someFcn: 101.953</span></b></div>
<div class="p1">
<b><span style="font-family: 'Courier New', Courier, monospace;">MyCustomScope: 102.08</span></b></div>
<div class="p1">
<b><span style="font-family: 'Courier New', Courier, monospace;"><br />
</span></b></div>
<div class="p1">
The output is in milliseconds, but the timer is accurate down to 1 microsecond (1/1000th of a millisecond). You can see here that someFcn() was called within the unnamed scope we created in main(), and the timer within someFcn went out of scope after someFcn() finished executing, and then "MyCustomScope" went out of scope soon after. The results here show us that it takes about 102.08 milliseconds to loop 10 million times and create an integer on the stack, set it to the square root of 5, increment it, then remove it from the stack, during each loop. The results from the scope timer show that someFcn()'s code took up most of the time, and the remaining 0.127 milliseconds was for the call to someFcn(), the function timer within, and then exit someFcn(). We can deduce this because the 102.08 milliseconds recorded by the function timer began after the function timer was already created and the call to someFcn had been made and was already in progress. 0.127 seems like a lot, most of that time is in the creation of the timer within someFcn and the outputting of timer info to the console, not for the function call. If function calls took 0.127 milliseconds then computers would be performing like they were about 35 years ago.</div>
<div class="p1">
<br /></div>
<div class="p1">
Here's the version of the performance timer that will run on Mac OSX. In my next post I will post the code for Windows. I'm not trying to draw this out into two posts, it's just really late and I haven't written and tested the Windows version yet (the difference will be only in the timer class internally used).</div>
<div class="p1">
<br /></div>
<div class="p1">
<br /></div>
<pre class="brush: cpp">// PerfTimer.h
#pragma once
#include <iostream>
#include <mach/mach.h>
#include <mach/mach_time.h>
#include <unistd.h>
class PerfTimer
{
public:
PerfTimer(const char* timerName)
{
m_name = std::string(timerName);
// Start the timer
m_startTime = mach_absolute_time();
}
~PerfTimer()
{
uint64_t endTime = mach_absolute_time();
uint64_t elapsed = (endTime - m_startTime);
static mach_timebase_info_data_t sTimebaseInfo;
if ( sTimebaseInfo.denom == 0 )
{
mach_timebase_info(&sTimebaseInfo);
}
uint64_t elapsed_nano = elapsed * sTimebaseInfo.numer / sTimebaseInfo.denom;
// Output timer duration in milliseconds
std::cout << m_name.c_str() << ": " << elapsed_nano / 1000000.0 << " milliseconds" << std::endl;
}
private:
uint64_t m_startTime;
std::string m_name;
};
#ifndef SHIPPING_BUILD
#define CreateFcnTimer PerfTimer __func__timer(__func__)
// The 'x' in 'xtimer' is replaced by whatever string is passed into the scope timer
// but the quotations are removed. So if the calling code is ScopeTimer("stuff")
// then 'xtimer' becomes 'timerstuff'. This makes sure every timer name is unique
// within the scoe it is used.
#define ScopeTimer(x) PerfTimer xtimer(x)
#else
// The timers can be shut off in shipping builds by replacing their standard
// macros with these.
#define CreateFcnTimer ((void)0)
#define ScopeTimer(x) ((void)0)
#endif
</pre>
First I'll explain how the timer itself works, then how the macros work. When the timer is constructed it records the name passed into the constructor so we can output it later, and then records the exact system time. Then, when it destructs it queries the system time, and then outputs the difference between the time it was constructed and destructed. The timer is basically a simple object that records when it is created and when it leaves scope or is destructed. The <span style="font-family: 'Courier New', Courier, monospace;">CreateFcnTimer</span> macro works by creating a PerfTimer instance, and it names the variable the function name followed by the word '<span style="font-family: 'Courier New', Courier, monospace;">timer</span>'. This ensures that the name of the timer variable is fairly unique so it's unlikely to have collisions with other times you might use within the same scope. Also, the name of the function is the name passed into the constructor, and when the timer destructs it's that name that will output next to the time elapsed. The <span style="font-family: 'Courier New', Courier, monospace;">MyCustomScope</span> macro is similar to <span style="font-family: 'Courier New', Courier, monospace;">CreateFcnTimer</span> except that it does not use the function name automatically so you can name it whatever you choose. Similarly to <span style="font-family: 'Courier New', Courier, monospace;">CreateFcnTimer</span>, it uses the name you pass into the macro to generate the name of the timer instance variable, so you would only have a conflict when using this macro if you happened to create another timer with the exact same name in the same scope.<br />
<br />
And if you notice, I've used the technique from my previous post to ensure that these timers will not run on a shipping build, which would slow down your program a good amount with the creation of the timers and especially the console output of them.Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0Denver, CO, USA39.737567 -104.984717939.5422015 -105.3005749 39.9329325 -104.66886090000001tag:blogger.com,1999:blog-6184383319550035753.post-36728665186771298982012-06-02T00:09:00.000-06:002012-06-02T00:31:44.425-06:00C++ Macros aren't completely evil, I promiseAs a C++ programmer you'll undoubtedly hear of many macro horror stories. Macros can be easily abused, can bloat your program, and can be a debugging nightmare. But, macros are not completely evil, when used properly they can be clean and useful.<br />
<br />
The other day I was updating a logging system. For those that don't know, a logging system (or logger) is usually a system created along side a program or engine that allows programmers to log messages, or errors, and to stream their output in different ways, like to a debug console, or to a file, or even an email in some rare cases (like a critical program failing in a bad way and a live product team needs to know immediately). Anyway, I was updating a logging system, and I needed two things that it did not yet offer:<br />
<ul>
<li>I needed the parameters being logged to have no expense within the shipped product (the product that was in the customer's hands). </li>
<ul>
<li>Without macros there are ways people try to limit logging commands:</li>
<ul>
<li>Multiple function definitions for your logging commands, the shipped version of these do nothing when called.<br />
<pre class="brush: cpp">#define SHIPPING_BUILD
#include <iostream>



namespace logging


{


#ifndef SHIPPING_BUILD
void print( int i )


{


std::cout << i;


}


#else


void print ( int i ) { }


#endif


}



int expensiveFcnReturningAnInt()


{
// The compiler would actually optimize this so it would


// be extremely cheap to call, but you get the idea, this


// function would be something you don't want to happen


// in a shipping build if used only for logging.


return 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1;


}



int main(int argc, const char * argv[])


{


logging::print( expensiveFcnReturningAnInt() );


return 0;


}</pre>
</li>
<li>In the above example the expense of the logging itself is removed, there is nothing logged to the debug console, or written to a log file. But the main issue here, is that <span style="font-family: 'Courier New', Courier, monospace;">expensiveFcnReturningAnInt()</span> was still called, which is expensive, completely unnecessary, and useless</li>
</ul>
<li>With macros you can affect the code at compile time. In this example the logging statement will no longer even exist in the program for shipping builds.</li>
<ul>
<li> <pre class="brush: cpp">#define SHIPPING_BUILD
#include <iostream>
#ifndef SHIPPING_BUILD
#define INTERNAL_PRINT(x) logging::print(x)
#else
#define INTERNAL_PRINT(x) ((void)0)
#endif
namespace logging
{
void print( int i )
{
std::cout << i;
}
}
int expensiveFcnReturningAnInt()
{
// The compiler would actually optimize this so it would
// be extremely cheap to call, but you get the idea, this
// function would be something you don't want to happen
// in a shipping build if used only for logging.
return 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1;
}
int main(int argc, const char * argv[])
{
INTERNAL_PRINT( expensiveFcnReturningAnInt() );
return 0;
}
</pre>
</li>
</ul>
<li>In this sample, the call inside of <span style="font-family: 'Courier New', Courier, monospace;">main()</span> to <span style="font-family: 'Courier New', Courier, monospace;">INTERNAL_PRINT</span> is completely optimized out of the program when <span style="font-family: 'Courier New', Courier, monospace;">SHIPPING_BUILD</span> is defined.</li>
</ul>
<li>I needed a simple, one-line logging command that accepted a stream of information, just like an std::stringstream.</li>
<ul>
<li>Without a macro, you would be forced to make an entire class to try and get you close to this functionality, and even then you might not get it. </li>
<li>With a macro you can have exactly what you want:</li>
</ul>
</ul>
<blockquote style="border: none; margin: 0 0 0 40px; padding: 0px;">
</blockquote>
<ul><ul>
<li><pre class="brush: cpp">#define SHIPPING_BUILD
#include <iostream>
#ifndef SHIPPING_BUILD
#include <sstream>
#define PRINT_STREAM(x) \
{ \
std::stringstream strStream; \
strStream << x; \
logging::print(strStream.str().c_str()); \
}
#else
#define PRINT_STREAM(x) ((void)0)
#endif
namespace logging
{
void print( const char* message )
{
std::cout << message;
}
}
int expensiveFcnReturningAnInt()
{
// The compiler would actually optimize this so it would
// be extremely cheap to call, but you get the idea, this
// function would be something you don't want to happen
// in a shipping build if used only for logging.
return 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1;
}
int main(int argc, const char * argv[])
{
PRINT_STREAM( "Expensive fcn result is: " << expensiveFcnReturningAnInt() );
return 0;
}</pre>
</li>
</ul>
</ul>
I would recommend splitting your logging stuff into its own header, or class even. The examples above have everything in the same file/snippet to keep things easier to read for this blog.Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0tag:blogger.com,1999:blog-6184383319550035753.post-26341954421453525942012-04-20T08:37:00.001-06:002013-02-26T13:39:04.802-07:00C++11: Strongly-typed enumEnums have always been a useful feature of C++, allowing the programmer to easily make a list of values that are related to one another, with names that are easy to understand. In fact, enums are at the heart of the messaging system I talk about in <a href="http://nic-gamedev.blogspot.com/2012/02/game-engine-architecture.html">this post</a>. However, the classic C++ enum is subject to many issues as well that make it less useful than it could be, and this is why in C++11 they have introduced a strongly-typed enum, called an
<span style="color: #3d85c6; font-family: 'Courier New', Courier, monospace;">enum class</span>.<br />
<br />
<b>1.) Implicit conversion to an integer.</b><br />
Enums are not type-safe. They do prevent you from directly assigning one type of enum value to another, but there is nothing stopping you from casting an integer directly to an enum type.<br />
<br />
<pre class="brush: cpp">enum PrimaryColor
{
Red = 0,
Blue,
Yellow
};
enum FavoriteColor
{
Green = 0,
Orange,
Purple
};
PrimaryColor pC = Red;
FavoriteColor fC = Orange;
pC = fC; // Error, you cannot assign one enum value directly to another.
pC = Green; // Same error
bool primaryColorIsGreater = (pC >= Green); // Bad! This is allowed, but probably isn't intended.
</pre>
<br />
Notice on the final line we are able to make a comparison between a primary color and a favorite color. Green isn't even a primary color, so this is probably not intended.<br />
<br />
If you want something type safe, the <span style="color: #3d85c6; font-family: 'Courier New', Courier, monospace;">enum class</span> comes to the rescue!<br />
<br />
<pre class="brush: cpp">enum class PrimaryColor
{
Red = 0,
Green,
Blue
};
enum class FavoriteColor
{
Green = 0,
Orange,
Purple
};
PrimaryColor pC = Red;
FavoriteColor fC = Orange;
pC = fC; // Error, you cannot assign one enum value directly to another.
pC = Green; // Same error
bool primaryColorIsGreater = (pC >= FavoriteColor::Green); // Error, you cannot directly compare types from different enums.
</pre>
<br />
<br />
<b>2.) Scope</b><br />
Enums are not strongly scoped. The enumerators of an enum have scope in the same scope as the enum itself. For example, what if in the example above we wanted <span style="font-family: 'Courier New', Courier, monospace;">FavoriteColor</span> to have some of the colors as <span style="font-family: 'Courier New', Courier, monospace;">PrimaryColor</span>?<br />
<br />
<pre class="brush: cpp">enum PrimaryColor
{
Red = 0,
Blue,
Yellow
};
enum FavoriteColor
{
Green = 0,
Red, // Error, 'Red' is already defined in the PrimaryColor enum
Blue // Error, 'Blue' is already defined in the PrimaryColor enum
};
</pre>
<br />
We're not able to do this with standard enums because they're not strongly scoped, however, the new <span style="color: #3d85c6; font-family: 'Courier New', Courier, monospace;">enum class</span> will let us do this.<br />
<br />
<pre class="brush: cpp">enum class PrimaryColor
{
Red = 0,
Green,
Blue
};
enum class FavoriteColor
{
Green = 0,
Red, // Ok
Blue // Ok
};
</pre>
<br />
3.) Inability to specify underlying type<br />
The underlying type of an enum is not portable, because different compilers will use different underlying types for an enum. For example, if you're using an enum directly in a packet of information, the sender and receiver may have a different perception of what size that enum value takes.<br />
<br />
<pre class="brush: cpp">enum Version
{
Version1 = 1,
Version2 = 2,
Version3 = 3
};
struct Packet
{
Version version; // Bad! This size can vary by implementation.
// More data here
}
</pre>
<br />
You can workaround this, but it's not ideal (hence calling it a 'workaround'):<br />
<pre class="brush: cpp">struct Packet
{
unsigned char version; // This works, but requires casting
// More data here
}
</pre>
<br />
The workaround is ugly, we shouldn't have to store a version number as a char, and require the user on the other end to understand what type of data is stored in that char, and force them to cast it back to a integer (or unsigned integer). The <span style="color: #3d85c6; font-family: 'Courier New', Courier, monospace;">enum class</span> solves this issue for us, by allowing us to specify the underlying type of the enum, so we can guarantee what size it will be.<br />
<br />
<pre class="brush: cpp">enum class Version : unsigned
{
Version1 = 1,
Version2 = 2,
Version3 = 3
};
struct Packet
{
Version version; // This is now safe to do, we know that 'version' is an unsigned int.
// More data here
}
</pre>
<br />
Also, because the size of a standard enum differs by implementation, using values that assume signed or unsigned can be unsafe. Take, for example, the enum below:<br />
<br />
<pre class="brush: cpp">enum MyEnum
{
Value1 = 1,
Value2 = 2,
ValueBig = 0xFFFFFFF0U
};
</pre>
<br />
Note that the last value has been explicitly set to an unsigned int. Because of the differing implementations of enums by different compilers, the resulting value of <span style="font-family: 'Courier New', Courier, monospace;">ValueBig</span> also differs depending on what you're compiling with. This means that your code is not longer portable, and will only work as intended in some compilers. For compilers that treat enums as unsigned <span style="font-family: 'Courier New', Courier, monospace;">ValueBig</span> will be <span style="font-family: 'Courier New', Courier, monospace;">4294967280</span>, for those that treat is as signed <span style="font-family: 'Courier New', Courier, monospace;">ValueBig</span> will be <span style="font-family: 'Courier New', Courier, monospace;">-16</span>. Even worse, there are compilers that treat <span style="font-family: 'Courier New', Courier, monospace;">ValueBig</span> as <span style="font-family: 'Courier New', Courier, monospace;">4294967280</span>, but when comparing it against -1 will tell you that <span style="font-family: 'Courier New', Courier, monospace;">ValueBig</span> is less than -1. The <span style="color: #3d85c6; font-family: 'Courier New', Courier, monospace;">enum class</span> solves this problem by allowing the programmer to specify the type. If we want 'ValueBig' to be 0xFFFFFFF0U then we just make sure that our
<span style="color: #3d85c6; font-family: 'Courier New', Courier, monospace;">enum class</span> is specified to be an <span style="color: #3d85c6; font-family: 'Courier New', Courier, monospace;">unsigned int</span>:<br />
<br />
<pre class="brush: cpp">enum class MyEnum : unsigned
{
Value1 = 1,
Value2 = 2,
ValueBig = 0xFFFFFFF0U // ValueBig is now guaranteed to be 4294967280
};
</pre>
<br />
In Visual Studio 2011 the enum class is signed by default. I'm willing to bet that the C++11 standard defines this to be the required default, to prevent issues like what occurred with the basic enum.<br />
<br />
<pre class="brush: cpp">enum class MyEnum // We do not specify the value
{
Value1 = 1,
Value2 = 2,
ValueBig = 0xFFFFFFF0U // ValueBig in VS2011 is -16
};
</pre>
<br />
Some IDEs are helpful and will show you what your values are going to be so there are no surprises.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgdrEMGGf-yhEDSzyRTAatk3ztofuzU-pD6WAO2SurDx-FO0PSgCbSn-r6Hvwu93wNSmeB7T70D1q3kd7LsElWYPAlm1dAfXMxFQxGr2g0wokOIuViaw317-5XrB5FiIg3qaj9syONkaZM/s1600/enum.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="153" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgdrEMGGf-yhEDSzyRTAatk3ztofuzU-pD6WAO2SurDx-FO0PSgCbSn-r6Hvwu93wNSmeB7T70D1q3kd7LsElWYPAlm1dAfXMxFQxGr2g0wokOIuViaw317-5XrB5FiIg3qaj9syONkaZM/s320/enum.jpg" width="298" /></a></div>
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<span style="font-size: x-small;"><br /></span>
Sources:<br />
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2347.pdfNichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0tag:blogger.com,1999:blog-6184383319550035753.post-1751636541719961162012-04-19T22:25:00.000-06:002012-04-19T22:27:29.682-06:00C++11: Range-based for-loops and autoOne of the downsides to using C++ in recent years has been how verbose it is compared to some other languages, such as Java, C#, or Scala, just to name a few. One of the goals of the new C++11 standard was to allow for code that is more terse, and I must say, I love it.<br />
<br />
One of the things about using STL in C++ that has always bothered me was how bulky it is. Let's take for example, iterating over a vector of strings, using the standard C++03 for-loop.<br />
<br />
<pre class="brush: cpp">std::vector<std::string> words;
words.push_back("Hello");
words.push_back("World");
words.push_back("...and good morning!");
std::vector<std::string>::const_iterator wordItr;
for (wordItr = words.begin(); wordItr != words.end(); ++wordItr)
{
std::cout << (*wordItr).c_str() << " ";
}
</pre><br />
That's a lot of code just to loop through the words and print each one. In C++11 they have introduced a new keyword: <span style="color: #3d85c6; font-family: 'Courier New', Courier, monospace;"><b>auto</b></span>. <b><span style="color: #3d85c6; font-family: 'Courier New', Courier, monospace;">auto</span> </b>assumes the type of whatever is assigned to it, making it less verbose when the type would be especially long, such as <span style="font-family: 'Courier New', Courier, monospace;"><b>std::vector</b></span><std::string><span style="font-family: 'Courier New', Courier, monospace;"><b>::const_iterator</b></span>. Let's see if we can clean up the code a bit using the </std::string><b><span style="color: #3d85c6; font-family: 'Courier New', Courier, monospace;">auto</span> </b>keyword.<br />
<br />
<pre class="brush: cpp">std::vector<std::string> words;
words.push_back("Hello");
words.push_back("World");
words.push_back("...and good morning!");
for (auto word = words.cbegin(); word != words.cend(); ++word)
{
std::cout << (*word).c_str() << " ";
}
</pre><br />
That's a fair amount better. We didn't have to spend an entire line of code just creating our iterator variable, auto saved so much room we we able to do it inline within the for-loop. However, we still have to initialize to begin(), and compare against end(), and increment the iterator. Those things are so standardized, it would be great if the for loop could take care of that for us. And it can! C++11 introduces range-based for-loops to do just that.<br />
<br />
<pre class="brush: cpp">std::vector<std::string> words;
words.push_back("Hello");
words.push_back("World");
words.push_back("...and good morning!");
for (auto word: words)
{
std::cout << word.c_str() << " ";
}
</pre><br />
<span style="color: #3d85c6; font-family: 'Courier New', Courier, monospace;"><b>auto </b></span>takes care of the type for us so we don't have to type out the entire iterator, and the range-based for-loop takes care of the initialization, comparison, and incrementing of the variable. On top of that, the range-based for-loop takes care of giving us the value pointed to by the iterator itself, so we don't have to dereference the iterator to get the string it points to. This means instead of <span style="font-family: 'Courier New', Courier, monospace;"><b>(*word).c_str()</b></span> we can just do <span style="font-family: 'Courier New', Courier, monospace;"><b>word.c_str()</b></span>.<br />
<br />
Also, for those of you who use Visual Studio, the good news is that Visual Studio 11 will have support for range-based for-loops. It was reported in September that it would not have support for it, but after people complained for months about it, it looks like Microsoft decided to put some more work into their compiler. If you would like to try it out in Visual Studio the VS11 Beta is out and supports it: <a href="http://blogs.msdn.com/b/vcblog/archive/2012/02/29/10272778.aspx">http://blogs.msdn.com/b/vcblog/archive/2012/02/29/10272778.aspx</a><br />
<br />
I have noticed however that the IDE doesn't properly recognize it, and will give you warnings if you hover over parts of the for-loop, but it does compile and run. I'm sure this is something they'll have fixed in the final version. Regardless, VS11 does not support nearly as much of C++11 as other compilers like GCC, which are free, and I'm not sure I could restrict myself to a compiler that would restrict my learning and development as a programmer. But, I sure do love the IDE of Visual Studio, and I'm going to miss that.Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com1Denver, CO, USA39.737567 -104.984717939.5422015 -105.3005749 39.9329325 -104.66886090000001tag:blogger.com,1999:blog-6184383319550035753.post-88822381165707517152012-02-11T22:11:00.000-07:002012-04-20T07:23:04.355-06:00Game Engine Architecture, C#Here's the same architecture as my last two posts, but this time in C# (the last two were in Scala and C++).<br />
<br />
<pre class="brush: csharp">using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace MessagingInCSharp
{
class Program
{
static void Main( string[] args )
{
// Create a scene manager
SceneManager sceneMgr = new SceneManager();
// Have scene manager create an entity for us, which
// automatically puts the object into the scene as well
Entity myEntity = sceneMgr.CreateEntity();
// Create a render component
RenderComponent renderComp = new RenderComponent();
// Attach render component to the entity we made
myEntity.AddComponent(renderComp);
// Set 'myEntity' position to (1, 2, 3)
MsgSetPosition msgSetPos = new MsgSetPosition(myEntity.uniqueID, 1.0f, 2.0f, 3.0f);
sceneMgr.SendMessage(msgSetPos);
Console.WriteLine("Position set to (1, 2, 3) on entity with ID: " + myEntity.uniqueID);
Console.WriteLine("Retreiving position from entity with ID: " + myEntity.uniqueID);
// Get 'myEntity' position to verify it was set properly
MsgGetPosition msgGetPos = new MsgGetPosition(myEntity.uniqueID);
sceneMgr.SendMessage(msgGetPos);
Console.WriteLine("X: " + msgGetPos.x);
Console.WriteLine("Y: " + msgGetPos.y);
Console.WriteLine("Z: " + msgGetPos.z);
}
}
public enum MessageType
{
SetPosition,
GetPosition
}
public class Vector3
{
public float x = 0.0f;
public float y = 0.0f;
public float z = 0.0f;
}
public class BaseMessage
{
public int destEntityID;
public MessageType messageType;
protected BaseMessage( int destinationEntityID, MessageType messageType )
{
this.destEntityID = destinationEntityID;
this.messageType = messageType;
}
}
public class PositionMessage : BaseMessage
{
public float x;
public float y;
public float z;
protected PositionMessage( int destinationEntityID, MessageType messageType,
float X = 0.0f, float Y = 0.0f, float Z = 0.0f) :
base(destinationEntityID, messageType)
{
this.x = X;
this.y = Y;
this.z = Z;
}
}
public class MsgSetPosition : PositionMessage
{
public MsgSetPosition( int destinationEntityID, float X, float Y, float Z ) :
base(destinationEntityID, MessageType.SetPosition, X, Y, Z)
{}
}
public class MsgGetPosition : PositionMessage
{
public MsgGetPosition( int destinationEntityID) :
base(destinationEntityID, MessageType.GetPosition, 0.0f, 0.0f, 0.0f)
{}
}
public abstract class BaseComponent
{
public virtual bool SendMessage( BaseMessage msg )
{
return false;
}
}
public class RenderComponent : BaseComponent
{
public override bool SendMessage( BaseMessage msg )
{
// Entity has a switch for any messages it cares about
switch (msg.messageType)
{
case MessageType.SetPosition:
{
// Update render mesh position/translation
Console.WriteLine("RenderComponent handling SetPosition");
}
break;
default:
return base.SendMessage(msg);
}
return true;
}
}
public class Entity
{
public int uniqueID;
public int UniqueID
{
get { return this.uniqueID; }
set { this.uniqueID = value; }
}
private Vector3 position = new Vector3();
private List<BaseComponent> components = new List<BaseComponent>();
public Entity( int uniqueID )
{
this.uniqueID = uniqueID;
}
public void AddComponent( BaseComponent component )
{
this.components.Add(component);
}
public bool SendMessage( BaseMessage msg )
{
bool messageHandled = false;
// Entity has a switch for any messages it cares about
switch (msg.messageType)
{
case MessageType.SetPosition:
{
MsgSetPosition msgSetPos = msg as MsgSetPosition;
position.x = msgSetPos.x;
position.y = msgSetPos.y;
position.z = msgSetPos.z;
messageHandled = true;
Console.WriteLine("Entity handled SetPosition");
}
break;
case MessageType.GetPosition:
{
MsgGetPosition msgGetPos = msg as MsgGetPosition;
msgGetPos.x = position.x;
msgGetPos.y = position.y;
msgGetPos.z = position.z;
messageHandled = true;
Console.WriteLine("Entity handled GetPosition");
}
break;
default:
return PassMessageToComponents(msg);
}
// If the entity didn't handle the message but the component
// did, we return true to signify it was handled by something.
messageHandled |= PassMessageToComponents(msg);
return messageHandled;
}
private bool PassMessageToComponents( BaseMessage msg )
{
bool messageHandled = false;
this.components.ForEach(c => messageHandled |= c.SendMessage(msg) );
return messageHandled;
}
}
public class SceneManager
{
private Dictionary<int, Entity> entities = new Dictionary<int,Entity>();
private static int nextEntityID = 0;
// Returns true if the entity or any components handled the message
public bool SendMessage( BaseMessage msg )
{
// We look for the entity in the scene by its ID
Entity entity;
if ( entities.TryGetValue(msg.destEntityID, out entity) )
{
// Entity was found, so send it the message
return entity.SendMessage(msg);
}
// Entity with the specified ID wasn't found
return false;
}
public Entity CreateEntity()
{
Entity newEntity = new Entity(SceneManager.nextEntityID++);
entities.Add(newEntity.UniqueID, newEntity);
return newEntity;
}
}
}
</pre>Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0tag:blogger.com,1999:blog-6184383319550035753.post-6653629270298884402012-02-11T00:59:00.001-07:002013-02-25T22:49:04.598-07:00Game Engine Architecture, now in ScalaIn my previous post I discussed game engine architecture, object<->component hierarchy, etc. Here's the sample architecture as the last post, but instead of C++ this version is written in Scala. One thing worth noting, we get identical functionality in this Scala example, with 35% less code!<br />
<br />
<pre class="brush: csharp">package MessagingInScala
object GameMessageType extends Enumeration {
type GameMessageType = Value
val SetPosition = Value
val GetPosition = Value
}
import GameMessageType._
class Vector3(var x: Float, var y: Float, var z: Float)
abstract class GameMessage (val destinationID: Int) {
def messageType: GameMessageType
}
abstract class PositionMessage (destinationID: Int,
var x: Float, var y: Float,
var z: Float) extends GameMessage(destinationID) {
}
class MsgSetPosition(destinationID: Int,
x: Float, y: Float,
z: Float) extends PositionMessage(destinationID, x, y, z) {
override val messageType = SetPosition
}
object MsgSetPosition {
def Apply(destinationID: Int,
x: Float, y: Float,
z: Float) = new MsgSetPosition(destinationID, x, y, z)
}
class MsgGetPosition(destinationID: Int) extends PositionMessage(destinationID, 0.0f, 0.0f, 0.0f) {
val messageType = GetPosition
}
object MsgGetPosition {
def Apply(destinationID: Int) = new MsgGetPosition(destinationID)
}
abstract class BaseComponent {
def SendMessage(message: GameMessage) = false
}
class RenderComponent extends BaseComponent {
override def SendMessage(message: GameMessage): Boolean = {
message.messageType match {
case GameMessageType.SetPosition => {
// Update render mesh position
println("RenderComponent received SetPosition")
true // Return value
}
case _ => super.SendMessage(message)
}
}
}
class Entity(ID: Int) {
private var Components: List[BaseComponent] = List()
var position: Vector3 = new Vector3(0.0f, 0.0f, 0.0f)
val uniqueID: Int = ID
def AddComponent(component: BaseComponent) {
Components = component :: Components
}
def SendMessage(message: GameMessage): Boolean = {
message.messageType match {
case GameMessageType.SetPosition => {
println("Entity received SetPosition")
var msgSetPos: MsgSetPosition = message.asInstanceOf[MsgSetPosition]
position.x = msgSetPos.x
position.y = msgSetPos.y
position.z = msgSetPos.z
PassMessageToComponents(message) // This is also the return value
}
case GameMessageType.GetPosition => {
println("Entity received GetPosition")
var msgGetPos: MsgGetPosition = message.asInstanceOf[MsgGetPosition]
msgGetPos.x = position.x
msgGetPos.y = position.y
msgGetPos.z = position.z
PassMessageToComponents(message) // This is also the return value
}
case _ => PassMessageToComponents(message) // This is also the return value
}
}
def PassMessageToComponents(message: GameMessage): Boolean = {
var messageHandled = false
Components.foreach(c => {
messageHandled |= c.SendMessage(message)
})
messageHandled
}
}
object Entity {
var nextUUID: Int = 0
def apply() = new Entity(nextUUID + 1)
}
class SceneManager {
// You don't need to type the entire HashMap path like this, I'm
// doing this so the reader understands this is not a Java HashMap
var entities: Map[Int, Entity] = Map.empty[Int, Entity]
def SendMessage(message: GameMessage): Boolean = {
if ( entities.contains(message.destinationID) ) {
entities(message.destinationID).SendMessage(message)
} else {
false
}
}
def CreateEntity(): Entity = {
val newEntity: Entity = Entity()
entities += newEntity.uniqueID -> newEntity
newEntity
}
}
object Main extends App {
val sceneMgr: SceneManager = new SceneManager
val testEntity = sceneMgr.CreateEntity()
val testRenderComp = new RenderComponent
testEntity.AddComponent(testRenderComp)
val msgSetPos: MsgSetPosition = new MsgSetPosition(testEntity.uniqueID, 1.0f, 2.0f, 3.0f)
sceneMgr.SendMessage(msgSetPos)
println("Position set to (1, 2, 3) on entity with ID " + testEntity.uniqueID)
println("Retreiving position from object with ID: " + testEntity.uniqueID)
val msgGetPos: MsgGetPosition = new MsgGetPosition(testEntity.uniqueID)
sceneMgr.SendMessage(msgGetPos)
println("X: " + msgGetPos.x)
println("Y: " + msgGetPos.y)
println("Z: " + msgGetPos.z)
}
</pre>
Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com1tag:blogger.com,1999:blog-6184383319550035753.post-1460423871270236302012-02-09T00:13:00.002-07:002012-05-21T00:04:27.978-06:00Game Engine Architecture, C++I recently saw a question on Stack Overflow about engine architecture, specifically how to layout systems and communicate between them. My favorite engine architecture by far is an object<->component architecture. I posted a full working code sample as an answer to the question, along with details. <a href="http://gamedev.stackexchange.com/questions/23533/interaction-between-engine-parts/23578#23578" target="_blank">Here's the link to the question</a>, if you don't wish to follow the link, here's the full answer along with code. Enjoy!<br />
<br />
<br />
<br />
<br />
My favorite game engine structure is the interface and object<->component model using messaging for communication between almost all parts.<br />
<br />
You have multiple interfaces for main engine parts such as your scene manager, resource loader, audio, renderer, physics, etc.<br />
<br />
I have the scene manager in charge of all objects in the 3D scene/world.<br />
<br />
Object is a very atomic class, containing only a few things that are common to almost everything in your scene, in my engine the object class holds only position, rotation, a list of components, and a unique ID. Every object's ID is generated by a static int, so that no two objects will every have the same ID, this allows you to send messages to an object by its ID, rather than having to have a pointer to the object.<br />
<br />
The list of components on the object is what gives that objects is main properties. For example, for something that you can see in the 3D world, you would give your object a render component that contains the information about the render mesh. If you want an object to have physics you would give it a physics component. If you want something to act as a camera, give it a camera component. The list of components can go on and on.<br />
<br />
Communication between interfaces, objects, and components is key. In my engine I have a generic message class that contains only a unique ID, and a message type ID. The unique ID is the ID of the object you want the message to go to, and the message type ID is used by the object receiving the message so it knows what type of message it is.<br />
<br />
Objects can handle the message if they need, and they can pass the message on to each of their components, and components will often do important things with the message. For example, if you want to change and object's position you send the object a SetPosition message, the object may update its position variable when it gets the message, but the render component may need to message to update the position of the render mesh, and the physics component may need the message to update the physics body's position.<br />
<br />
Here is a very simple layout of scene manager, object, and component, and message flow, that I whipped up in about an hour, written in C++. When run it sets the position on an object, and the message passes through the render component, then retrieves the position from the object. Enjoy!<br />
<br />
<pre class="brush: csharp">#include <iostream>
#include <stdio.h>
#include <list>
#include <map>
using namespace std;
struct Vector3
{
public:
Vector3() : x(0.0f), y(0.0f), z(0.0f)
{}
float x, y, z;
};
enum eMessageType
{
SetPosition,
GetPosition,
};
class BaseMessage
{
protected: // Abstract class, constructor is protected
BaseMessage(int destinationObjectID, eMessageType messageTypeID)
: m_destObjectID(destinationObjectID)
, m_messageTypeID(messageTypeID)
{}
public: // Normally this isn't public, just doing it to keep code small
int m_destObjectID;
eMessageType m_messageTypeID;
};
class PositionMessage : public BaseMessage
{
protected: // Abstract class, constructor is protected
PositionMessage(int destinationObjectID, eMessageType messageTypeID,
float X = 0.0f, float Y = 0.0f, float Z = 0.0f)
: BaseMessage(destinationObjectID, messageTypeID)
, x(X)
, y(Y)
, z(Z)
{
}
public:
float x, y, z;
};
class MsgSetPosition : public PositionMessage
{
public:
MsgSetPosition(int destinationObjectID, float X, float Y, float Z)
: PositionMessage(destinationObjectID, SetPosition, X, Y, Z)
{}
};
class MsgGetPosition : public PositionMessage
{
public:
MsgGetPosition(int destinationObjectID)
: PositionMessage(destinationObjectID, GetPosition)
{}
};
class BaseComponent
{
public:
virtual bool SendMessage(BaseMessage* msg) { return false; }
};
class RenderComponent : public BaseComponent
{
public:
/*override*/ bool SendMessage(BaseMessage* msg)
{
switch(msg->m_messageTypeID)
{
case SetPosition:
{
// Update render mesh position/translation
cout << "RenderComponent handling SetPosition\n";
}
break;
default:
return BaseComponent::SendMessage(msg);
}
return true;
}
};
class Object
{
public:
Object(int uniqueID)
: m_UniqueID(uniqueID)
{
}
int GetObjectID() const { return m_UniqueID; }
void AddComponent(BaseComponent* comp)
{
m_Components.push_back(comp);
}
bool SendMessage(BaseMessage* msg)
{
bool messageHandled = false;
// Object has a switch for any messages it cares about
switch(msg->m_messageTypeID)
{
case SetPosition:
{
MsgSetPosition* msgSetPos = static_cast<MsgSetPosition*>(msg);
m_Position.x = msgSetPos->x;
m_Position.y = msgSetPos->y;
m_Position.z = msgSetPos->z;
messageHandled = true;
cout << "Object handled SetPosition\n";
}
break;
case GetPosition:
{
MsgGetPosition* msgSetPos = static_cast<MsgGetPosition*>(msg);
msgSetPos->x = m_Position.x;
msgSetPos->y = m_Position.y;
msgSetPos->z = m_Position.z;
messageHandled = true;
cout << "Object handling GetPosition\n";
}
break;
default:
return PassMessageToComponents(msg);
}
// If the object didn't handle the message but the component
// did, we return true to signify it was handled by something.
messageHandled |= PassMessageToComponents(msg);
return messageHandled;
}
private: // Methods
bool PassMessageToComponents(BaseMessage* msg)
{
bool messageHandled = false;
std::list<BaseComponent*>::iterator compIt = m_Components.begin();
for ( compIt; compIt != m_Components.end(); ++compIt )
{
messageHandled |= (*compIt)->SendMessage(msg);
}
return messageHandled;
}
private: // Members
int m_UniqueID;
std::list<BaseComponent*> m_Components;
Vector3 m_Position;
};
class SceneManager
{
public:
// Returns true if the object or any components handled the message
bool SendMessage(BaseMessage* msg)
{
// We look for the object in the scene by its ID
std::map<int, Object*>::iterator objIt = m_Objects.find(msg->m_destObjectID);
if ( objIt != m_Objects.end() )
{
// Object was found, so send it the message
return objIt->second->SendMessage(msg);
}
// Object with the specified ID wasn't found
return false;
}
Object* CreateObject()
{
Object* newObj = new Object(nextObjectID++);
m_Objects[newObj->GetObjectID()] = newObj;
return newObj;
}
private:
std::map<int, Object*> m_Objects;
static int nextObjectID;
};
// Initialize our static unique objectID generator
int SceneManager::nextObjectID = 0;
int main()
{
// Create a scene manager
SceneManager sceneMgr;
// Have scene manager create an object for us, which
// automatically puts the object into the scene as well
Object* myObj = sceneMgr.CreateObject();
// Create a render component
RenderComponent* renderComp = new RenderComponent();
// Attach render component to the object we made
myObj->AddComponent(renderComp);
// Set 'myObj' position to (1, 2, 3)
MsgSetPosition msgSetPos(myObj->GetObjectID(), 1.0f, 2.0f, 3.0f);
sceneMgr.SendMessage(&msgSetPos);
cout << "Position set to (1, 2, 3) on object with ID: " << myObj->GetObjectID() << '\n';
cout << "Retreiving position from object with ID: " << myObj->GetObjectID() << '\n';
// Get 'myObj' position to verify it was set properly
MsgGetPosition msgGetPos(myObj->GetObjectID());
sceneMgr.SendMessage(&msgGetPos);
cout << "X: " << msgGetPos.x << '\n';
cout << "Y: " << msgGetPos.y << '\n';
cout << "Z: " << msgGetPos.z << '\n';
}
</pre>Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0tag:blogger.com,1999:blog-6184383319550035753.post-57982241831954264312012-02-07T22:00:00.006-07:002013-03-22T10:11:25.038-06:00LINQ and Lambda in C# 4.0 for cleaner, leaner codeThere are times when less is more. If you want clean and concise code, or if readability is more important than finely tuned high-performance, then LINQ and Lambda expressions might just be for you.<br />
<br />
First let's look at a small code sample that does NOT use LINQ or Lambda that where we want to filter through some physics collision results for objects of a certain ID, and then sort our results by the lower IDs first.<br />
<br />
<pre class="brush: csharp">struct CollisionPair : IComparable, IComparer
{
public int first;
public int second;
// Since we're sorting we'll need to write our own Comparer
int IComparer.Compare( object one, object two )
{
CollisionPair pairOne = (CollisionPair)one;
CollisionPair pairTwo = (CollisionPair)two;
if (pairOne.first < pairTwo.first)
return -1;
else if (pairTwo.first < pairOne.first)
return 1;
else
return 0;
}
// ...and our own comparable
int IComparable.CompareTo( object two )
{
CollisionPair pairTwo = (CollisionPair)two;
if (this.first < pairTwo.first)
return -1;
else if (pairTwo.first < this.first)
return 1;
else
return 0;
}
}
static void Main( string[] args )
{
List&ltCollisionPair&gt collisions = new List&ltCollisionPair&gt
{
new CollisionPair { first = 1, second = 5 },
new CollisionPair { first = 2, second = 3 },
new CollisionPair { first = 5, second = 4 }
};
List&ltCollisionPair&gt sortedCollisionsWithFive = new List&ltCollisionPair&gt();
foreach (CollisionPair c in collisions)
{
if (c.first == 5 || c.second == 5)
{
sortedCollisionsWithFive.Add(c);
}
}
sortedCollisionsWithFive.Sort();
foreach (CollisionPair c in sortedCollisionsWithFive)
{
Console.WriteLine("Collision between " + c.first +
"and " + c.second);
}
}
</pre>
Now let's take a look at what we can do when we use LINQ and Lambda expressions to clean things up a bit.
<br />
<pre class="brush: csharp">struct CollisionPair
{
public int first;
public int second;
}
static void Main( string[] args )
{
List&ltCollisionPair&gt collisions = new List&ltCollisionPair&gt
{
new CollisionPair { first = 1, second = 5 },
new CollisionPair { first = 2, second = 3 },
new CollisionPair { first = 5, second = 4 }
};
(from c in collisions
where ( c.first == 5 || c.second == 5 )
orderby c.first select c).ForEach(c =&gt
Console.WriteLine("Collision between " + c.first +
"and " + c.second));
}
</pre>
So which part is LINQ, and which part is Lambda?
Here's the LINQ part:
<br />
<pre class="brush: csharp">(from c in collisions
where ( c.first == 5 || c.second == 5 )
orderby c.first select c)
</pre>
This loops through 'collisions', and you can reference each element in the container by 'c'. Then it filters the list so only elements with either a first or second ID of 5 remain.
Then it orders the list by the first element, and then selects all elements remaining and creates a list out of them. In this case the list may be hard to see, it's formed by wrapping the entire LINQ expression in parentheses. The sample below might make it easier to see:
<br />
<pre class="brush: csharp">// LINQ
var filteredCollisions = from c in collisions
where ( c.first == 5 || c.second == 5 )
orderby c.first select c
</pre>
And here is the Lambda expression:
<br />
<pre class="brush: csharp">// Lambda
ForEach(c =&gt
Console.WriteLine("Collision between " + c.first +
"and " + c.second));
</pre>
This performs a ForEach on a list, the list formed by the LINQ expression that comes before it in the original code. For each element in the list, it calls each element 'c', and then performs a Console.Writeline on each element.
Here's the original sample, simplified a bit:
<br />
<pre class="brush: csharp">// LINQ
var filteredCollisions = from c in collisions
where ( c.first == 5 || c.second == 5 )
orderby c.first select c
// Lambda
ForEach(c =&gt
Console.WriteLine("Collision between " + c.first +
"and " + c.second));
</pre>
If you want to use LINQ you'll want to make sure to use System.Linq:
<br />
<pre class="brush: csharp">using System.Linq;
</pre>
Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0tag:blogger.com,1999:blog-6184383319550035753.post-63000788450083075952011-12-28T17:32:00.002-07:002011-12-28T17:33:48.433-07:00QuickStart Engine v0.26 Preview, Nuclex GUIFor a long time now I've wanted a single GUI in the QuickStart Engine's demo, to make things easier to learn, and over the last few weeks I've been thinking that if I am going to go through the trouble of setting up a GUI for the demo that I might as well setup the GUI such that the user could put it in their own games. However programming a full featured GUI is a very large task, the Nuclex GUI framework alone has almost as many code files as the QuickStart Engine! There was really no need to write my own GUI so I decided to find a GUI framework suitable to be used in C#, XNA, and games, and I believe I've found that with the <a href="http://nuclexframework.codeplex.com/wikipage?title=Nuclex.UserInterface&referringTitle=Documentation" target="_blank">Nuclex GUI framework</a>.<br />
<br />
Here's a screenshot of a simple draggable window in the game with a couple of buttons.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-BXPVnwZj518/Tvu09oFOwvI/AAAAAAAAAFw/KYIBIBUtWJM/s1600/QSGUI.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="358" src="http://3.bp.blogspot.com/-BXPVnwZj518/Tvu09oFOwvI/AAAAAAAAAFw/KYIBIBUtWJM/s640/QSGUI.jpg" width="640" /></a></div><br />
Before this is released I'll want to expose simple ways of connecting the GUI to a game (for example, letting buttons send game messages might be handy), and I would also like to be able to control the transparency of the window. I would like to just include the Nuclex binary files (.dlls) in the project rather than include the Nuclex GUI sourcecode, but it looks like I might have to make some changes to get the transparency stuff that I want.Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0tag:blogger.com,1999:blog-6184383319550035753.post-83909886914693433672011-12-15T19:59:00.003-07:002012-04-20T07:18:18.650-06:00QuickStart Game Engine v0.25 Preview: Buoyancy/Density PhysicsI'm currently working on v0.25 of the QuickStart Game Engine, which will include a handful of performance enhancements, but most of the work has gone into a new component called WaterVolumePhysicsComponent. This component lets you describe a volumetric region in which water physics will be applied to any dynamic physics body, this means that water will now apply drag to anything within it, it will apply a weight to objects as they leave the water (because they're still "wet"), and it will take into account the density differences between the water and the physics body, allowing less dense entities to float, and denser entities to sink. The density differences between the body and water will also determine if the entity just barely sits near the top of the water, or if it's incredibly light it will float almost entirely on top of the water.<br />
<br />
In previous versions of the engine there has been a yellow sphere that could be fired by pressing spacebar, in the new demo there will be two new spheres, a blue one fired by pressing Left Ctrl, and a red one fired by pressing Left Shift. The blue sphere will be extremely light, letting it rise very quickly out of the water and float almost entirely on top of the water, the yellow sphere will be medium density which is slightly less dense than water, letting it float to the top but not sit as high above the water as the blue sphere, and the red sphere will be very heavy and dense, letting it sink to the bottom of the water.<br />
<br />
Density is really all that matters in terms of buoyancy in the water, but it also affects the amount of force and momentum an object has; All 3 spheres are the same size, but different densities, so each sphere weighs much differently than another. If you fire a blue sphere at one of the wooden crates in the demo, it doesn't have enough weight to move the crate almost at all, but the yellow sphere can give it a small nudge because it's a higher weight, and the red sphere can knock the crates around pretty good because they're much heavier than the crates. It is fun to fire the different spheres at things and watch how they act differently in the water.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhKMUbmcn-6R-4qRokOoMi4m4MtiYsqO1kyAoibFN0HxG2u6ba2LbFs2ItZFSpgxReTuCc7d-nKdWbDaGC9N4KyaTFCnNJO5itnQINxKmW-M0UJiBqJwSz3pLii3Jvw7MGGOR0qbNVGRCw/s1600/QSBuoyancy.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="480" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhKMUbmcn-6R-4qRokOoMi4m4MtiYsqO1kyAoibFN0HxG2u6ba2LbFs2ItZFSpgxReTuCc7d-nKdWbDaGC9N4KyaTFCnNJO5itnQINxKmW-M0UJiBqJwSz3pLii3Jvw7MGGOR0qbNVGRCw/s640/QSBuoyancy.jpg" width="640" /></a></div><br />
<br />
<br />
I expect version 0.25 to be released in the next week or two.Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0tag:blogger.com,1999:blog-6184383319550035753.post-50092503058803738672011-12-07T00:36:00.010-07:002011-12-28T22:22:56.551-07:00XNA 4.0 == Me pulling my hair outXNA 4.0 has been out over a year now, but I've only just recently had the time to use it. Shawn Hargreaves from the XNA Development Team explained how a lot of things would be broken by XNA 4.0 (although these were all good things in their opinion), and boy he wasn't kidding. As a result of the changes, here's what I've gone through in my game engine trying to convert it from XNA 3.1 to XNA 4.0. <a href="http://blogs.msdn.com/b/shawnhar/archive/2010/03/16/breaking-changes-in-xna-game-studio-4-0.aspx" target="_blank">Here's a link with a summary of the breaking changes</a>.<br />
<br />
1.) Clipping planes are no longer supported within XNA. Clipping planes were supported directly by DX9 hardware, but not DX10 hardware, so in an effort to be forward looking, support was removed from XNA 4.0. I had to put all clipping plane calculations into my shaders. This means every single mesh that could be rendered in a scene with water (pretty much everything) had to have clipping plane stuff put into the shaders. Annoyance factor (6 out of 10). <a href="http://forums.create.msdn.com/forums/t/56786.aspx" target="_blank">Read more here</a>.<br />
<br />
3.) Point-sprites are no longer supported, also because they're not supported by DX10. This affects particle systems, which often used point-sprites to represent particles. Using a point sprite meant 1 vertex per particle, but without a point sprite you need at least 4 vertices to represent a square polygon (quad). This meant having to add an index buffer to the particle emitters, and changing the way particles are created and updated. It also has performance implications, non-rotating particles render a bit slower on average than they used to, but rotating particles actually perform better, so it's not a total loss.<br />
Annoyance factor (4 out of 10). <a href="http://blogs.msdn.com/b/shawnhar/archive/2010/03/22/point-sprites-in-xna-game-studio-4-0.aspx" target="_blank">Read more here</a>.<br />
<br />
3.) RenderTarget2D was changed so that it derives from Texture2D and you can no longer call .GetTexture() on it, additionally the clearing of render targets was changed which forced me to shift around some code. Annoyance factor (2 out of 10). <a href="http://blogs.msdn.com/b/shawnhar/archive/2010/03/26/rendertarget-changes-in-xna-game-studio-4-0.aspx" target="_blank">Read more here</a>.<br />
<br />
4.) Number of primitives that can be drawn in a single draw call has been limited to 1,045,575. As part of my visual debugging I had a way to render a small line for each vertex of the terrain heightfield, however on a map that is 1024x1024, plus a few other objects on screen, that is enough to push the vertex count past the new limit. This one actually isn't that annoying for me, other than the fact I now have to fix it, but apparently some DX10 cards don't allow more than this per draw call so it's probably best that I fixed this anyway. Annoyance factor (2 out of 10).<br />
<br />
5.) The quality of SpriteFonts has been decreased. It wasn't really a performance problem in the past, so I'm assuming this was done for performance reasons with Windows Phone 7. <a href="http://www.nuclex.org/blog/gamedev/113-xna-sprite-font-quality" target="_blank">Read more here</a> for a comparison of XNA 3.1, and XNA 4.0. Additionally the linked article provides a font processor you can use if you would like to maintain the high quality sprite fonts. Annoyance factor (1 out of 10), annoying that quality needlessly drops in my engine, but at least I didn't have to do any work to get it running properly.<br />
<br />
6.) Here's the one that gets me the most. In an effort to unify hardware requirements for games, XNA now forces all games to run in one of two graphics profiles, called 'Reach' and 'HiDef'. The problem is that 'HiDef' is only DX10 and higher, and while 'Reach' supports DX9, it had to make sure it supported almost all DX9, so all kinds of stuff you could do in DX9 with XNA 3.1 is now gone. So I now have three choices with my game engine (that I can think of).<br />
<ul><li>I can use the 'Reach' requirement only for the engine, and I lose support for many graphics techniques that have been used for 6+ years, and lose features that I've had working in the engine for years.</li>
<li>I can use the 'HiDef' requirement only, and drop support for all DX9 hardware (about 40% of the GPUs out there at this time). This seems ridiculous to me knowing that everything in my engine runs fine on about 80% of DX9 GPUs.</li>
<li>I can try and use both of the requirement types, which means I have to duplicate all of the game engine's assets so it can cover both sets of assets (one in each type of graphics profile). This puts a huge burden on anyone making a game using the engine that wants to also support both formats.</li>
</ul><div>All of these options are pretty bad IMO. Here are the problems I'm having with the new 'Reach' format they've imposed.</div><div><ul><li>They dropped support for most texture formats that you would need to do self-shadowing (meshes casting shadows on to other meshes). I have to entirely re-write my self-shadowing implementation to not use depth shadow maps if I want to support the 'Reach' graphics profile. <a href="http://forums.create.msdn.com/forums/p/62145/382485.aspx" target="_blank">Read more here</a>.</li>
<li>They also dropped support for texture sizes larger than 2048x2048, which many DX9 cards support. This means that shadow quality based on standard depth shadow mapping will be cut to 1/4th of what it could be in XNA 3.1.</li>
<li>They dropped support for 32-bit index buffers, which means that for large terrains I now have to render it in smaller chunks. The sweet spot I had found for most machines was 512x512 chunks for terrain, which limited how many frustum against terrain axis-aligned bounding box checks I had to do, and limited the amount of draw calls that were being made. The largest that can be done with 16-bit index buffers is 128x128 chunks. That means if my camera previous had four 512x512 chunks in view, I had four draw calls, and now I would have up to 64 128x128 chunks in view. In reality it would probably be less than 64 chunks because the smaller chunks would give more granularity to the frustum checks, but overall I would have many more frustum checks, putting more work on the CPU, and more draw calls but potentially less geometry, which depending on the situation could put more or less work on the GPU.</li>
<li>They dropped support for non-power-of-two texture sizes, which means the quality of the water reflection and refractions is either going to drop, or it will be higher than it needs to be, hurting performance.</li>
</ul><div>There are likely other restrictions I haven't run into yet, but I'm sure others running into problems are also bothered by this. I'll admit it has the one major upside, and that is no longer having to worry about something working on a developer's PC and not on an end-user's PC. You either meet the requirements of the graphics profile or you don't, that simple. Sadly I believe they set the requirements for the 'Reach' profile as low as they did for Window Phone 7 development, at the expense of killing features for a large percentage of DX9 users. Honestly I'm not surprised by this, it's somewhat standard for Microsoft to make a change that benefits them, and tell everyone else to deal with it. This will make Windows Phone 7 development easier, give people more reasons to upgrade to DX10 or DX11 (both Microsoft proprietary formats), and those newer GPUs give customers more reasons to upgrade to Windows 7 or the upcoming Windows 8. I do feel that Microsoft is slowly trying to pull XNA away from PC development, they're continuing to restrict the ability of developers to use XNA to create a PC-only game.</div></div><div><br />
</div><div>Anyway I'm going to mull over things for another day or so before I decide whether to rework a handful of features to try and get things working on the 'Reach' profile, or if I just abandon DX9 support all together, which would be painful now but would matter little within the next couple of years as DX9 becomes a distant memory. Luckily my engine is open-source and not making me any money, so I don't have to worry about angering any potential paying customers by telling them that if they use the engine that their game can't run on DX9 hardware.</div><div><br />
</div><div>Annoyance factor (9 out of 10)!</div><br />
<a href="http://blogs.msdn.com/b/shawnhar/archive/2010/03/12/reach-vs-hidef.aspx" target="_blank">Read more here</a> about the 'Reach' vs 'HiDef' changes in XNA.Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0tag:blogger.com,1999:blog-6184383319550035753.post-10491407265893161792011-12-06T09:53:00.002-07:002012-04-20T07:15:30.096-06:00QuickStart Engine v0.24 coming soonI've been hard at work on the next version of the QuickStart Engine, trying to get some much needed features into the engine while I still have some free time. I predict I'll have this next version checked in within the next few days.<br />
<br />
Here's my changelist so far:<br />
<ul><li>Messages now have a new member called 'protocol'. This gives the message properties so that it can not return after being handled by a single source, but also continue on to other components. It also lets the sender and handler know the intent of the message, for example, a SetPosition message has 'Broadcast' type, which means it is going to be broadcasting a change from the sender of the message to any component that is listening. In contrast, a GetPosition message has 'Request' type, which means only a single component should handle the message, and the handler is expected to return new information in the message. And finally there is the 'Accumulate' method, which allows the user to send the message to multiple components, and each one will have a chance to make changes or add to the data.</li>
<li>ViewMatrix, ProjectionMatrix, and ViewFrustum data members in BaseEntity were moved to the CameraComponent class. This will save on memory by not having these exist on every entity, and also will remove clutter from the BaseEntity class. This did cause some changes to the variables passed through various functions, mostly in the GraphicsSystem class.</li>
<li>When using the QSGame.QueueMessage method message protocol is enforced, to prevent the user from sending a request message, which would fail because request messages must immediately return results to the caller.</li>
<li>Changed the default physics deactivation values for the engine, added constants for this that can be changed based on the game and scale used. This will result in a better framerate when there are lots of dynamic physics objects in a scene.</li>
<li>Entities and components now receive a call to a new function called 'AddedToScene', which is called whenever the entity is added to a scene. This allows the entity and components to do things that normally required a game message to be sent, which couldn't be done until an entity was in the scene.</li>
<li>LightComponents no longer need to have InitializeLightDirection() called manually on them to properly rotate the light, this is now done automatically within the component.</li>
<li>Entities with SkyComponents no longer need to be manually attached to the camera, they will now handle this on their own.</li>
<li>GeometricPrimitiveType enum uses 'Box' now instead of 'Cube', to match the ShapeType enum.</li>
<li>Terrain (which was a class derived from BaseEntity) is now TerrainComponent and is derived from BaseComponent. This makes it easier to load Terrain through the new loading method (XML templates).</li>
<li>Constant movement component now allows for a constant direction movement, not just sine-wave type of movements.</li>
<li>The current render camera is now notified of any changes to graphics settings.</li>
</ul><b>Bug fixes:</b><br />
<ul><li>Light direction shader parameter now has a correct .W value of 1.0 rather than 0.0</li>
<li>Cameras will now automatically assume the aspect ratio of the viewport/window rather than defaulting to a specific preset value (unless you explicitly define one).</li>
</ul><br />
<b>Features:</b><br />
<ul><li>Entities and Components can now be loaded entirely from XML definition files. This is a large step towards supporting a level editor that can save out entire scenes in a compact format. In the mean time it means that designer types can create entities through XML rather than C#.</li>
<li>Multi-sampling anti-aliasing should work once again. Edit your settings.xml and set "IsMultiSampling" to true to use it, but be aware on PC it will generally cut the framerate in half.</li>
<li>Texturing and normal mapping now work properly. Demo has been setup with a couple of textured and normal mapped entities.</li>
<li>Ability to create physics box and sphere shapes based on the vertices in a model. This allows you take a model and wrap it in box or sphere physics. Previous this only worked with TriangleMesh shapes which are static so their uses are limited.</li>
<li>The full component list stored in BaseEntity is now a dictionary with a 'key' of ComponentType. This allows programmers to easily get a component from an Entity for direct access as an alternative to creating and sending game messages.</li>
<li>New physics class for Terrain, called TerrainPhysicsComponent. This allowed us to move all heightfield specific physics out of the PhysicsComponent and into its own class. This also makes it easier to load terrain.</li>
</ul>Here's a sample screenshot showing texturing works. And every entity in this scene is now loaded almost entirely from XML files rather than code.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj0rkYZvdpjglmGTOM9AaFeFFoBaR2u6ijZO_cY35JiYXXmIfmkeyMnep3EQCaRSdwDaafoU4Almy5ckPKC9rO4Ansz9pJAb4isCjVAFI0dNdk-UkF4MTM7iBbAu0lTWqPqVSLKdVjayQ8/s1600/QSTexturing.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="480" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj0rkYZvdpjglmGTOM9AaFeFFoBaR2u6ijZO_cY35JiYXXmIfmkeyMnep3EQCaRSdwDaafoU4Almy5ckPKC9rO4Ansz9pJAb4isCjVAFI0dNdk-UkF4MTM7iBbAu0lTWqPqVSLKdVjayQ8/s640/QSTexturing.jpg" width="640" /></a></div>Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0tag:blogger.com,1999:blog-6184383319550035753.post-57457819105658610632011-11-29T16:20:00.002-07:002011-12-28T17:34:54.069-07:00QuickStart Engine v0.23 released!For a year my open-source game engine for XNA had been incompatible with the newest version of XNA (version 4.0). With work and other responsibilities I hadn't had the time to get to updating it until recently. So for anyone interested in a basic game engine for XNA 4.0, here you go:<br />
<a href="http://quickstartengine.codeplex.com/">http://quickstartengine.codeplex.com/</a><br />
<br />
If you just want to try out the demo program, try this link:<br />
<a href="http://quickstartengine.codeplex.com/releases/view/77590#DownloadId=308132">http://quickstartengine.codeplex.com/releases/view/77590#DownloadId=308132</a> <br />
<br />
These are screenshots from v0.22, but it's visually almost identical to v0.23<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://i3.codeplex.com/Download?ProjectName=QuickStartEngine&DownloadId=119689" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="398" src="http://i3.codeplex.com/Download?ProjectName=QuickStartEngine&DownloadId=119689" width="640" /></a></div><br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://i3.codeplex.com/Download?ProjectName=QuickStartEngine&DownloadId=119690" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="398" src="http://i3.codeplex.com/Download?ProjectName=QuickStartEngine&DownloadId=119690" width="640" /></a></div>Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0tag:blogger.com,1999:blog-6184383319550035753.post-49170961285679277112011-11-25T18:29:00.001-07:002011-12-28T17:34:34.350-07:00Converting the Quickstart Game Engine to XNA 4.0Microsoft made a lot of changes to XNA between 3.1 and 4.0, and only recently have I had the time to look into converting the <a href="http://quickstartengine.codeplex.com/" target="_blank">Quickstart Game Engine</a> to run in XNA 4.0.<br />
<br />
Here's Shawn Hargreaves list of breaking changes (changes that will break the engine) in XNA 4.0:<br />
<a href="http://blogs.msdn.com/b/shawnhar/archive/2010/03/16/breaking-changes-in-xna-game-studio-4-0.aspx">http://blogs.msdn.com/b/shawnhar/archive/2010/03/16/breaking-changes-in-xna-game-studio-4-0.aspx</a> <br />
<br />
Some of these are a real pain, specifically the fact that they got rid of point sprites, which the particle system uses, and clipping planes, which the water planes use to render reflections and refractions.<br />
<br />
Those are the two that I'll be struggling with for the next couple of days, but hopefully I'll soon have the engine running on XNA 4.0. I've also identified some possible significant performance benefits I may implement as well.<br />
<br />
Stay tuned.<br />
<br />
Screenshot from Quickstart Engine 0.22 (running on XNA 3.1):<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://i3.codeplex.com/Download?ProjectName=QuickStartEngine&DownloadId=116413" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="480" src="http://i3.codeplex.com/Download?ProjectName=QuickStartEngine&DownloadId=116413" width="640" /></a></div>Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0tag:blogger.com,1999:blog-6184383319550035753.post-15125687229594829702011-11-18T14:44:00.001-07:002011-12-28T17:34:15.410-07:00Let's Make a Game Engine for XNA 4.0r, Part 5, RenderDescriptions, Vertex Declaration, and everything elseIn Part 4 of this series we covered the Render and Camera Components. RenderComponent uses RenderDescriptions to hold information about its mesh so the RenderManager can render it, and that RenderDescription holds either a Model (which is a standard XNA class), or a GeometricPrimitive (which is part of this engine).<br />
<br />
<b><span style="font-size: large;">GeometricPrimitive</span></b><br />
GeometricPrimitive is a base class I've built into the engine, but it was written by Microsoft's XNA team as part of a sample, as such I'm not going to cover much about it other than the basics. There are 7 files that are part of this system, and I modified each one slightly to be part of the project, if you're creating your own project rather than using the downloaded one you'll want to just copy the GeometricPrimitives directory out of the download project into your project, and you'll need to make sure the namespaces match within each file as well.<br />
<br />
GeometricPrimitive takes a GraphicsDevice as part of its constructor. Based on the shape of the primitive it constructs a VertexBuffer, a list of its verticies, an IndexBuffer, and a list of its indices. Based on those variables we will have enough information to render the primitive. The only changes I made to these classes after putting them into this engine was to remove the #regions, and I pulled the BasicEffect out of the class itself since the RenderManager handles the rendering. Most importantly, I added the enum GeometricPrimitiveType to the GeometricPrimitive.cs file to allow users to use an enum type to create a shape for them:<br />
<pre class="brush: csharp">public enum GeometricPrimitiveType
{
Cube,
Sphere,
Cylinder,
Torus,
Teapot
}
</pre>If you look in the downloaded version of the engine you'll notice a 6th primitive shape called a BezierPrimitive. This isn't used directly, it is used by the TeapotPrimitive.<br />
<br />
Here is a link to the original Geometric Primitives sample if you would like to learn more:<br />
<a href="http://create.msdn.com/en-US/education/catalog/sample/primitives_3d">http://create.msdn.com/en-US/education/catalog/sample/primitives_3d</a><br />
<br />
<br />
<span style="font-family: inherit; font-size: large;"><b>VertexPositionNormal</b></span><br />
<span style="font-family: inherit;">This class is an IVertexType (which is a standard XNA type). When creating a list of vertices you need to have a vertex type, this is the vertex type used by the Geometric Primitives, this file is also from Microsoft's sample. Place VertexPositionNormal.cs in the RenderManager folder. Here's the entire file:</span><br />
<pre class="brush: csharp">using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
namespace SimpleGameEngine.Render
{
/// <summary>
/// Custom vertex type for vertices that have just a
/// position and a normal, without any texture coordinates.
/// </summary>
public struct VertexPositionNormal : IVertexType
{
public Vector3 Position;
public Vector3 Normal;
/// <summary>
/// Constructor.
/// </summary>
public VertexPositionNormal(Vector3 position, Vector3 normal)
{
Position = position;
Normal = normal;
}
/// <summary>
/// A VertexDeclaration object, which contains information about the vertex
/// elements contained within this struct.
/// </summary>
public static readonly VertexDeclaration VertexDeclaration = new VertexDeclaration
(
new VertexElement(0, VertexElementFormat.Vector3, VertexElementUsage.Position, 0),
new VertexElement(12, VertexElementFormat.Vector3, VertexElementUsage.Normal, 0)
);
VertexDeclaration IVertexType.VertexDeclaration
{
get { return VertexPositionNormal.VertexDeclaration; }
}
}
}
</pre><br />
<b><span style="font-size: large;">RenderDescription</span></b><br />
RenderDescription is a data class, it holds no functionality, just holds data that can be passed between a RenderComponent and the RenderManager. Create RenderDescription.cs and place it inside of the RenderManager folder. The data RenderDescription holds is:<br />
<br />
A Model (XNA's Model Class), or a GeometricPrimitive. It shouldn't hold both, the RenderManager will check if the Model exists first, and if it doesn't it will then check for a GeometricPrimitive, there's no reason to use both. This class also holds the worldTransform Matrix. And that's it. Here's the entire file:<br />
<pre class="brush: csharp">using System;
using System.Collections.Generic;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using SimpleGameEngine.GeometricPrimitives;
namespace SimpleGameEngine.Render
{
public class RenderDescription
{
// A render description must contain either a Model, or
// a GeometricPrimitive
public Model model;
public GeometricPrimitive geoPrim;
public Matrix worldTransform = Matrix.Identity;
public RenderDescription()
{
}
}
}
</pre><br />
<b><span style="font-size: large;">EngineCommon</span></b><br />
This is a file that will contain common constants used throughout the project. Create a file called EngineCommon.cs and place it in the main GameEngine folder (same level as Main.cs). Right now this just contains a variable for the name of the default root entity. Here's the entire file:<br />
<pre class="brush: csharp">using System;
using System.Collections.Generic;
using System.Text;
namespace SimpleGameEngine
{
public class EngineCommon
{
public const String RootEntityName = "Root";
}
}
</pre><br />
And that's it for our first milestone. At this point you got a lot of good practice watching the engine come together, and if you made your own files and code as you went along you should know it pretty well. Along the way there was a good chance for a typo on either my or your part, if your project doesn't compile I recommend just using the downloaded version of the engine, and if you want to change things around a little feel free to alter it to your liking, the license on the engine is such that you can do whatever you want with it.<br />
<br />
So let's run the engine (press F5 to build and run attached), and what we should get is two loaded entities, one is the root entity, and the other is a primitive cube in front of the camera.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh4wf3zRwtWlnijJurLnB4HdRnnM55LbmM9tU9738xF1z0KcpIVyJGRV6rrQcNorkW6x9F9k7h8cvjYYIuOmTzArp1zxUbfMZYnGmxvnzb5daOWo9-sr5-x1aw3MLnUMHBR6Lg2kEFlS0U/s1600/firstRenderCube.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="404" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh4wf3zRwtWlnijJurLnB4HdRnnM55LbmM9tU9738xF1z0KcpIVyJGRV6rrQcNorkW6x9F9k7h8cvjYYIuOmTzArp1zxUbfMZYnGmxvnzb5daOWo9-sr5-x1aw3MLnUMHBR6Lg2kEFlS0U/s640/firstRenderCube.jpg" width="640" /></a></div><br />
And there we have it. Now lets reflect back on things a bit. We took an awfully long time to make a program that renders a cube, we could have done it in about 1/10th the time, with much less code. However, the goal wasn't really to make a cube rendering program, what we wanted was the start to a flexible game engine that is extensible and reusable. If you think about it we could very easily change the program to render a stack of cubes, so let's give that a shot. If you remember the place we're temporarily using to load entities into our scene is within the SceneManager, so open that up and look for LoadContent().<br />
<br />
Add this at the bottom of the function (but within the temporary lines comments):<br />
<pre class="brush: csharp">BaseEntity testCube2 = new BaseEntity(this, "Cube2");
testCube2.position = new Vector3(0, -1.01f, -10);
RenderComponent rendComp2 = new RenderComponent(testCube2, GeometricPrimitiveType.Cube);
AddEntityToScene(testCube2);
BaseEntity testCube3 = new BaseEntity(this, "Cube3");
testCube3.position = new Vector3(0, 1.01f, -10);
RenderComponent rendComp3 = new RenderComponent(testCube3, GeometricPrimitiveType.Cube);
AddEntityToScene(testCube3);
</pre><br />
And now we see this:<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjsh9di0I-EEN5PFRRpYDQtLlMidP-4D7eh0utJRH0PSExbkkLFK7X2ntJlc9ru95icHscGNjf93NOtA-V3Hp0klkovgyLqvT2oqL3zvZGpoZoCCxAqw0m4ho4klEacvQgVA1QwEwOc0co/s1600/multiCubes.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="404" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjsh9di0I-EEN5PFRRpYDQtLlMidP-4D7eh0utJRH0PSExbkkLFK7X2ntJlc9ru95icHscGNjf93NOtA-V3Hp0klkovgyLqvT2oqL3zvZGpoZoCCxAqw0m4ho4klEacvQgVA1QwEwOc0co/s640/multiCubes.jpg" width="640" /></a></div><br />
After some new additions to the engine it'll be able to do a lot more than this. From here on I won't be going into as much detail about setting everything up line by line, I will publish new versions of the engine that you can download, and I will go into some detail about new functionality. The biggest reason for this is because it takes a lot longer to blog about making an engine than it does to actually make it. I made this entire engine as you see it now in 7 hours, and it took about 15 hours to blog about it. The idea behind this project is that I will create a simple but extensive framework from which I will be able to create demos and samples that I can post on my blog, and the posted sample and code will relate to each other without me having to describe the entire engine to the use. For example if I want to create a spline cinematic camera demo, and I did it from scratch, there would be a ton of code in there that most people do not care about, now the engine can take place of that code and sit hidden from view so people can concentrate on the math and features behind such a camera system.<br />
<br />
I will keep you guys posted on new versions of the engine, as well as posting samples that use the engine. Thanks for reading!Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0tag:blogger.com,1999:blog-6184383319550035753.post-15125914643376258792011-11-18T10:55:00.003-07:002013-03-09T13:17:35.881-07:00Let's Make a Game Engine for XNA 4.0r, Part 4, RenderComponent and CameraComponentIn <a href="http://nic-gamedev.blogspot.com/2011/11/lets-make-game-engine-for-xna-40r-part_18.html" target="_blank">Part 3</a> of this series we covered BaseEntity and BaseComponent. Entities and Components are really at the heart of gameplay in any object/entity and component-based game engine, for example, in LEGO Universe we had over 110 different types of components, including a scripting component that allowed scripts to do all kinds of custom gameplay. In this post (Part 4) we will create our first two components, RenderComponent, and CameraComponent, and to start with we'll keep them extremely simple. Remember, our first milestone goal is just to render a cube on the screen with the engine.<br />
<br />
<b><span style="font-size: large;">RenderComponent</span></b><br />
Ok, let's start with RenderComponent. First, make sure you derive RenderComponent from BaseComponent:<br />
<pre class="brush: csharp">public class RenderComponent : BaseComponent
</pre>
<br />
And the only two objects this class holds for now is a RenderDescription (which we'll get to see in Part 5), and a Matrix that defines the scale of the render mesh (although we won't implement scale until after the first milestone):<br />
<pre class="brush: csharp">private RenderDescription description;
private Matrix scaleMatrix = Matrix.Identity;
</pre>
Notice we don't have accessors for these. The only time you want an accessor in a component is for data you want other users to be able to access or alter from outside the component. But if we make a script component giving access to these variables is as easy as making an accessor or function.<br />
<br />
Next you'll see that derived components, like derived managers, must handle GetName():<br />
<pre class="brush: csharp">protected override String GetName()
{
return "Render";
}
</pre>
<br />
RenderComponent will start out with two constructors, one in which the user can create a render component based on the name of an asset in the content pipeline, and another in which the user can create a render component based on a geometric primitive:<br />
<pre class="brush: csharp">public RenderComponent(BaseEntity ParentEntity, String ModelName) :
base(ParentEntity)
{
Initialize();
LoadModel(ModelName);
}
public RenderComponent(BaseEntity ParentEntity, GeometricPrimitiveType primitiveType) :
base(ParentEntity)
{
Initialize();
LoadPrimitive(primitiveType);
}
</pre>
Notice the component pass the 'ParentEntity' reference to the base class, which is BaseComponent. BaseComponent stores that reference, and when the derived component calls base.Initilize(), within its own Initialize() method, then BaseComponent attaches the component to the Entity. <br />
<br />
You can see based on which constructor is called we use a function called LoadModel() and pass in the name of the model, or another called LoadPrimitive() and pass in the type of primitive, here are those methods:<br />
<pre class="brush: csharp">private void LoadModel(String modelName)
{
description.model = this.Parent.Manager.Content.Load<model>(modelName);
}
private void LoadPrimitive(GeometricPrimitiveType primitiveType)
{
switch (primitiveType)
{
case GeometricPrimitiveType.Cube:
description.geoPrim = new CubePrimitive(this.Parent.Manager.Game.GraphicsDevice);
break;
case GeometricPrimitiveType.Sphere:
description.geoPrim = new SpherePrimitive(this.Parent.Manager.Game.GraphicsDevice);
break;
case GeometricPrimitiveType.Cylinder:
description.geoPrim = new CylinderPrimitive(this.Parent.Manager.Game.GraphicsDevice);
break;
case GeometricPrimitiveType.Torus:
description.geoPrim = new TorusPrimitive(this.Parent.Manager.Game.GraphicsDevice);
break;
case GeometricPrimitiveType.Teapot:
description.geoPrim = new TeapotPrimitive(this.Parent.Manager.Game.GraphicsDevice);
break;
default:
throw new Exception("LoadPrimitive does not handle this type of GeometricPrimitive. Was a new primitive type made and not handled here?");
}
}
</pre>
Within LoadModel we utilitize the ContentManager to load our asset based on its name. ContentManager can be access from a component by going through the Entity, then SceneManager. And within LoadPrimitive we use an enum of a primitive type to decide which primitive to load. I will go over the GeometricPrimitives briefly in Part 5, there will be no need to go into them in full detail, as I didn't write them, they are extracted from a Microsoft XNA Sample that you can use if you wish to learn about them.<br />
<br />
In our Update() method we make sure our render mesh's worldTransform is updated just in case the position or rotation of the entity changed. Please note that this is not the most efficient way to do this, what would be more efficient is to have components that care about changes to position or rotation listen for those changes, and when a change occurs then update the worldTransform. Maybe I'll do this in a later version of the engine. The worldTransform is a matrix that holds the scale, rotation, and translation (position) of a mesh. This is needed by the shaders to properly render the mesh:<br />
<pre class="brush: csharp">public override void Update(GameTime gameTime)
{
description.worldTransform = this.scaleMatrix * this.Parent.rotation * Matrix.CreateTranslation(this.Parent.position);
}
</pre>
<br />
And finally is our Draw method. Draw is called by XNA's base Game class, and we pass it through to the RenderManager, which calls Draw on all entities to request all of the RenderDescriptions they may have. Having already seen RenderManager in a previous section I won't explain what it does with those RenderDescriptions. But RenderDescriptions are covered in Part 5.<br />
<pre class="brush: csharp">public override void Draw(GameTime gameTime, List<renderdescription> renderDescriptions)
{
// Could do frustum culling here if we wanted to be more efficient.
// We could go a step further and gather the entities within sections of an octree that are
// currently within the view frustum, then skip the frustum check here.
renderDescriptions.Add(description);
}
</renderdescription></pre>
<br />
And that's it for RenderComponent. Here's the entire file:<br />
<pre class="brush: csharp">using System;
using System.Collections.Generic;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using SimpleGameEngine.Entity;
using SimpleGameEngine.Render;
using SimpleGameEngine.GeometricPrimitives;
namespace SimpleGameEngine.Components
{
public class RenderComponent : BaseComponent
{
private RenderDescription description;
private Matrix scaleMatrix = Matrix.Identity;
protected override String GetName()
{
return "Render";
}
public RenderComponent(BaseEntity ParentEntity, String ModelName) :
base(ParentEntity)
{
Initialize();
LoadModel(ModelName);
}
public RenderComponent(BaseEntity ParentEntity, GeometricPrimitiveType primitiveType) :
base(ParentEntity)
{
Initialize();
LoadPrimitive(primitiveType);
}
protected override void Initialize()
{
description = new RenderDescription();
description.worldTransform = this.scaleMatrix * this.Parent.rotation * Matrix.CreateTranslation(this.Parent.position);
base.Initialize();
}
private void LoadModel(String modelName)
{
description.model = this.Parent.Manager.Content.Load<Model>(modelName);
}
private void LoadPrimitive(GeometricPrimitiveType primitiveType)
{
switch (primitiveType)
{
case GeometricPrimitiveType.Cube:
description.geoPrim = new CubePrimitive(this.Parent.Manager.Game.GraphicsDevice);
break;
case GeometricPrimitiveType.Sphere:
description.geoPrim = new SpherePrimitive(this.Parent.Manager.Game.GraphicsDevice);
break;
case GeometricPrimitiveType.Cylinder:
description.geoPrim = new CylinderPrimitive(this.Parent.Manager.Game.GraphicsDevice);
break;
case GeometricPrimitiveType.Torus:
description.geoPrim = new TorusPrimitive(this.Parent.Manager.Game.GraphicsDevice);
break;
case GeometricPrimitiveType.Teapot:
description.geoPrim = new TeapotPrimitive(this.Parent.Manager.Game.GraphicsDevice);
break;
default:
throw new Exception("LoadPrimitive does not handle this type of GeometricPrimitive. Was a new primitive type made and not handled here?");
}
}
public override void Update(GameTime gameTime)
{
description.worldTransform = this.scaleMatrix * this.Parent.rotation * Matrix.CreateTranslation(this.Parent.position);
}
public override void Draw(GameTime gameTime, List<RenderDescription> renderDescriptions)
{
// Could do frustum culling here if we wanted to be more efficient.
// We could go a step further and gather the entities within sections of an octree that are
// currently within the view frustum, then skip the frustum check here.
renderDescriptions.Add(description);
}
}
}
</pre>
<br />
<span style="font-size: large;"><b>CameraComponent</b></span><br />
Next up we have CameraComponent, which at this time does virtually nothing special. You see, to render a basic camera we need position, rotation, and aspect ratio. Position and rotation are part of all entities, existing within BaseEntity, so for now that just leaves aspect ratio as the only thing we need the camera component for. But later on it will do more advanced things.<br />
<br />
Rather than go over each part of such a simple class, I will post the entire file here. The only thing worth noting is that is has an aspectRatio variable which is initializes to be based on the dimensions of the viewport/window.<br />
<br />
<pre class="brush: csharp">using System;
using System.Collections.Generic;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using SimpleGameEngine.Entity;
using SimpleGameEngine.Render;
namespace SimpleGameEngine.Components
{
public class CameraComponent : BaseComponent
{
private float aspectRatio;
public float AspectRatio
{
get { return aspectRatio; }
}
protected override String GetName()
{
return "Camera";
}
public CameraComponent(BaseEntity ParentEntity) :
base(ParentEntity)
{
Initialize();
}
protected override void Initialize()
{
// Default aspect ratio is that of the viewport/window
aspectRatio = this.Parent.Manager.Game.GraphicsDevice.Viewport.AspectRatio;
base.Initialize();
}
}
}
</pre>
<br />
And that's it for Part 4. In <a href="http://nic-gamedev.blogspot.com/2011/11/lets-make-game-engine-for-xna-40r-part_1339.html" target="_blank">Part 5</a> we're going to cover everything that remains for the first milestone for this engine, after which point you should be at the same point as if you had downloaded the engine yourself.Nichttp://www.blogger.com/profile/11938742522409928163noreply@blogger.com0