Ah right, if you've not seen it already I'd look into something like Spelunky's blended method so you end up with some randomisation but core paths are always made.
Cool, I'll look into it
