My first time DMing was with a bunch of older players. They of course went completely off the beaten path and seemed to disregard every hook for anything I had thought of doing. I decided to wing it... Soon time travel and clandestine meetings with the Smurfs came into play...
It turned out to be great fun. Before long, I was sought after as a DM.
I have played out shades of the first idea with some success.
I like the potential of the second idea.
The third idea could be great fun, depending on the players. Some players are genre nazis... I have tried all sorts of time travel, genre twisting, and system switching. Most like a change of pace, but some can be very against it.
Thoth-Amon gives good advice, give the players a little survey. See what they like, expect, want, would accept, etc. Then you can create a game that fits them perfectly.
Bookmarks