I’ve wanted for a long time to describe in detail how SpaceMonger works. It’s been more than twenty years since I wrote SM 1.0, and there were a lot of innovations in SM 2.1 that I still really haven’t seen appear in any discussions elsewhere: I worked really hard to make SM fast and as smooth, even on the ridiculously limited computer hardware of the early 2000s.
Part of the work in making SM 2.1 was finding and using unusual algorithms that aren’t given much attention outside computer science literature — and part of that work was discovering and inventing new algorithms that, to the best of my knowledge, haven’t been published anywhere since. In this series of articles, I aim to fix that fact: It’s bothered me a lot that I’ve been hoarding some knowledge over the years, and it’s well past time that I share it.
So in this series of highly-irregularly-published articles (irregular because I don’t have a lot of spare time anymore), I’m going to explain how SM 2.1’s treemapping algorithm works, in enough detail that you could make your own renderer that is as fast as SM’s and can do on-the-fly updating and zooming and all that cool “magic” that it pulls off.
Now, that said, I’m not going to give you the actual original C++ code from it, for several reasons:
- Nobody in codes in C++ anymore if they can avoid it, and
- The share of programmers who can actually read C++ anymore is pretty slim, and
- StarDock is still selling a derivative of that C++ code, and I don’t want to impact their sales, and
- C++ is a terrible language for explaining anything at a high level.
(And no, I’m not going to apologize for the C++ bashing, because have you people seriously looked at what they’ve done to that language in the last ten years? I still love coding in C, but all the weird additions in modern C++ that try to make it more competitive with low-level languages like Rust and high-level languages like Python somehow manage to add successively worse and worse layers on top without actually fixing any of its core problems. I was fine with C++ when it was C-with-classes. But the current C++ that’s a giant pile of unpredictable template metaprogramming? No thank you. I’d rather code in BF.)
(Also, why now? In just a couple of weeks’ time, I’ll have been in my current job — the job I took after SpaceMonger — for ten years. It’s literally about to be a full decade since the SpaceMonger days, so it’s definitely time to share everything that happened then.)
const that make the code easier to understand for everyone.
I’m also going to do all the drawing/rendering using HTML Canvas, and using nothing more than basic canvas operations like “draw text” and “fill rectangle with color,” so that it’s obvious there’s no special sauce that makes this implementation browser-specific: The resulting algorithms should be easily-ported to any graphics system, any environment.
All of the code I write for these articles will be covered under the MIT License, which means you can reuse it for any purpose for any reason, including selling it.
So that’s the overview of what I’ll be doing here, and why I’ll be doing it. Below, I’ll update this article with links to the subsequent articles as I write them:
- Part 1: SpaceMonger Treemapping Redux
- Part 2: The Project [this article]
- Part 3: Sample Datasets and the Normal Log
- Part 4: The Data Pipeline
- Part 5: Basic Rendering
- Part 6: Agnostic Layout
- Part 7: Zooming and Panning
- Part 8: Fast Layout
- Part 9: Selection
- Part 10: The Knuth Check
- Part 11: Regexes and Pattern Matching
- Part 12: Sorting