Yeah, there's flexibility and then there's having a complete sandbox, and we're more in the former camp.
The levels are most directly inspired by Lode Runner:TLR (awesome game from the early 90s which is now freeware, by the way, if you've not played it) in terms of how they are basically flexible puzzles. However, Lode Runner: TLR puzzles tended to be pretty one-note in solo play in particular, really only opening up when you had two players playing at once (on one keyboard, ahem). Because SH is top-down rather than side-view, that lets us make better use of the space than a game like Lode Runner (or indeed AVWW) can.
It's just too different dynamics, and when you're talking about a single screen at a time (no panning) then having that screen real estate matters. The individual screens in SH have more tiles than Bomberman or Zelda 1, so each level can be more intricate. Like Zelda dungeons, a given level can also span more than one screen; but those are more the minority rather than the majority outside the overworld, because the multi-screen levels both take us a lot longer to design as well as are a lot more advanced-feeling to play.
Anyway, even Lode Runner is a pretty bad analogy when you get right down to it. This game is much more action-oriented than that in terms of how you execute your plans, but also more planning-oriented in how you set up your plans. Each level starts out with you invincible like happens in AVWW (or Zelda 1), and then you get to look around as long as you want, then make a run for it. The roofs on buildings, or darkness or hidden tools/traps in destructible objects, usually makes it so that you can't plan out everything if you haven't tried the level ever before, though. There is a pause function that lets you still see everything that's going on on the screen, and in fact it shows little denotations for what kind of Grays each on-screen Gray is.
Depending on how a level has been designed (and the 80+ levels we already have in place really vary in this, a trend I expect to see continue), the level of linearity can really vary. Some levels really do just have one intricate sequence of events that you have to go through, but how you deal with the monsters along the way determines if you meet the bonus objectives or not. A few levels are very open-ended and can be tackled in numerous ways, mostly involving more skill than tactics. Most levels are more in the middle, requiring a mix of skill and tactics, and allowing for some flexibility in order of operations that can make a great difference in the overall outcome.
At core, this is kind of a puzzle game in the same sense that AI War or Zelda 1 are puzzle games: there's all this realtime action-y stuff in all three games, and longer-term goals that you're trying to accomplish (self-set in AI War, set by the adventure storyline in Zelda and SH), and then there's these individual spaces that you come across that have environmental puzzles for you to unravel (procedurally assigned planets in AI War, dungeons or specific screens in Zelda, levels in SH).
It's a bit hard to compare it to other games, because honestly I don't know of anything else that does things like this. But I did start from the premise of wanting to make a Lode Runner type of game from the top-down rather than the traditional side view, and the rest of the game grew from there (in the same sense that I wanted to make something kind of like Supreme Commander in space when I made AI War). As with AI War (and indeed, before AI War even existed), SH grew like crazy compared to its original concept and took on much more unique overtones.
