giggs' blog

Rubik's simulator

Over the last 3 weeks I coded a Rubik’s simulator using raylib. You can play with it here.
Code is available here.
After learning C and practicing it on Advent of Code, I wanted to try and code an actual application using the language. This is the epic tale of how this application was developed. Join me as I slay (my own) demons terrible bugs.
The first half of this article is about the journey from an overall/personal standpoint. The second half shares implementation details.

The plan

I asked my programmer friends what kind of projects are well suited to C, and the unanimous answer was a game.
At the intersection of games, things I’m interested in and things I could conceivably program in a couple of months were chess and a Rubik’s cube.
In both cases, the first hurdle was how to open up a window and display something. I could either go full Handmade and make it a year+ project, or… I could use a library again! raylib was suggested by my friend polomi. It did seem to nicely fit my requirements. With the ability to display things in 3D, the Rubik’s cube was the clear winner.

What raylib does

From the raylib home page:

NOTE for ADVENTURERS: raylib is a programming library to enjoy videogames programming; no fancy interface, no visual helpers, no gui tools or editors… just coding in pure spartan-programmers way. Are you ready to enjoy coding?

I wasn’t ready, I was impatient! Though primarily aimed at videogames programming, it’s not a game engine per se. Simply said, it’s an easy and reliable way to get stuff to show on screen. It is built on top of the OpenGL API and enjoys a good reputation on the Handmade Network.
Their description is very accurate, and I enjoyed using raylib immensely… After swallowing my pride and using their premade project for VisualStudio.
I initially tried to set it up myself. Being illiterate in compilers, linkers and VisualStudio in general made that pretty hard. I eventually got a working setup, but I’d already made a lot of progress in the premade environment and ended up using that instead.

Credit to the raylib contributors, their premade tool is great. As is their tutorial for porting a raylib project to web assembly for web use. I would have never been able to host it anywhere without that.

raylib makes it easy to draw geometric shapes at a certain location in 3D space. It provides functions to apply a texture to those shapes, and plenty of mathematical tools to move things around. These tools are great!… If you know which ones to use and when.

Quaternion QuaternionFromMatrix(Matrix mat)
// Get a quaternion for a given rotation matrix

What it doesn’t

3D graphics involve a fair bit of geometry. That’s not a problem, I like geometry. However, my last math class was in high school just about half of my lifetime ago. I had never studied linear algebra, didn’t know what a matrix (or a quaternion) was, and struggled to recall how to do a dot product.
If you want to move objects around reasonably well, you need to understand the underlying maths. Otherwise, you’ll spend over an hour trying to rotate a single cube in place. Purely hypothetical situation, of course…
raylib has a helpful community, but doesn’t provide a linear algebra crash course (luckily, 3Blue1Brown does!). The theory was fine, but applying it wasn’t as straightforward as I’d hoped.
Just this once I’ll blame raylib, for their use of matrix multiplication from the left in their rotation function and from the right in their translation function (I guess there’s a good reason?).

Getting used to bigger projects

The project ended up being a little under 2000 lines of code (about half of it being data initialization). While those are rookie numbers, it’s 4 times larger than anything I’d previously written. With the size came a valuable set of insights.

A couple of times, I lost track of stuff I’d already written like a variable for something I wanted to track. I began using a note system which will hopefully prove useful.

I do not use enough tests in the code itself. The point isn’t so much to make sure a particular piece of code works upon writing it, but rather to quickly pinpoint where a change I make later breaks something. I’d already read about this, but experiencing the issues really helped hammering the point home. I still used far too few, but I’ll get there.

Past me probably wouldn’t have started coding anything useful, but would have stayed stuck in the planning stage agonizing over the best way to initialize data and avoid repetition. I was glad to just get the ball rolling. While this was obviously good for “getting shit done”, it came at the cost of some drudgery work when I wanted to change something in the structure, which inevitably lead to modifying many lines of initialization. Some of it could be automated it, some of it couldn’t (or I didn’t know how).

Some amount of rewriting is bound to be inevitable, but there’s progress to be made in how I approach this for future projects. Indeed, my friend polomi was kind enough to review the code and said this was the main problem with it. I’ll most likely improve in that aspect as I gain more experience, as long as I keep it in mind.

Some bloopers

One of the perks of working with 3D graphics is that bugs can be funny.
Here’s what happened when I gave an angle value in degrees to a function that uses radians.

Here’s what happened when I tried to apply the wrong rotation matrix to a set of cubes.
That second glitch inspired me to do this stylized “solver”, which I meant to improve but ended up scraping.
And here’s the first test of camera rotation functions that used quaternions. You can clearly see the camera resisting attempts to move as it somehow got closer to the cube, and eventually zooming off in another dimension.

Managing expectations

Speaking of the camera, this remained a sour note until I started writing this article. The camera implementation I used inherently restricts some movements in certain positions. Here’s successfully rotating the cube left and failing when looking at it from above.

There are a couple of ways to overcome these limitations. After spending most of a day learning about quaternions and trying to implement a system using them, I realized that even ironing out the bugs I had wouldn’t give me the results I wanted. In these darkest hours, I contemplated coding a chess game instead.
Eventually, I decided that trying to improve the camera wasn’t worth it for the time being. The current system was good, and I wasn’t sure how much I still ignored. Thus, I couldn’t get a reasonable time estimate for a successful implementation of my idea.
This wasn’t an easy decision to make. It’s inevitable that any project must ship at some point and some features get left out, I need to learn to make peace with such decisions. The fact that I tried and failed made it a bit harder, but I should learn to cope with this as well.
In the end, this turned out to be a blessing. After playing around with the nearly final version and getting very valuable feedback from my friend Tikle, I realized the system I wanted was ill-suited to manipulating a Rubik’s cube. I coded a simple button press to get the user out of the rotation lock.

Technical details

The Rubik’s simulation

The world created in the program is simply a white room with a cube at the center and a camera rotating around it. Nothing fancy. Each of the 27 little cubes stays in its starting position, except when the side it belongs to is rotated.
To draw the rotation of a side, simply rotate the 9 cubes in it around the axis the side rests on, and increment the rotation angle on each frame. This was the first function I wrote; the main hurdle was understanding the basics of rotation matrices and translation operations.

Mouse controls

Initially, I coded key presses for each rotation. One key for each of the 9 sides that can rotate. This was good to get the rotation functions working, but unacceptable from a user standpoint. Mouse controls had to be implemented. Even if you can easily get the mouse position on screen with raylib, what’s next?
I ended up creating a data structure for each of the 54 small faces of the cube. Each data cell holds the face’s coordinates in space, 2 neighbour faces and the rotation that makes either pair move.

Upon clicking, a ray is cast from the camera to where the cursor is. The program will keep the face hit by this ray that is closest to the camera. Then, mouse movement is detected. After a certain threshold, the program calculates the mouse movement vector and checks the lengths of its orthogonal projection on the vectors linking the face to its neighbours.
After tuning the movement threshold, this system turned out very accurate and fast from the user’s perspective. I’m really pleased with it. Some credit goes to Tikle for uncovering bugs and helping with testing!

Is it solved?

How do you know when you’ve solved a cube? Trivial human question.
Storing the starting position and checking against it obviously doesn’t work. So what do you do?
My initial convoluted idea would have involved changing much of the data structure, so polomi took pity on me and offered a very simple concept. Just attach the same vector to each face of each colour, and check that for a given colour all vectors are parallel.

Unfortunately, this doesn’t work if you have a cube where the orientation of a center face matters, and I had already implemented those. Fortunately, checking for the solved state is simpler in this case. Rather than having to check each of the 54 faces, you can simply attach a vector to each of the 27 cubes. This way, a non-oriented center is detected.

Undo/redo

This is the main advantage of a Rubik’s program when you’re learning. If you mess up something, you can easily undo your last moves. Implementing an undo/redo function was pretty simple here. I setup a lookup table for each rotation, and stored the number matching the rotation in a buffer. I set the buffer size at 10000 moves to be safe, but hopefully no one using this program will ever need that. If anyone ever does, be sure to thank polomi for encouraging me to code a proper circular buffer rather than just resetting it if it ever went over the limit.

Closing thoughts

At first, I thought I bit off a bit more than I could chew, especially with the camera rework attempt, but it turned out well. Part of the difficulty was (unwillingly) self-imposed at first. I simply didn’t explore the raylib library well enough. I stuck to their cheatsheet and ignored all the math functions included in one of their headers.
Good things came out of it, as I got a better understanding of some linear algebra concepts than I would have otherwise. Nevertheless, I should remember to be more curious about the tools I’m using. I ended up taking several included functions and modifying them to suit my needs for this program.

3D graphics is a fascinating subject, and I’m sure the rabbit hole goes infinitely deep. I’m not sure I want to jump into it. This felt like a very good introduction though, and I certainly gained a lot of experience. Valuable lessons were learned from both a programming and personal standpoint.
I effortlessly set to work on this project every day since I finished Advent of Code 2017 and generally couldn’t wait to get started. I say set to work, but it never felt like work, even in the most frustrating moments. There was great satisfaction in bringing all the pieces together. Sometimes, I wish I’d gotten into this earlier. But mostly, I’m glad I found this passion.

#programming #C #Rubik's