This is an excellent question, and has now sparked a blog post:
http://christophermpark.blogspot.com/2011/04/q-in-what-ways-is-valley-without-wind.html 
Which I'll copy here for those in the forums:
Question from leekster: I was just curios how much of the game is procedurally generated? Is it in the vein of Dwarf Fortress, where all of it is random? I understand monsters can't be random due to all the animations and textures. But are spells randomly generated? Thanks for your help.
Answer from Chris: Well, this is a really good question, but also a really complicated one to answer. I could answer you with a lot of technical details, or I could try to answer the spirit of your question. I suppose I'll try to do a bit of both.
Dwarf Fortress As Your ExampleFirst, to clarify, though: Dwarf Fortress is not nearly "completely random" as you imply. This isn't a criticism of that game, but I think that if I'm going to be able to answer you we have to define our terms a bit here. I've only played a little bit of DF, but for the most part I find that it has lots of pieces, but and high randomization with how those pieces fit together, but the overall algorithms are anything but random.
For instance, in DF all the various ground types are predefined -- Sandy Clay, layers with Aquifers, and dozens of others. So far as I know, all the enemy and dwarf types are also predefined -- but boy are there are a lot of them. In terms of the world map regions, those are also defined by the designer, but plentiful. They are "random," but not truly so -- you get clumpings of regions, you get islands, you get rivers, etc. This is randomized algorithmic, not pure random. You don't get things like a water tile next to a lava tile next to a grassy tile next to a snow tile; things are randomized only in the bounds where they make some kind of sense.
So in a lot of senses, DF is not very random at all -- I would argue that 80% of the game isn't random at all. This is also true of AI War, which is also known for being pretty random, if not so plentiful in its pieces as DF. But that other 20% that IS randomized is what makes the game
feel "completely random." That's a really important distinction.
AVWW Is Mostly Like ThatNow, to answer the spirit of your question: from what I have seen of DF, I would say that AVWW will have a similar degree of randomization overall. AVWW will also have a similar or greater degree of randomization to AI War. The tricky thing about this sort of algorithmic randomization, though, is that it requires a
ton of input in order to generate a lot of randomized output. AI War has had about two and a half years to build up, and DF has had... I want to say seven years, but I'm not positive. Maybe as little as three.
At any rate, earlier in their life cycles, both DF and AI War felt "less random," even though they were just as random, because they had less content. If you have three things to choose from at random, that doesn't seem very random even if it is. If you have three million things, it would seem very random to choose between such items even if it's not random at all, or only partly random.
AVWW, of course, won't ship with three of anything -- nor with three million. My hope is to have dozens or hundreds of each type of thing in the game at 1.0, though, so that there's a high degree of "this feels random" that we can then continue to build on with free DLC and paid expansions as we have with AI War in the two years since it came out. My expectation is that AVWW will feel considerably more random and content-ful at 1.0 than most games on the market, but that it will truly start becoming
crazy post-release, assuming players are interested in that.
Specific ExamplesSo, that was all pretty general and vague, but hopefully it answers the
spirit of your question, which I think is important to do. Now to a few specific examples:
Monsters of course aren't random because that wouldn't have much meaning. How do you create a random monster? The closest thing I can think of is spore, and I think we can all agree that even after years of a large company pouring in resources to creating "random" creatures, the result was underwhelming. This is a case where I think that human creativity trumps randomness, and if you have enough monsters that are interesting then you wind up with something that feels varied and interesting, which is the point.
That said, the way that monsters are seeded into the world is hugely random, although there are various "population patterns" that we use to make sure that things don't fall out of bounds -- this is akin to making sure there's no lava or tropics in the arctic zones of DF world maps. Algorithmic randomness is a big pattern in all the games mentioned here.
Spells are pretty much the same sort of story. They aren't random because I'm not sure what that would really mean. In the closest example to "random" for spells, Magicka, most of those spell combinations that players "discover" were actually anticipated by the developers and programmed in. Those art effects and the way the spells work has to come from somewhere. Don't get me wrong, their approach was brilliant and fun, but it also wasn't very random in the case of most of what players encountered -- it only
felt random.
Of course, they did have some genuine randomness built in to the areas that they didn't specifically code, and some of those devolved into some balance-breaking superspells that they had to deal with. Not unexpected, and not even tragic, just the cost of doing business when you have any random component.
At any rate, spells in AVWW aren't planned to be random or combinatorial, although we do have a pretty interesting slots system that we'll be unveiling soon. Basically letting you customize and combine various types of items and equipment to get some more unique, if not random, results.
More to the point,
which spells you get at any given time will be pretty random. You have to find the right pieces to make these spells, and as you level up you'll want to also craft higher-level spells. So if you get a Fireball I gem, you won't just use that for the rest of the game because it's your favorite spell. You'll eventually craft Fireball II and maybe even Fireball XIV if you play that long (that's like 140 hours in one world to get a level 14 spell, we estimate). So your equipment loadout is going to be heavily random as well as changing on an ongoing basis as you explore around and craft new stuff.
Terrain is another good example of where algorithmic randomization comes into play. When you look at the DF world map, for example, all the worlds are different in their details, but their very broad outline is always the same, right? Cold arctic and antarctic at the north and south, a realistic temperature spectrum between them, and water in realistic bodies with one or more land masses in between them. When you generate a new world in DF, it looks like a reasonable facsimile of a world, not like some cut-up messy
soup of a world.
Through my work on AI War, what I've really found is that it's important to have multiple layers of randomization. If you just have one layer, even a really good layer, it doesn't feel that random. If you have ten layers each with some hand-crafted parts and some random parts, you get multiplicative complexity that feels
very random -- and yet still also makes sense. This is something you can also see evidence of in the DF maps -- you have regions and subregions and types of ground layers and hostiles and so on, all nested within the overall world creation algorithm.
Terrain generation in AVWW works in much the same way, in that there are some broad not-that-random-but-still-somewhat-random algorithms in play, and then nested within that are many layers of randomness. So far we're only partly through actually getting those layers all up and running, but as each layer comes online it makes the game leap forward in terms of how varied it is. Hopefully by our next video I'll be able to show off the next major outdoor layer, which I'm quite excited about finally getting to.
Characters are another good example of randomization. Sure, we only have x number of sprites (right now 2, but hopefully about 60+ by the time we launch 1.0), but there's a ton more to a character than just their visual look. In terms of names, there are literally a few million possible combinations of first and last names per sprite. In terms of actual stats, we have a system of stats (physical attack, magic defense, etc) that get randomly rolled per character out of a pool of points. This is pretty familiar to any western RPG, really, but we don't let you re-roll. You choose from the characters you meet, which has a pretty interesting element to it on its own.
So that's a few examples of our philosophy of algorithmic randomization, anyway.
Randomization Vs Customization 
I should also note that when it comes to "random" spells or weapons, perhaps the question was if they would have randomly-rolled stats. That's something that equipment in games like Diablo and Borderlands has. To me, that's a system that has really been done a lot elsewhere, and we're going a different way -- customization over randomization when it comes to equipment.
In AVWW, you never just find a spell or a sword lying around -- you find the
components you need to
craft such things lying around. That's an important distinction, because each component has more than just a single use. If you find a Shotgun of Scoped Awesomeness in Borderlands, but you hate shotguns, you have nothing you can do with that weapon but give it to an ally or to sell it. Or use it despite the fact that you hate it.
When you're finding components instead of finished goods, there is still randomization in what you're finding, but it's less random and more directed-by-you in terms of what your final goods are. If you hate gatling guns, you never have to built one. You can build swords and shields and other medieval weapons instead -- and then jack them up with magic so that they rival the power of this modern weaponry you're forgoing. Or you can jack up the gatling gun with a fire gem, if you want to go a completely different way.
What we are
not doing is is having fire gems that have variable stats. To me, that just really devalues what a fire gem even is, and ultimately makes all weapons and spells pretty similar except for their visual look. Instead we have, for instance, longswords, broadswords, short swords, and rapiers, all of which have differing base stats, and of which you can craft different levels. So a Level 10 Longsword would crush a Level 5 Rapier in a fight, of course, but if you prefer the stabbing action of rapiers to the slashing ability of some of the others, you can overall craft more Rapiers with varying custom modifiers and abilities as you play the game. For a while maybe you have a rapier with a strength crest, and later it's a fire gem, and even later after you get to the point of having two slots maybe it's two things.
In Closing
This is a huge topic, and it's something I've been meaning to write about for this game for a while -- thanks to leekster for asking the question! I didn't cover nearly everything here, but it should give you a pretty solid idea of the general approach we're going with. It's a good mix of hand-crafted, random, and customizable aspects, which we think players will find unique and rewarding. And suitably vast, in terms of creating a pseudo-infinite world, of course!
