I'm back from my unannounced half-year hiatus. After hitting my little tech demo milestone last August, I tried some more new avenues on the force-directed layout approach but continued to hit the same fundamental wall. I needed to take a break to generate some new ideas, and also to devote some extra attention to helping someone I care about through a difficult time.
The break was good, and eventually I found myself reimmersed in the problem. I went back and did a much more thorough literature review, turning up all kinds of sources I had missed before. After spending a bunch of time poring over papers and books on graph drawing, I belatedly discovered OGDF, the Open Graph Drawing Framework. OGDF is more specifically focused on graph drawing than the Boost Graph Library, and it contains an algorithm that seems extremely suitable.
I've managed to integrate it in a basic way over the past couple of evenings, and the early results look promising:
As you can see, the new algorithm can handle quite large layouts with little difficulty. The aesthetics will need some work, obviously, and there are a few edge crossings happening with the current naive hall routing code. So, the next trick will be to perform some kind of compaction on these maps to bring it all in closer and hopefully do away with the grid-aligned, circuit-board feel it presently has.
Well, that's plenty of excitement for one night. If I can get the compaction nailed down in a decent way, I'd like to move on to putting more interesting content in levels, such as puzzles. I'm less interested in worrying about hack-and-slash mechanics right now; any game can do that, and I want to focus on mechanics that are enabled by the graph structure. I'm thinking a lot about ZZT.