Introducing CDS (The C Data Structures Library)

CDS was a side project to demonstrate I can write efficient data structures in a procedural language like C.  It currently supports all types (with void pointers) with the following data structures:

• dynamic array (cds_dynamic_array)
• singly linked list (cds_slist)
• doubly linked list (cds_dlist)
• stack (cds_stack)
• queue (cds_queue)
• binary search tree (cds_binary_tree)
• hash table (cds_hash_table) 

CDS tries to use consistent practices amongst the entire code base.  Every custom type, function, and macro starts with the cds_ or CDS_ prefix.  Data structure functions are typically structured in the following way: cds_datastructurename_function().  Therefore, to push_back an element onto a dynamic array you would call cds_dynamic_array_push_back(array, data);  This tends to make function calls and type names long, but is good practice, keeps things consistent, and avoids polluting the namespace.

Every data structure function returns a cds_result enum.  Every error code that could be thrown in any of the provided functions is a cds_result.  This keeps results more informative, consistent, and performance friendly.  Rather than returning -1 or NULL when an error occurs, it returns more specific information (e.g. CDS_BAD_ALLOC).  This is better practice because a number of things can potentially go wrong with a given operation, and this tries to ease the amount of time spent guessing.

Common operations include:
    create: allocates the given structure
    clear: removes the elements from the given structure
    delete: deletes the given structure (but not its elements)
    delete_all: deletes the given structure and its pointers to other elements
    add/push_back/insert/etc: adds the pointer to the structure
    remove/pop_back/pop/etc: removes a pointer from the structure
    count: get the current count of the structure
    find: search for a pointer address or do a value comparison via a cds_cmp_func
    iterate: passes every data type in the container safely to the given cds_visit_func

Assertions are given but not fully apparent in all of the code.  They can be compiled out of runtime code since they use optional macros.  There is support for custom memory allocators and log functions that can be interchanged easily at run/compile time so long as they match the function format of their stdlib equivalents.  Other intricacies include custom growth behavoirs, type specific comparisons, and more through function pointers, enums, and macros.

This code is still unfinished and in a relatively early state.  Since school and work keep getting in the way I'm releasing it now but intend on improving it later.  The code is free for non commercial use and commercially with permission (contact email given in the README).  Use at your own risk!

Browse CDS on GitHub

Here's a sample program example demonstrating cds_stack.  You'll see similar semantics for the rest of the data structures too.

UPDATE: I've revisited the library and am no longer so strict on the "every function returns an error result" philosophy.  Sometimes it is excessive and  actually makes code more error prone.  However, a vast majority of the functions still follow the old format.
UPDATE 2: CDS has received a significant new release, with full ANSI C compatibility, Doxygen Documentation, new functions, rewritten examples, and a host of bug fixes.  You can read about it here.

/* Create the stack */
cds_log("Running the stack test...\n");
cds_stack *stack = NULL;
cds_result cr = cds_stack_create(&stack);
if (cds_error_check(cr))
        return 1;
 
/* Add the values to the stack */
cds_log("Adding the usual values...\n");
int values[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
unsigned int n = 10;
unsigned int i;
for (i = 0; i < n; ++i) {
        cr = cds_stack_push(stack, values + i);
        if (cds_error_check(cr))
                return 1;
}
 
logStack(stack, 1);
 
/* Clean up the stack */
cds_log("Popping everything off the stack...\n");
int *top = NULL;
/* if you want to allow null values in your stack 
 * use cds_stack_count() instead */
while ((top = cds_stack_top(stack)) != NULL) {
        cds_log("Pop: %d\n", *(int *)top);
        cr = cds_stack_pop(stack);
        if (cds_error_check(cr))
                return 1;
}
 
/* if you call pop on an empty stack it returns CDS_UNDERFLOW */
cds_log("The stack is now clear.  Count: %u\n", cds_stack_count(stack));
cds_log("If you try to pop an empty stack, it will return: ");
cr = cds_stack_pop(stack);
char resultString[CDS_RESULT_MAX_STR_LEN];
cds_result_string(cr, resultString);
cds_log("%s\n", resultString);
 
/* you can also iterate on a stack like all the other data structures 
 * but we don't do that here
 */
cds_log("Deleting the stack...\n");
cr = cds_stack_delete(&stack);
if (cds_error_check(cr))
        return 1;
cds_log("Deletion successful...\n");

Procedural Terrain Generation

Windows Forms Launcher Window

I've often been interested in groups of algorithms that offer procedural generation of gameplay environments.  There is a rather wide range for these algorithms, both in computational time and complexity.  Some algorithms, such as Diamond Square are rather trivial to implement.  Others, such as the algorithms behind the MMO Love, are obviously much more in depth.  Since I'm about to explore a hybrid of these algorithms (Perlin Noise and others) I figured I'd resort back to an old project I worked on concerning terrain generation.  The idea of the project was to act as a tool to demonstrate how certain algorithms worked and compare them (as well as get some more experience with OpenGL 4).  The final launcher looked something like that on the right.  A drop-down of the algorithm, a radio select rendering mode, and algorithm specific settings.  The user could launch multiple windows and compare the differences.  This served as a rather effective tool for differentiating different methods and the effect of algorithm variables on the output (e.g. generating a terrain map with a decay rate of 0.3 instead of 0.7).  With a simple rotating camera and variable zoom levels, the user could inspect the final results of their work.

Diamond Square with high variation and low decay

It was nice to have effective proof of the weaknesses these algorithms have.  For example, Diamond Square in it's normal form, is prone to artifacts (especially with typical linear congruential number generation) and frequently builds mountains.  We also found sequential random additions was decent at generating rolling hills, but not smooth ones that often resembled cones.

All in all, procedural worlds won't replace the mapmaker anytime soon, but they are a powerful tool, and can serve as a nice base that can be tweaked and remodeled later.  I'd recommend game programmers become familiar with Diamond Square and Perlin Noise at the very least.

With a greater decay and lower variation

Wireframe View

  Go To the Project Page

SRT Moved to GitHub

Since Git as a VCS has become more prominent and the popularity of the service GitHub has (rightfully) skyrocketed, I finally got around to putting the Simple SDL RayTracer onto GitHub.  Not everyone in the industry uses SVN so it's high time I got comfortable with something else too.  If you've been holding off on Git because the clients have been bad I don't really blame you.  But they have gotten much better since I first tried them out, especially on Windows, and are frequently being offered as plugins for IDEs if that's the sorta thing you're into.

Introducing SRT

A few weeks ago I finished an early version of a ray tracer written in completely standard ANSI C.  I undertook this small project for a number of reasons.  It dawned on me that most of the work I had been doing involved an environment with an IDE and an object oriented language.  While this isn't an inherently bad thing, it is healthy to stay proficient in as many paradigms as possible.  Therefore, I decided I was going to do a project in straight C with MinGW and Notepad++ to remind myself that you can do everything without polymorphism, inheritance, and encapsulation.  The end goal was a simple raytracer with an interface that mimicked Open GL.  Since I decided to use SDL for software pixel operations I decided to call the project SRT, for "SDL Ray Tracer."  The acronym is just as viable for "Simple Ray Tracer."  Feel free to browse the project in its early form on Google Code at the link below.  Hopefully the project will be seen on GitHub someday too.

Browse SRT on GitHub

Browse SRT on Google Code

Basic features of SRT include the following:

• Raycasting support for multiple shapes, including spheres, 3D planar polygons, and oriented bounding boxes (OBBs)
• Support for typical 3D transformations, vector, and matrix operations.  The "Projection" and "ModelView" matrices can be translated, rotated, and scaled.
• Material and lighting support, with full RGBA channels for ambient, diffuse, and specular colors.  Materials also include scalar values for reflectivity and transmission (transparency).  Phong illumination included by default.
• Optional support for super sampling, control over recursive depth and other parameters for scene lighting.
• Although only tested on Windows, should support all the platforms and resolutions that SDL supports.
• Typedefs and macros provide support for single or double floating point precision, and assertions which can be omitted from "release" code.
• Future releases will hopefully support multiple light sources, orthographic projections, manipulation of the matrix stack, texture mapping, and thread support.

A typical program for SRT might resemble the following.  Note the resemblance to a typical Open GL program.

-- Init Function --
srtCreateWindow(800, 600, "SRT: SDL Ray Tracer");
srtPerspective(45.0, 800.0 / 600.0, 1.0);

-- Draw Function--
/* clear buffer */
srtClearColor3(0.05f, 0.05f, 0.05f);
srtClear();
srtBeginScene();

/* move camera 4.5 units backs */
srtMatrixMode(SRT_PROJECTION);
srtTranslate(0.0, 0.0, 4.5);

/* load identity modelview */
srtMatrixMode(SRT_MODELVIEW);
srtLoadIdentity();

/* setup a light */
srtLightAmbient4(0.065f, 0.065f, 0.065f, 0.15f);
srtLightDiffuse4(0.35, 0.35, 0.35, 0.35);
srtLightSpecular4(0.25, 0.25, 0.25, 0.85);
srtLightPosition3(-1.0, 1.1, -0.75);

/* setup a material */
srtMatAmbient4(1.0, 0.0, 0.0, 1.0);
srtMatDiffuse4(0.45, 0.45, 0.45, 0.75);
srtMatSpecular4(0.3, 0.3, 0.3, 0.35);
srtMatShininess(2.8);
srtMatReflectivity(0.45);

/* sphere: x, y, z, radius */
srtCreateSphere4(1.1, -0.85, -4.5, 0.65);

/* finish the scene */
srtEndScene();
srtPaintBuffer();
srtFlip();

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.