It's good to have people here from things like AMOS and STOS - nothing beats an idea that's been stewing for 25 years!
AGK really is the language that lets you complete your ideas and hit a large number of devices with it as well.
I think it's worth investigating the manual controls for physics collision. For example, if you made a backdrop sprite, you could add however many 'lines' to it as you need - like a horizontal line with segments at varying heights. It's actually quite straightforward, I had an experiment a while ago using a big planet sprite, and generated it with a memblock and added a collision shape all around it. Theres a game in there somewhere but I'm too busy to keep on it, it serves as a good example of manual collision lines though. It's surprising just how many lines you can add without ruining the performance - for a scrolling horizontal landscape I'd say it's definitely worth a shot. Maybe generating the terrain using a cut down perlin calculation and some memblocks would be an idea - save yourself the trouble of designing levels
Additional obstacles and details can be added as separate sprites... like physics sprites for puzzle elements... maybe a bit like a 2D Pikmin, where you might have to pile a load of critters onto one side of a ramp.
The old fashioned way would be to use the bitmap data, like if you load an image and convert it to a memblock, you can then affect the memblock (to blow bits up if you like) - a lemming might dig into the terrain or even build on it, so you'd adjust the memblock data and convert back to an image when done. AppGameKit would actually make a pretty decent language for a lemmings game.
Really, this isn't a problem you have, it's an option... you could use a memblock image to replicate Lemmings or Worms, but you'd have to deal with collision yourself using the raw data - not a huge undertaking once you know how memblocks work. The other option is to use physics sprites and a chain of 'lines' - but that makes terrain modification in game very difficult. The 2 techniques don't really play well together, but at least they work nicely in AGK.
Personally I'd love to see a Worms style digging game in AppGameKit - and I have an example somewhere that shows the techniques nicely... in fact I have a 2D destructable terrain example and the big physics object with the chain of lines as an example as well, just say if you want me to upload them.
I am the one who knocks...