I'm new to planning out my maps ahead of time. I've used plenty of premade ones, dungeon tiles, etc. But, I want to really challenge my players and help them feel like they're discovering a world.
So, I put my pencil to graph paper, and nothing. It's like writer's block that won't go away.
How do you make your basic idea fit on that paper? Where to begin? I'm probably making it harder than it is, but any pointers would probably help me out. It turns out, graphing these battlemaps is friggin' hard!
I saw this about seven hours after you posted it, and it took me some time to formulate a response, as battle maps just come naturally to me (most of the time; when I can't make my own, I tweak a published one). Here is my best attempt at advice, and perhaps others can elaborate further:
First, are you using 4 line per inch graph paper, or 1" grid paper? If you're using old school graph, that may be one problem. 1" grids help me a lot when I need to visualize my encounter. Just look up downloadable 1"grid PDFs, or use Incompetech's customizable system (all free). With the latter, change the size to 1 line per inch, and try the lowest possible line weight and a light color (to save ink), since you only need to barely see the grid. However, this may not be the problem.
Visualize the setting. A cave is a good place to start, since the shape is completely up to you. Rough-hewn walls for a naturally eroded cave, smoothe, symetrical walls for something carved by dwarves, or a combination of the two. Next, envision your environmental hazards and traps: lava pools, pits, falling rocks, cave-ins, etc., and place them strategically. Remember that you're not trying to kill the player characters, nor are you their babysitter. They need opportunities to use those well-earned skills to get out of trouble. If you're like me, you'll enjoy their successes as much as their failures.
Now, what inhabits your cave? Look into your Monster Manual, Monster Vault, whatever you use, and start off with level-specific creatures (using the "monsters by level" index), and find monsters that would inhabit your setting. If the characters are level 3, your creatures should span from level 1 to 5, level 6 for a boss. Be mindful of the ammount of monsters per level, for once again, you're not trying to kill them. Be sure and throw a mix of creatures at them to make it interesting. There are formulas in the books for building encounters, but it's all up to you in the end.
Now, detailing your map. Let's say it's a cave that was once mined by dwarves, but hobgoblins killed off the miners and now use it as a base from which they orchestrate raids. Draw in the details of old mining carts and rails, a pickaxe and other tools lying about, maybe some tables with old parchment and flagons / plates, etc. Then draw in the crap that hobgoblins and their ilk may leave lying around: broken crates, refuse, dung-piles in the corner, bones, etc. Also, consider what each room was / is used for. There's an entrance, halls, mining areas, sleeping quarters, dining area, whatever. You may also have a final 'boss' area. You'll want to position it in way that the characters likely end up there last, but without railroading them. Maybe make an adjacent room equally accessible. In this 'boss' area, throw in some traps and hazards that make the final encounter a real challenge.
Finally, don't forget loot. Place it in hidden spots along the way, suitable to the PCs' levels, and don't forget to make it sweeter in the final encounter. You can also throw in an NPC somewhere along the way, or in the final encounter, to add story elements to the area, like a dwarf who needs to get out. This is all just an example, and if I've not made something clear enough, or completely missed the point, ask and I'll elaborate. I hope that others will offer their own advice as well. Good luck, friend.
Part of the great joy of D&D is making maps! I like to mix it up too, as far as using published maps and drawing my own. I also throw in some Hirst Arts dungeon creations of my own when they venture into a dungeon. You mentioned wanting your players to discover the world before them.
One method that I have employed in the past is to take some black construction paper and cut it out to cover the different rooms of the dungeon. There are a few published maps (like the one in the D&D redbox) that are complete dungeons. Let your players walk into the room and see the map lying on the table, all covered in black except perhaps for that first room. There is something about the prospect of all this unknown area that pushes the players to explore, a little more I think than laying out a map at a time.
I have done this to great effect with a map that I have drawn too. Purchase a few color wet-erase markers for quick depictions of fire, ice, other effects too. You can quickly put down, move and remove those auras, zones and effects. of course, you don't need great artistic skill to draw a few rooms. Your players won't care about that as long as your oral descriptions are colorful!
I am always on the lookout for creative ways to use maps. But it was always hard for the players not to meta-game when they could "look down" on the whole dungeon (like the red box map and a few others), and then try to pretend that they didn't know what was on the other side of the door.
The black construction paper made it possible to reveal a room at a time. Also, I would write a number on the black construction paper so I knew which room they were entering and what was waiting inside, since some maps have multiple paths that the adventurers could take.
Paizo publishing's dry-erase "Flip-Maps" are great.
They usually have a detailed, generic design on one side - a small dungeon, a forest area, a tavern, a cave, or that sort of thing. On the other, they have a blank 1" grid. The blank grid is a great alternative to 1" graph paper, the detailed side provides a good area for improvised situations, and both sides can be drawn/sketched on with dry-erase markers to add details.
As for the smaller, more traditional graph paper with the small squares: that stuff can be handy for drawing your own, smaller-scale, personal DM maps ahead of time, to keep in your notes. When needed, you can refer to the maps in your notes to sketch out areas as the PCs explore them.
Keep in mind that older editions of D&D had most of the exploration taking place in the players' imaginations - there was no 1" grid in most D&D games before 3rd Edition came along. Players might sketch maps on smaller-scale graph paper as the DM described them in old-fashioned dungeon-crawls through mazes and such, but this was, in general, optional for many games. This doesn't have to change: for 4th Edition games, the combats can be tough to do without battle map visuals, but you don't have to portray every square of the dungeon with 1" grids - instead, bring out the battle maps when needed for combats, and narrate your way through the non-combat trips down twisting hallways and so on.
Trying to solve out-of-game problems (like cheating, bad attitudes, or poor sportsmanship) with in-game solutions will almost always result in failure, and will probably make matters worse.
Gun Safety Rule #5: Never point the gun at anything you don't intend to destroy. (Never introduce a character, PC, NPC, Villain, or fate of the world into even the possibility of a deadly combat or other dangerous situation, unless you are prepared to destroy it instantly and completely forever.)
Know your group's character sheets, and check them over carefully. You don't want surprises, but, more importantly, they are a gold mine of ideas!
"If it ain't broke, don't fix it." It's a problem if the players aren't having fun and it interferes with a DM's ability to run the game effectively; if it's not a problem, 'fixing' at best does little to help, and at worst causes problems that didn't exist before.
"Hulk Smash" characters are a bad match for open-ended exploration in crowds of civilians; get them out of civilization where they can break things and kill monsters in peace.
Success is not necessarily the same thing as killing an opponent. Failure is not necessarily the same thing as dying.
Failure is always an option. And it's a fine option, too, as long as failure is interesting, entertaining, and fun!
"Broken or not, unbalanced or not, if something seems to be preventing the game from being enjoyable, something has to give: either that thing, or other aspects of the game, or your idea of what's enjoyable." - Centauri
