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.)
So instead of posting the original C++, I’m going to write an equivalent renderer, from scratch, in pure JavaScript, and describe it here as I implement it. That way, I can explain all the details, and you can see both the problems as I introduce them, and the solutions I derived.
Why JavaScript? Several reasons:
- JavaScript is a high-level language, so we can talk about the algorithms, instead of talking about the proper time to call
free()ordelete. - Pretty much everybody can read and write some subset of JavaScript these days: It’s as close to a universal language as programming has.
- A JavaScript implementation is usable in lots of environments, from websites to local apps via Electron.
(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.)
The code will be both posted here, with explanations, and the final JavaScript library will be in a repository in my GitHub account, so if you just want to understand the algorithm, you can read here; or if you just want to use the final implementation, you can just grab the repo (when it’s actually implemented).
I’m going to use modern ES6 JavaScript, so it will either need to run in a modern web browser, or it will need to be transpiled if you want to run it in an older browser. That said, I’m going to avoid using weird JavaScript features that are unlikely to be readable to people not intimately-familiar with the language: The real reason for using modern JS is so that I can use language features like 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
