#4 - Jan. 4, 2012, 7:50 a.m.
The exterior landscape will for the most part be static, but with pockets of randomness (this doesn't include monster spawns which are still quite random). You'll always know where the towns and roads are, and know the edges of the map. We felt that exploring the exteriors to find landmarks and quest areas wasn't very compelling. It's also more productive for co-op to be able to say to a friend 'Let's meet at this shrubbery' and everyone knows how to quickly get there every time. Dungeons are more linear in the way that content is encountered, so they can be randomized quite a bit and you're not very likely to be just running around aimlessly. Iif you do hit a dead end you're at least assured you encountered plenty of battle (and thus loots) on the way.
So while the exterior is largely static, within that defined landscape there are literal square holes (from small to huge) and within those empty square holes a great number of possible pieces can be dropped in. And they're chosen randomly. So you may play a few games and always see empty terrain in the same place, but on your next playthrough you'll instead have a broken down wagon appear and a quest giver that needs you to go kill a unique fallen shaman who stole his tools to fix it. And maybe the playthrough after that the sqaure puzzle piece is a short dungeon to explore with a big chest or mini-boss at the end. Ideally it'll encourage exploration of the exterior zones over and over, hoping to find that a rewarding adventure has appeared.
Dungeons on the other hand are completely randomized, same as Diablo II.* All of the halls and rooms and all the bits are shuffled around and it's all different every time. Some of the rooms themselves will offer unique quests if they're rolled up, and in some cases individual rooms themselves have those square chunks missing and within those randomly chosen rooms a number of random events can occur.
It's a bit involved to explain, but very simple in practice (I believe some images of the square puzzle pieces were actually shown at a BlizzCon?).
*Some small "dungeons" are completely hand crafted and won't include randomization of layout at all, but these are generally things like wine cellars or other underground areas of a few rooms or less.
