In order to expand my limited knowledge of C/C++ I’ve started to read and use the following books as reference material:
- “Thinking in C++, Volume 1, 2nd Edition” by Bruce Eckel (free version)
- “Effective C++, 3rd Edition” by Scott Meyers
- “Sams’ Teach Yourself C in 21 Days, 4th Edition” by Peter Aitken and Bradley L. Jones
I’ve also read an article or two in the book “Game Programming Gems” (edited by Mark DeLoura) while looking for a good way to store and manipulate the boolean matrices for the DLX algorithm. I’m leaning towards using Andrew Kirmse’s code from the “Simple, Fast Bit Arrays” article which has a license on the following form: “As long as you keep the copyright notice you can do whatever you want with it”. Not sure how that will interact with the GPL license I’m using, but I’ll figure out something.
I’ve checked out Donald Knuth’s own DLX program: dance.w. He uses a system called CWEB (hence the .w) to write his programs so I had to download, compile and run that in order to convert dance.w into dance.c. Then I could finally compile it. With my limited C knowledge I only understood bits and pieces, but I’ll keep trying as I learn more. I could argue that I don’t understand everything because he uses a handful of GOTO statements, but that’s not where I get stuck. Still, I don’t think Dijkstra would have approved of those GOTOs. Knuth has also written a more general version of the DLX program named gdance.w, but I’ll visit that after I’ve intellectually conquered dance.w.
My own implementation of the DLX algorithm in C++ is also complete. I’ve spent more than a few hours trying to befriend C++ and I think I’m finally getting the hang of it. I’ve implemented the algorithm as a shared library (.dll in Windows .so in Linux) by following the pseudo code from Knuth’s paper. My code uses the same variable names and it follows the same structure as in the paper. The storage, manipulation and transformation algorithms which takes the input boolean matrix and turns it into a collection of objects is still under development. This means that I’ve not actually tested the DLX implementation, but seeing how similar it’s to the pseudo code there is a fair chance that it might actually work.
I’ve also reread the paper “PRP – Parallel Recursive Procedures” by Arne Maus and Torfinn Aas in order to get some more ideas on how to parallelize the DLX algorithm. As I was implementing the DLX algorithm I wrote a bit about the implementation and some other challenges which are yet to come. Currently the progress on the project is as scheduled by the project plan.
NOTE: This post has been imported from my old it’s learning ePortfolio DECS blog.
Location, location, location 