Author Archives: Randy Gaul

memfile.h – Reading files from memory with fscanf

Often times it is extremely convenient to compile certain assets, or data, straight into C code. This can be nice when creating code for someone else to use. For example in the tigr graphics library by Richard Mitton various shaders and font files are directly included as character arrays into the C source. Another example is in dear imgui where some font files (and probably other things) are embedded straight into the source.

The reason this is useful is embedding things in source removes dependencies from code. The less dependencies the better. The easier it is for someone to grab your code and solve problems, the better your code is.

I’ve created a single header called memfile.h that implements a function for opening a file in memory, and also implements a bunch of fscanf overloads. Here is a link to the github repository.

Here’s the readme:

memfile is a C header for opening files in memory by mimicking the functionaliy of fopen and fscanf. memfile is not compatible with standard C FILE pointers, but works pretty much the same way. Here’s a quick example:

Just include memfile.h and you’re good to go. I’ve created an example to demonstrate usage in main.c. As extra goodies I’ve included the incbin script I used to generate the poem symbol from main.c (incbin.pl stolen from Richard Mitton).

Here’s example usage:

 

TwitterRedditFacebookShare

Essentials of Software Engineering – With a Game Programming Focus

I’ve been commissioned to write a big document about what I think it means, and what is necessary, to become a good software engineer! If anyone finds the document interesting please do email me (email on my resume) with any questions or comments, even if you hate it and deeply disagree with me! This is the first release so some sections may be a bit skimpy and I might have some false info in there here and there.

I’m a fairly young engineer so please do take all my opinions with a healthy dose of skepticism. Nonetheless I hope the document is useful for someone! Many of my opinions come from my interpretation of much more experienced engineers I’ve come in direct contact with, and this PDF is sort of a creation of what others taught me.

As time goes on I may make edits or add new chapters, when I do I’ll modify the version number (just above the table of contents). Here is the PDF:

Download (PDF, Unknown)

Forest RTS – Unfinished Game

 

Decided to release an unfinished game that will never be finished. RIP. The game started as a for-fun game jam to test out working with a couple friends of mine. In the end we ended up working for 2-3 weeks before deciding to move on to another project. Read more about the game here.

Download executable: Download (ZIP, 9.53MB).

Link to source: here.

forest_clip

bear swamp_poison swamp

I ended up enjoying the human AI quite a bit, and it grew to a decent size! This was my first time implementing things like A*, or a semi-complex state machine, and the end it was total fun. Here’s an explanation of the human behavior in case anyone was curious (taken straight from the source code);

Download executable: Download (ZIP, 9.53MB).

Preprocessed Strings for Asset IDs

Mick West posted up on his site a really good overview of some different methods for hashing string ids and gave good motivation for optimizing this area early on in a project. Please do review his article as it’s a prerequisite to this post, and his article is just really good.

I’ve been primarily concerned with memory management of strings as they are extremely hairy to work with. For me specifically I’ve ruled out the option of a string class — they hide important details and it’s too easy to write poor (but functional) code with them. This is just my opinion. Based on that opinion I’d like to achieve these points:

  • Avoid all dynamic memory allocation, or de-allocation
  • Avoid complicated string data structures
  • Little to no run-time string traversals (like strcmp)
  • No annoying APIs that clutter the thought-space while writing/reading code
  • Allow assets to refer to one another while on-disk or in-memory without complicated pointer translations

There’s a lot I wanted to avoid here, and for good reason. If code makes use of dynamic memory, complicated data strctures, etc. that code is likely to suck in terms of both performance and maintenance. I’d like less features, less code, and some specific features to solve my specific problem: strings suck. The solution is to not use strings whenever possible, and when forced to use strings hide them under the rug. Following Jason Gregory’s example he outlined about Naughty Dog’s code base from his book “Game Engine Architecture 2nd Ed” I implemented the following solution, best shown via gif:

anim

The SID (string id) is a macro that looks like (along with a typedef):

I’ve implemented a preprocessor in C that takes an input file, finds the SID macro instances, reads the string, hashes it and then inserts the hash along with the string stored as comment. Pretty much exactly what Mick talked about in his article.

Preprocessing files is fairly easy, though supporting this function might be pretty difficult, especially if there are a lot of source files that need to be pre-processed. Modifying build steps can be risky and sink a ton of time. This is another reason to hammer in this sort of optimization early on in a project in order to reap the benefits for a longer period of time, and not have to adjust heavy laid-in-stone systems after the fact.

Bundle Away the Woes

I’ve “stolen” Mitton’s bundle.pl program for use in my current project to recursively grab source files and create a single unified cpp file. This large cpp can then be fed to the compiler and compiled as a “unity build”. Since the bundle script looks for instances of the “#include” directive code can be written in almost the exact same manner as normal C++ development. Just make CPP files, include headers, and don’t worry about it.

The only real gotcha is if someone tries to do fancy inclusions by defining macros outside of files that affect the file inclusion. Since the bundle script is only looking for the #include directive (by the way it also comments out unnecessary code inclusions in the output bundled code) and isn’t running a full-blown C preprocessor, this can sometimes cause confusion.

It seems like a large relief on the linker and leaves me to thinking that C/C++ really ought to be used as single-translation unit languages, while leaving the linker mostly for hooking together separate libraries/code bases…

Compiling code can now look more or less like this:

First collect all source into a single CPP, then preprocess the hash macros, and finally send the rest off to the compiler. Compile times should shrink, and I’ve even caught wind that modern compilers have an easier time with certain optimizations when fed only a single file (rumors! I can’t confirm this myself, at least not for a while).

Sweep it Under the Rug

Once some sort of string id is implemented in-game strings themselves don’t really need to be used all too often from a programmer’s perspective. However for visualization, tools, and editors strings are essential.

One good option I’ve adopted is to place strings for these purposes into global table in designated debug memory. This table can then be turned off or compiled away whenever the product is released. The idea I’ve adopted is to allow tools and debug visualization to use strings fairly liberally, albeit they are stored inside the debug table. The game code itself, along with the assets, refer to identifiers in hash-form. This allows product code to perform tiny translations from fully hashed values to asset indices, which is much faster and easier to manage compared to strings.

This can even be taken a step further; if all tools and debug visualizations are turned off and all that remains is a bunch of integer hash IDs, assets can then be “locked” for release. All hashed values can be translated directly into asset IDs such that no run-time translation is ever needed. For me specifically I haven’t quite thought how to implement such a system, and decided this level of optimization does not really give me a significant benefit.

Parting Thoughts

There are a couple of downsides to doing this style of compile-time preprocessing:

  • Additional complexity in the build-step
  • Layer of code opacity via SID macro

Some benefits:

  • Huge optimization in terms of memory usage and CPU efficiency
  • Can run switch statement on SID strings
  • Uniquely identify assets in-code and on-disk without costly or complicated translation

If the costs can be mitigated through implementing some kind of code pre-processor/bundler early on then it’s possible to be left with just a bunch of benefits :)

Finally, I thought it was super cool how hashes like djb2 and FNV-1a use an initializer value to start the hashing, typically a carefully chosen prime. This allows to hash a prefix string, and then feed the result off to hash the suffix. Mick explains this in his article this idea of combining hashed values as a useful feature for supporting tools and assets. This can be implemented both at compile or run-time (though I haven’t quite thought of a need to do this at compile-time yet):

 

I hate the C++ keyword auto

Warning: rant post incoming!

I’m not really sure what other programmers are thinking about or focusing on when they read code, but personally I’m thinking mostly about the data being operated on. One of the first things I like to figure out when reading new code is if any C++ constructors, destructors, or other features that generate code are being used with a current data type.

If a piece of code is operating on only integers usually it becomes easy to have a grounded concept in what kind of assembly is to be generated. The same goes for code operating on just floats, or in general just POD data. The moment C++ features are used that generate large amounts of code at compile-time “surprises” can pop out in the form of constructor code, destructor code, implicit conversions, or entire overloaded operators.

This bugs the crap out of me. When I look at code I rarely want to know only what the algorithm does, and instead need to also know how the algorithm operates on given data. If I can’t immediately know what the hell is going inside of a piece of code the entire code is meaningless to me. Here’s an example:

Please, tell me what the hell this for loop is doing. What does that = operator do? Is there a possible implicit cast when we pass results to the StoreResults function? What is .begin, what is i, and how might the ++ operator behave. None of the questions can be answered [to my specific and cynical way of thinking about C++] since this code is operating on purely opaque data. What benefit is the auto keyword giving here? In my opinion absolutely none.

Take a non-auto example:

In the above code it is painfully obvious that the only opaque pieces of code are functions, and the functions are easy to locate at a glance. No unanticipated code can be generated anywhere, and whenever the user wants to lookup the Results struct to make sure there are no “C++ loose ends” in terms of code-flow a simple header lookup to find the Results declaration is all that’s needed. I enjoy when code is generated in a predictable way, not in a hidden or hard to reason about way. The faster I can reason about what this code will do at run-time the faster I can forget about it an move onto something else more important.

Code with unnecessary abstractions bugs me since it takes extra time to understand (if an understanding can even be reached), and that cost better come with a great benefit otherwise the abstraction nets a negative impact. In the first example it’s not even possible to lookup what kind of data the results variable represented without first looking up the SortByName function and checking the type of the returning parameter.

However, using auto inside of (or alongside) a macro or template makes perfect sense. Both macros and templates aim at providing the user with some means of code generation, and are by-design opaque constructs. Using auto inside of an opaque construct can result in an increase in the effectiveness of the overall abstraction, without creating unnecessary abstraction-cost. For example, hiding a giant templated typename, or creating more versatile debugging macros are good use-cases for the auto keyword. In these scenarios we can think of the auto keyword as an abstraction with an abstraction-cost, but this cost is side-stepped by the previously assumed abstraction-costs of templates/macros.

Please, stop placing auto in the middle of random every-day code. Or better yet, just stop using it at all.

Compute Basis with SIMD

A while back Erin Catto made a cool post about his short function to compute a basis given a vector. The cool thing was that the basis is axis aligned if the input vector is axis aligned.

Catto noted that the function can be converted to branchless SIMD by using a select operation. So, a while ago I sat down and wrote the function, and only used it once. It didn’t really seem all too helpful to have a SIMD version, but it was fun to write anyway (I made use of Microsoft’s __Vectorcall):

 

Single File Libraries – bundle.pl | incbin.pl

Sean T. Barrett makes a lot of very cool single-file libraries in C. Recently he’s also been making another big list of other single-file (or two files with src/header) that he likes.

The great thing about Sean’s libraries is that they contain functions that do exactly what they intend to accomplish, without doing anything more or less. They don’t contain any extra complexity other than specifically what is needed to get the job done. This helps when preventing his libraries from creating external dependencies, meaning his libs can be deployed as a single file inclusion into a pre-existing project, without linking to external libraries or requiring additional headers.

These qualities make libraries like Sean’s extremely easy to hookup and get going. If you want to learn how to make quality libraries just look at any of the STB libraries.

Writing Libraries

Sean writes libraries in an old version of Visual Studio (I think VC6?), and codes in C. He also keeps all of his code inside of a single file while writing it — I’ve seen this on Twitch.tv. For the rest of us that aren’t as crazy or hardcore as Sean we can just use bundle.pl.

Bundle.pl is a Perl script written by an unknown author (probably written by Richard Mitton). I found the file inside of Mitton’s single-file library “tigr”, which stands for Tiny Graphics Library. Mitton uses bundle.pl to recursively include a bunch of files into one larger c file. Check out the script yourself:

The idea is to make a dummy C file that includes other source files, like this:

Then bundle.pl can be run from the command line (assuming you have Perl installed) like so:

The script outputs some nice and quick text to stdout displaying which files were visited and packages the entire source tree into a single source file. The output file contains nice comments indicated the beginning and ending of files, like this excerpt from one of my own single-file libraries:

incbin

Mitton writes about the old joys of using the incbin command in assembly, where the assembler would embed the binary contents of a file straight into your program. It sounds like this gets dubious when dealing with linkers nowadays (I’ve had some really long link times by including large files into source code…), though it still happens from time to time in small single-file libraries.

An example is in Mitton’s tigr library where he uses a makeshift perl script “incbin.pl” to embed shaders and a png file (containing raster font glyphs) straight into C source code. This concept can also be seen in Omar Ocornut’s imgui library where some font files are embedded into the source. Omar seems to have used a small C program to generate the binary data as C source.

Again, I’m not sure who originally wrote this incbin.pl script but it was probably Mitton himself.

Finding Heap Corruption Tip on Windows

If one is fortunate enough to have access to <crtdbg.h> from Microsoft’s Visual C++ header, when running in debug mode there are a few _Crt*** functions that can  be pretty useful. My favorite ones are _CrtCheckMemory and _CrtDbgBreak (which is just a macro for __debugbreak in my case).

This function checks padding bytes around allocations made by the debug heap for buffer overruns. Usually this is not too necessary if you just do bounds checking yourself in debug mode, though sometimes old code crops up that you didn’t even write yourself, and needs debugging.

Lucky enough for me I had a good guess as to where the corruption was coming from as I had some call stacks in-tact from my crash. Finding the heap corruption was easy in my particular case since the code is deterministic and can be re-run quickly. Sprinkling this macro around will let me back-trace through the code to find exactly where the first instance of corruption happened:

A few minutes later I ended up here:

Since my breakpoint activated just after this function call, but not before, I knew the corruption came from this pesky function. Turns out it was a weird typo that was really sneaky, just barely causing an off-by-one error.

See if you can spot the error below. Here’s the answer (text is white, so highlight it to read): on line 8 chromSize needs to be changed to i.

Good If Statements – Self Documenting Code

Here’s a quick trick for documenting those pesky if-statements, especially when littered with complicated mathematics.

Here’s an example from Timothy Master’s “Pragmatic Neural Network Recipes in C++” where the author needed to test some interval bounds to see if the conditions were appropriate to perform a parabolic estimate of a step-size. Sounds, and looks, complicated:

In my opinion this author writes extremely good code. In the above example the details of the code are very well documented, however that’s just due to wonderful (albeit dubiously placed) comments. When modified slightly the code can still maintain the same readability and perhaps gain a little clarity:

The trick is to just name those little integer values that collapse down to a 1 or 0 (the comparison operators in C, like && and ||, take their arguments and return a 1 or 0). One of the most common applications of this kind of naming is when there’s a complex end condition in an algorithm. Often times this kind of termination criterion can just be called “done”:

 

Circular Orbits | Planetary Motion | NBody Simulation

I took a few hours yesterday to start on a simulation for a job application. Part of the simulation involves trying to figure out how to create stable nbody orbits, at least stable for some amount of time to look interesting.

Turns out that the mathematics beyond constructing a circular orbit of just two bodies is a bit far-fetch’d. We can see in this link that solving for the velocity of each planet is very straightforward. Let me take a screenshot of the final equations here:

orbit_math

To me this makes a lot of sense and matches my own derivation, albeit with a slightly different final form (just due to some algebra differences). I plug in the equation into my simulation and hit run, however there’s just not enough velocity to keep an orbit. See for yourself (the simulation is slowed down a lot compared to later gifs):

satellites_slow

Each white circle is a body (like a planet) and the red circle is the system’s barycenter.

So I tinkered a bit and found out the velocity is too dim by a factor of sqrt( 2 ). My best guess is that the equations I’m dealing with have some kind of approximation involved where one of the bodies is supposed to be infinitely large. I don’t quite have the time to look into this detail (since I have much more exciting things to finish in the simulation), so I just plugged in my sqrt( 2 ) factor and got this result:

satellites

Here’s the function I wrote down to solve for orbit velocity in the above gif:

I’m able to run the simulation for thousands of years without any destabilization.

If any readers have any clue as to why the velocity is off by a factor of rad 2 please let me know, I’d be very interested in learning what the hiccup was.

Next I’ll try to write some code for iteratively finding systems of more than 2 bodies that have a stable configuration for some duration of time. I plan to use a genetic algorithm, or maybe something based off of perturbation theory, though I think a genetic algorithm will yield better results. Currently the difficulty lies in measuring the system stability. For now the best metrics I’ve come up with is measuring movement of the barycenter and bounding the entire simulation inside of a large sphere. If the barycenter moves, or if bodies are too far from the barycenter I can deem such systems as unstable and try other configurations.

One particularly interesting aspect of the barycenter is if I create a group of stationary bodies and let them just attract each other through gravity, the barycenter seems to always be dead stationary! The moment I manually initialize a planet with some velocity the barycenter moves, but if they all start at rest the barycenter is 100% stable.

satellites_all