The Importance of Databases in Game Development

Early in my game development core sequence classes I had to take an introductory database class.  It focused mostly on writing robust queries and the SQL Language itself.  There was still some talk about database management to understand normalization and the like in MySQL, but it mostly focused on queries.  At the time, I honestly didn't see the benefit in the class and I certainly wasn't alone in this analysis.  This was very short sighted for a number of reasons.  Let me digress:

First, everything, and I mean everything is moving onto the cloud.  Developers are pushing a lot more than just player profiles and the online stats of games 10 years ago.  Data as complex as custom game content means more developers, in more areas of a game's code need to be comfortable writing SQL queries which are reasonably efficient.  One poorly written query can be devastating to a server if it is hit enough times.

Secondly, social networking games is a vastly expanding market.  In these games, typically every piece of persistent data has to be put onto a database somewhere.  Therefore, when prototyping, developers have to understand good database design principles and be familiar with libraries used on their platform.

Last but not least, databases are being utilized in very cool ways to accomplish robust logging and resource management.

So why might a database be a worthwhile log listener for your logging system?  What makes it any better than a text or html file?  Technically a text file can be revisioned properly to store all the latest information, but this can be troublesome when large teams are handling the same content at once.  A database alleviates a lot of these problems and head aches.  In addition, SQL queries can serve as an excellent debugging tool.  Sure, a text file can store the same data but it is unreasonable for a programmer to hack together new parsing code every time they are looking for shared issues.  A well designed database will allow programmers to use joins and subqueries to find meaningful relationships (and problems) in their application.  Tom Niwinski discusses how they used databases in such a manner in his excellent feature on Gamasutra.  He describes how they had an AI controlled character roam their game world and log errors to the database.

Picture this scenario.  A large team installs the latest nightly build.  They all have an automated bot roam their world overnight.  In the morning they check for new entries in the database.  All these separate instances can now be joined and compared for common issues.  Log entries might specify an error, such as a player falling through the world, and give the world position.  Level designers can proceed to go to that position in the map and resolve the issue.

In his excellent book, Jason Gregory explains how databases can be used as resource managers.  They are more than capable of storing unique global identifiers, meta-data for game content, and a revision history for an object's life cycle.  Primary keys and heavily normalized tables lend themselves well to cross referenced integrity and truly singular identifiers

So...in summary.  Databases matter, in more ways than you might think.

Recursive Ray Tracing

Adding real recursion to the mix (and not just basic shadow rays) gives the added benefit of effects like transmission and reflection.  By building off our phong model, we were able to recursively reflect a ray up to a given cutoff depth and modify the final color with a "reflective" float between zero and one.  Reflections is one area of 3D graphics where a ray traced model really excels.  With just a few more lines of code we were able to get results like those shown in the picture.

Ray Tracing with Phong Shading

Phong shading is very popular, supported by most graphics libraries by default, and can be implemented very easily and efficiently. That's because the model rests on a relatively simple equation. Compare this to my last post on Ray Tracing (which had no lighting model at all) and you'll see the difference is quite profound.

The polygonal floor just uses a procedural shader that verifies the row and column of the intersection point.  Hopefully we'll get around to real texture mapping some time in the future.

Update on Polygon RayCasting

My previous post on 2D Polygon Raycasting had an error at the very end of it. It turns out that it is much more useful to return the surface normal of the object which is hit and not the reflection off this normal. Finding the reflection after wards is extremely easy to find later if you still need it by merely reflecting the ray direction off this normal. However, finding the edge normal given a resulting reflection and a ray direction is much more annoying to calculate.

The final code then turns out to be the following:

public static bool RayCast(Ray ray, Polygon polygon, float tmax, out float t, out Vector2 pt, out Vector2 normal)
        {
            t = float.MaxValue;
            pt = ray.Origin;
            normal = ray.Direction;
            
            // temp holder for segment distance
            float distance;
            int crossings = 0;

            for (int j = polygon.NumVertices - 1, i = 0; i < polygon.NumVertices; j = i, i++)
            {
                if (RayIntersectsSegment(ray, polygon.v[j], polygon.v[i], float.MaxValue, out distance))
                {
                    crossings++;
                    if (distance < t && distance <= tmax)
                    {
                        t = distance;
                        pt = ray.GetPoint(t);

                        Vector2 edge = polygon.v[j] - polygon.v[i];
                        normal = Vector2.Normalize(RightPerp(edge));
                        // no reflection here
                    }
                }
            }
            return crossings > 0 && crossings % 2 == 0;
        }

A Glimpse At Shape Tesselation

Tessellation, sometimes referred to as triangulation, is an important concept in computer graphics that subdivides triangles for finer detail. I plan to write up a full post on this later. For now, here's some pictures of an old assignment I completed last quarter. You can see support for the cube,
cone, cylinder, and sphere.

A Trip Down Memory Lane

 

 

An old project I made freshmen year in a group of 4 aspiring developers. Not bad for beginners with a mere 10 weeks of time from start to finish.

Game Engines -- Not For The Squeamish

Game engines are a beautiful area of study and have always been an interest of mine. Currently, as an independent study I am writing a full 2D game engine on top of XNA. It's a lot of work, I like it, and I'm happy to be pursuing such a challenge. However, in most cases you shouldn't be writing game engines. There is a lot of general purpose code lying around out there that hasn't been used in any meaningful implementation ever. If you are looking to write your first game, going into it with the idea that you will write an engine first is very misguided for a number of reasons. For a post which nicely summarizes why see ScientificNinja's thoughts on the matter.

Write Games, Not Engines

2D Polygon - Raycasting

Synopsis
Ever write a 2D game that supported convex polygons? Ever struggle to find good sources for ray casting onto polygons in 2D space?

Ironically, in 3D you'll find a number of different sources for Ray-Polygon intersection. Unless BSP trees are in use it usually involves some procedure resembling the following:

1) Derive a plane for the polygon, generally using the surface normal.
2) Find the intersection point of the ray and the plane (if any)
3) See if the polygon contains the point. There are a number of ways to do this, most notably using a binary search and seeing if the new point constructs a CCW triangle.

In 2D, the test can't really work this way. Instead we need to test the ray against each segment of the polygon. You might assume that if any intersection with a segment is found, we can conclude there is a valid intersection. However, this is not the case. There are two reasons we can't do an "early out" test in which the algorithm terminates with a true result if just one of the segments is intersected by the ray.

1) If a polygon contains the ray origin, there is no intersection. A usual PolygonContainsPoint() implementation can serve as a reasonably fast prerequisite test. However, it would be faster if we used the ray casting algorithm. If you read up on the algorithm you'll see it involves casting onto every segment and counting the number of crossings. With an even number, we can conclude the origin is outside the polygon, otherwise it resides inside of it.
2) When ray casting against a polygon we'll usually want far more information than just a boolean result. We'll usually want the distance of the ray, the contact point, and the normal of the ray intersection. In all these cases, we'll always want the closest intersection point. To definitively find it we'll need to test against every segment anyways. Running a contains method won't result in twice as many iterations (since it uses a binary search), but it will result in more than just one sweep of the polygon.

Ray-Segment Test

The ray segment test in 2D can be solved parametrically, as explained here. First we check if the ray direction and the segment are parallel, in which case we can quickly cancel out the possibility of a collision*. Then we solve for s and t. S must be a value between 0 and 1 to lie on the segment. T must be between zero (or some other user defined min value) and the max t value.

* This is false for collinear segments and rays. I have not found a clean and efficient way to deal with this case. If you have a suggestion, comment below. Using distance checks will work, but is an ugly way to check if a point is within the range of tmax. The normal in this case would probably have to be the ray direction reflected off the vertex normal.

And of course, the code for the test. Please note that LeftPerp(v) = (v.Y, -v.X). The special equals call simply checks if the value is within epsilon distance from zero. Please note that Epsilon is rarely the most appropriate tolerance value, but what is varies widely depending on your units and scaling and I found it was sufficient towards understanding the algorithm itself.  Still: numerical robustness matters!

public static bool RayIntersectsSegment(Ray ray, Vector2 pt0, Vector2 pt1, float tmax, out float t) {
    Vector2 seg = pt1 - pt0;
    Vector2 segPerp = LeftPerp(seg);
    float perpDotd = Vector2.Dot(ray.Direction, segPerp);
    if (Equals(perpDotd, 0.0f, float.Epsilon))
    {
        t = float.MaxValue;
        return false;
    }

    Vector2 d = pt0 - ray.Origin;

    t = Vector2.Dot(segPerp, d) / perpDotd;
    float s = Vector2.Dot(LeftPerp(ray.Direction), d) / perpDotd;

    return t >= 0.0f && t <= tmax && s >= 0.0f && s <= 1.0f;
}

Ray-Polygon Test
The final ray polygon test brings all of this together in a relatively simple way. As we iterate through the polygon we test every edge. If there is an intersection we increment the number of crossings. If the distance is less than the current minimum distance we now have a new closest intersection, and we proceed to calculate the normals and contact point for this edge. If the number of crossings is even and greater than zero at the end of the test, a true result is returned and the current distance, contact point, and normal are used.

Contact point shown in light green, ray reflection normal in purple

Update: The purple line above is actually drawing the reflection of the ray off the normal, not the edge normal itself.  The below code has been corrected to return the edge normal.  In practice, it is much more useful than the reflection (which can always be calculated afterwards using the normal if you need it).

public static bool RayCast(Ray ray, Polygon polygon, float tmax, out float t, out Vector2 pt, out Vector2 normal)
        {
            t = float.MaxValue;
            pt = ray.Origin;
            normal = ray.Direction;
            
            // temp holder for segment distance
            float distance;
            int crossings = 0;

            for (int j = polygon.NumVertices - 1, i = 0; i < polygon.NumVertices; j = i, i++)
            {
                if (RayIntersectsSegment(ray, polygon.v[j], polygon.v[i], float.MaxValue, out distance))
                {
                    crossings++;
                    if (distance < t && distance <= tmax)
                    {
                        t = distance;
                        pt = ray.GetPoint(t);

                        Vector2 edge = polygon.v[j] - polygon.v[i];
                        // We would use LeftPerp() if the polygon was
                        // in clock wise order
                        normal = Vector2.Normalize(RightPerp(edge));
                    }
                }
            }
            return crossings > 0 && crossings % 2 == 0;
        }

In this implementation, it is assumed that the polygon is a convex array of vertices in Counter Clockwise Order. This is why we reflect off the right perpendicular of the edge. If your implementation uses Clockwise polygons you'll want to use LeftPerp() instead. Here's a reference of the helper functions:

public static Vector2 LeftPerp(Vector2 v)
        {
            return new Vector2(v.Y, -v.X);
        }

        public static Vector2 RightPerp(Vector2 v)
        {
            return new Vector2(-v.Y, v.X);
        }

Happy raycasting!

Ray Tracing

For my Computer Graphics class this quarter I've been tasked with building a relatively robust ray tracer. This has involved math for transformations, setting up an image plane, ray-casting onto certain shapes, and much, much more. The requirements for the project build up as we progress throughout the quarter. Here's our latest early checkpoint with no lighting and no recursive ray casting.

It's worth noting that super sampling is used in the screenshot on the right. Super sampling basically involves casting multiple, close but still marginally displaced rays, and averaging the results. Click here to see the scene without super sampling enabled.

Our next checkpoint will involve implementing Phong shading. I'll try to post screenshots and give tips on the implementation when it is finished.

Drawing Lines in XNA With SpriteBatch

Lines are a vital primitive that can greatly aid one's work during development. They can be used to draw the actual geometry of an object, show the distance between them, and let testers spot bugs earlier in development.

If you have a drawing interface that only relies on SpriteBatch and don't feel like messing with Vertex Buffers, you can cheat drawing lines using a single texture. By using a 1x1, white pixel, we can create a simple interface to draw lines of any size and color.

First you'll need to create the texture. Having one static copy may be preferred over creating the texture inside every instance. A current project of mine keeps a copy of this texture in a "PrimitiveManager", which oversees a number of different needs. We'll just keep a copy of this pixel in the Line class here for simplicity's sake.

public class Line {
    public static Texture2D Pixel;

    public static Initialize(GraphicsDevice graphics) {
        Pixel = new Texture2D(graphicsDevice, 1, 1, false, SurfaceFormat.Color);
    }
}

This will create our simple 1x1 pixel. By using a Color Overlay, we can have it render in any color we like. It will support transparency too.

What kind of parameters would we like to use when drawing lines? Most lines are defined by a start point, an endpoint, a color, and a line thickness.

Since we are using a 1x1 pixel, the distance between the start and endpoint will be the scale in one direction, and the line thickness in the other. The rotation passed into SpriteBatch will be the Atan2() of the x and y values from this difference.

To draw lines we are going to set our Origin to be {0.0f, 0.5f}. This is the center left of the pixel, and will thereby apply scaling in one direction.

public class Line {
    public static Texture2D Pixel;
    private static Vector2 Origin = new Vector2(0.0f, 0.5f);
    
    public Color color;
    public Vector2 start;
    public Vector2 end;
    public float lineThickness;
    // following is not needed unless you are doing front-to-back
    // or back-to-front drawing
    public float layer;
    
    public static InitializeLineDrawing(GraphicsDevice graphics) {
        Pixel = new Texture2D(graphicsDevice, 1, 1, false, SurfaceFormat.Color);
    }
    
    public void Draw(SpriteBatch spriteBatch) {
        Vector2 d = end - start;
        float angle = Math.Atan2(d.Y, d.X);
        // add 1 for single points and due to the way 
        // the origin is set up
        float distance = d.Length() + 1.0f;
        spriteBatch.Draw(Pixel, start, null, color, angle, Origin, 
            new Vector2(distance, lineThickness), SpriteEffects.None, layer);
    }
}

Why do we add 1 to our distance calculation? There are two reasons:
1) A single point, with a start and end vector in the same space, should draw one pixel on screen. If we don't add 1 to our existing result, single point lines will not be drawn at all because the distance between them will be zero.
2) The origin is offset from the center, and our single pixel texture already occupies a known distance of one. If you look carefully, without this addition, lines will always be drawn one unit short.

In general, there are a number of different ways you can go about implementing this. My code is really just a bare skeleton. The origin can just be passed in every time in the draw method with a hard coded new Vector2(0.0f, 0.5f) constructor call. You might want to write an unload method that disposes of the texture. You could precompute the distance and angle between two points and save them, perhaps as private variables. Properties could work wonderfully to this effect. When either Start or End is changed, simply compute these values and avoid running an expensive square root operation on every frame. Atan2() isn't that expensive, but if you are going to save the distance as a field you might as well do the same with the angle.