Class Is Always In Session

I recently released a minor update to the CDS Library.  I fixed some bugs and provided more explicit casting.  The major incentive for these changes was compatibility with C++.  CDS is still very much grounded in ANSI C, which is deliberate for compatibility reasons, so it doesn't take advantage of C++ specific features (such as templates).  However, in terms of compatibility, I'm proud to have made a data structures library that almost any C/C++ compiler can build. 

Unfortunately I'm spread very thin so my time for side projects such as these is extremely limited.  I was hoping to get more experience writing cache conscious code, and perhaps experiment with some cache oblivious algorithms too.  

Consistently exploiting cache optimized code is  something I'm more mindful of, but admittedly need to improve on.  It would be nice to explore this more some other time, perhaps as an extension to this project.

I'm also working on a game project for school where I'm deliberately trying to tackle Component - Entity Models and get more experience with SIMD math and intrinsics.  I'm admittedly sticking relatively close to the framework used in Unity for now.  In another project I might look into more data driven representations that use component aggregation a bit more purely.  I started a thread on GameDev which discusses implementing lighter RTTI and ended up exploring ways to avoid the "everything is a game object" system we see so frequently in these types of frameworks.  While this model admittedly feels excessive for some simple things it does have its benefits.   When certain operations are best applied to logical game objects, iterating over every component or deleting them is much easier if you have one central game object.  Communication between connected components also becomes trivial.
 

Currently the big question at hand is message passing.  A hash table of function names and their addresses sounds reasonable.  But is passing a void pointer array the best way to pass arguments?  Do "returns" from these functions need to be put back into arguments of this array?  What about like method names in different components?  Whatever is chosen, it will have significant pros and cons that weren't very clear when we decided to go with components in the first place.  In practice, we're finding the component model actually hides a significant amount of abstraction from the user.  I'm not saying inheritance trees are better, merely that Component-Entity models, like all game object models, is going to feel a bit quirky from time to time. 

Speaking of quirky, intrinsics will definitely feel that way the first time you implement them.  Forced alignment, unclear macros, pipeline flushes, and bit masks?  Your standard vector/matrix types are no longer so routine.  And don't even get me started on how much of a pain it is to write this in a cross platform manner.  Altivec's SIMD functions are just different enough to warrant typedefs everywhere.  However, as an engine developer, intrinsics are definetly pretty cool.  They are blazing fast (if used appropriately) and make old problems new again.  That quaternion, bounding sphere, AABB, and float packed color structure are all "new" again.  Things like cosine functions and sorting algorithms also present exciting new ways to conquer some old problems.  It takes a specific kind of developer to get truly excited about rewriting these sorts of facilities.  However, for those that do, they should definitely look into intrinsics if they haven't already.

My third recent side project involved diving into Lua.  I work with PHP in my job so interpreted languages are not completely foreign to me.  While Lua is considered easy to learn its syntax does not resemble C and certain ways in which Lua is used (table lookup, metatables, etc) can actually get rather involved.  Nonetheless, it's a fun language to use, it was made by some very smart people, and it never feels like it's trying to be something its not.  Lua knows it's a scripting language, and as such, is more frequently adopted as one compared to languages that see this as some sort of insult.


I'd like to build an event system or somehow provide script level access to my component entity model.  However, it is still in development and not exactly a rudimentary task.  So I kept the scope small and just made a simple math library.  If nothing else, it provided a nice introduction to the language.







Other current events:
I learn a lot from reading other people's code.  So while a lot of people in the games industry despise Boost and Template Meta-programming in general, it doesn't hurt to familiarize myself with the subject matter.  I did the same with design patterns a couple years ago.  The possible misuse of a technique is not a good excuse to evade learning it altogether.  Is a singleton a monstrosity?  Does overuse of templates bloat and complicate code?  Yes and yes, but every implementation has its share of pros and cons.

I got Jesse Schell's excellent book from the library over the break.  I may not see myself as a designer, but it never hurts to have some sensible design ideas floating around in your head.  And even in the absence of great ideas, it improves communication skills with talented game designers.

I also got Volume 1 of Knuth's book for Christmas.  I simply don't have the time to muscle through something like this right now, but it's nice knowing that if I want to challenge myself, I merely need to reach over to my bookshelf.  It's gonna take a while to get through this one.

Update to CDS

Doxygen Documentation Makes Learning the API Much Easier

With new found (but short lived) free time over the break, I got around to committing a major new release of the CDS Library.  In addition to a host of new functions and finished structures, I made everything compatible with ANSI C and implemented Doxygen Documentation.  Other annoyances, such as const correctness have been ironed out, and all of the examples have been rewritten in a way that tries to teach new users how everything works.  CDS is still relatively new, and could benefit from more iterations and tweaking.  However, at this time it is pretty solid given the time constraints.  Functionality, style, and typenames are much more consistent now.  As usual, you can always find the latest version of CDS on GitHub. 

Browse CDS on GitHub

You can refer to my first post on CDS for more information here. Enjoy!

Below is a simple example program demonstrating the usage of a cds_dynamic_array:

int main(void) {
     /* create the array */
     cds_dynamic_array *array = NULL;
     unsigned int size = CDS_DEFAULT_DYNAMIC_ARRAY_SIZE; /* 4 by default */
     cds_result cr = cds_dynamic_array_create(&array, size); /* notice the address of the pointer is passed in */
    
     /* checks for an error, prints and returns 1 if something failed
      * we do this (in this example) repeatedly for safety
      */
     if (cds_error_check(cr)) return 1;
 
     /* add the strings to the container */
     char * presidents[] = {"washington", "jefferson", "roosevelt", "reagan", "clinton", "obama"};
     unsigned int numPresidents = 6;
     unsigned int i;
     for (i = 0; i < numPresidents; ++i) {
          cr = cds_dynamic_array_push_back(array, presidents[i]); /* will need to reallocate when i == 4 */
          if (cds_error_check(cr)) return 1;
     }
 
     /* print out the array */
     cds_log("Displaying the contents of the dynamic array...\n");
     logArray(array, 1);
 
     /* try adding past the current size of the array */
     void *curValue;
     cds_log("Adding some more strings to the container...\n");
     char *otherPresidents[] = {"adams", "bush", "coolidge", "kennedy"};
     unsigned int numOtherPresidents = 4;
     /* since the default size is 4, we've grown once, 4 * 1.5 = 6 */
     /* therefore, on the next insertion, the array will need to grow */
     /* we can use a custom growth function, to resize things differently */
     for (i = 0; i < numOtherPresidents; ++i) {
          cr = cds_dynamic_array_push_back_gf(array, otherPresidents[i], &arrayDoubleGrowth);
          if (cds_error_check(cr)) return 1;
     }
 
     /* lets try printing the array using an iterate function */
     cds_log("Printing the contents of the array using the iterate function...\n");
     cr = cds_dynamic_array_iterate(array, &printString2);
     if (cds_error_check(cr)) return 1;
 
     /* accessing the last element first just for the sake of printing it */
     unsigned int count = cds_dynamic_array_count(array);
     cr = cds_dynamic_array_get(array, count - 1, &curValue);
     cds_log("Removing the last element in the collection: %s", (char *)curValue);
 
     /* remove the element at the end of the array */
     cr = cds_dynamic_array_pop_back(array);
     if (cds_error_check(cr)) return 1;
 
     /* this will remove the element from the container, but give it as a pointer */
     cr = cds_dynamic_array_pop_back_data(array, &curValue);
     if (cds_error_check(cr)) return 1;
     cds_log("Removed: %s from the back of the array\n", (char *) curValue);
 
     /* remove functions will rely on pointer addresses by default
      * we know that roosevelt's address is in the array so this will work */
     cr = cds_dynamic_array_remove(array, presidents[2]);
     if (cds_error_check(cr)) return 1;
 
     /* if we want to remove with value equality, we must use the cmp functions 
      * so while "adams" is in the array, this is a new address
      */
     char adamsStr[] = "adams";
     cr = cds_dynamic_array_remove(array, adamsStr);
     char resultString[CDS_RESULT_MAX_STR_LEN];
     cds_result_string(cr, resultString);
     cds_log("Attempt to remove the same string at a different address: %s\n", resultString);
 
     /* if we use our strcmp equivalent, this can be done with the proper function */
     cr = cds_dynamic_array_remove_cmp(array, adamsStr, &cmpStr);
     cds_result_string(cr, resultString);
     cds_log("Attempt to remove the same string using the comparison function: %s\n", resultString);
 
     logArray(array, 0);
 
     /* you can also remove elements by index (with safe bounds checking) */
     cds_log("Removing from index 2...\n");
     cr = cds_dynamic_array_remove_at(array, 2);
     logArray(array, 0);
 
     /* The dynamic array supports multiple removal behavoirs
      * By default it is shift down, which maintains the relative order of elements
      * if remove_at(2) CDS_SHIFT DOWN: a b c d e f becomes a b d e f
      * It also supports replacing the removed element with the element at the end
      * This disrupts the relative order of elements, but is more efficient than shifting large arrays
      * if remove_at(2) CDS_REPLACE_WITH_LAST a b c d e f becomes a b f d e
      */
     cds_log("Removing from index 2 using CDS_REPLACE_WITH_LAST\n");
     cr = cds_dynamic_array_remove_at_rb(array, 2, CDS_REPLACE_WITH_LAST);
     logArray(array, 0);
 
     /* Reverse the relative order of elements */
     cds_log("Reversing the order of elements in the dynamic array...\n");
     cr = cds_dynamic_array_reverse(array);
     logArray(array, 0);
 
     cds_log("Deleting the dynamic array...\n");
     cr = cds_dynamic_array_delete(&array);
     if (cds_error_check(cr)) return 1;
     cds_log("Deletion successful...\n");
     return 0;
}

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");

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();