I recently got back into the development of an open source game I released last summer, You're the OS!. It is a browser game, written in Python and compiled to WebAssembly, in which, as the title indicates, you are the operating system of a computer. As such, you have to manage processes, memory and I/O events.
In case you haven't played the game, here is a very short summary of its core mechanics: you have some CPU cores, and you have a list of processes with varying levels of starvation, and you have to make them take turns on CPU cores and make sure none of them starves.
Recently, I added a power-up to the game: after 6 minutes of playing, you get a Sort button that, when clicked, sorts idle processes in decreasing order of starvation. I decided that the game would show the sorting algorithm being executed, by moving around processes as it happens. The sorting algorithm I wanted to use is Quicksort. In order for it to work like I wanted, there was 2 problems to overcome:
1 - This is a game, with a main loop that completely redraws everything on the screen 60 times per second. Therefore, it was not just a matter of writing a Quicksort function that performs an animation between each recursion. I needed to somehow create a function that performs a single step of the algorithm, then gives back control to the main loop (which ironically sounds just like a form of scheduling in an OS) for the duration of the animation frames, before being executed again from where it was interrupted.
2 - Just to make it more complicated, the list can change while it is being sorted, as a process can be killed, assigned to a CPU core, or removed from a CPU core.
Now, I want to share a comment from my code, detailing the solution that I came up with. I am quite proud of my solution, but not because it is particularly clever — on the contrary, I like it precisely because it is dumb:
This method creates the visual illusion that the next recursion of the quicksort algorithm is performed on the idle processes. In reality, the algorithm is always performed from the beginning, and stops as soon as a recursion that actually changes the array has happened. This way, the intended in-game result is achieved while avoiding the need to keep track of the algorithm's state, and a correct end result is ensured even when the idle process list changes between recursions.
To try and better explain what the comment means, here is the code of my Quicksort function that stops as soon as an actual change to the array is detected:
def simulate_next_sort_step(arr: [Process]):
# Standard Quicksort operations
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [process for process in arr if process.sort_key < pivot.sort_key]
middle = [process for process in arr if process.sort_key == pivot.sort_key]
right = [process for process in arr if process.sort_key > pivot.sort_key]
""" The magic happens here: we proceed to the next recursion only if
the current one didn't actually change anything. """
if (left + middle + right) == arr:
return simulate_next_sort_step(left) + middle + simulate_next_sort_step(right)
return left + middle + rightYou see, I realized along the way that the premise of my first problem described above was mistaken: my need was not, in fact, to implement a function that only executes the next recursion in the quicksort algorithm. My need was to implement an animation that pretends to only execute the next recursion in the quicksort algorithm. My solution does exactly that, in a stateless manner. It is a stupid, inefficient solution — but it is a solution that works, and completely avoids the corner case stated in my second problem: if the content of the array changes along the way, it will naturally cause the illusion of backtracking in the algorithm.
Of course, I could have gone through the trouble of actually figuring out a version of Quicksort that resumes from the previous function call and only executes one recursion. This would have been way more efficient, algorithmically speaking. But it would have also been way more complex, would have produced code that was harder to understand, and would have required addressing corner cases.
The thing is: I did not need the efficiency. This is a terrible implementation of Quicksort, but that terribleness does not really make a dent in the game's performance, knowing that the number of processes that need to be sorted at all times will never exceed 42 — which is a lot for the players of my game, but is nothing for an actual computer.
This solution that I came up with is a testament to the KISS principle ("Keep It Simple, Stupid"). It is also a good reminder that part of finding a good solution to a problem is to make sure that the problem is correctly identified.