Path-building game with dungeon corridors, rooms and scenarios

Hi,

I've only recently joined here so I apologise for any naive questions! I'm also not as clued-up on modern board games as I probably should be, so if people read what's below and say I should look at games X, Y and Z then that's fine with me!

A summary first of where I am at the moment:

I'm currently working on a board game idea which involves what I believe is generally called a 'path-building' mechanic, where you lay down (what I'm calling) square location tiles that have simple N, S, E or W exits (or combinations of...). The overall game concept is a cooperative rather than competitive experience, set in a dungeon with potentially multiple dungeon levels per game. The overriding theme is one of 'team building' and the design is aimed at early teens.

I'm not anticipating the game will feature much combat. The players will have various statistics and their strength can be reduced if they get hurt by traps and so on, but they aren't likely to have any direct combat with other creatures or characters, but if they do it will not be a frequent event. The main aim of the game is logic and puzzle solving. In that respect, it's more like a board game version of a text adventure, where brains are preferred to brawn most of the time.

I'm planning on having various cards for different things - Characters, Items, Treasures, Traps, Spells and so on. How many moves each player can perform in their turn will be based upon a stat rather than a dice roll. I'm torn between going with an empty game board 'grid' (to lay the location tiles on) or not going with a board at all. I'd also like the player's starting positions to be flexible, so sometimes they start together and sometimes they are split into different areas. In the latter, I'm assuming you'd need a board to define the outer boundaries of the 'level' so you could place the starting positions in each corner of the board's grid if those starting locations were movable tiles themselves.

That's enough of my brain-dump for now. Here's my current dilemma; how to populate the game with adventure-like puzzles, traps and so on for (most) locations but achieve this through card decks that allow the game to be different each time you play. In text adventures, a puzzle is solved by using an item collected many locations away. What type of mechanic in a board game would cater for that, where neither the puzzle nor the item(s) needed to solve it are guaranteed to be available during play?

I'm aware that some games use 'scenarios' (where you look up on a matrix of some kind) but that feels more like a 'choose your own path' type experience than a board game. I'd really like the game to use random cards as much as possible to assemble the traps, puzzles and encounters. How do other games achieve this?

Thanks in advance!