Markov chain.. translation of wikipedia please?
As tempting as it is to paste in the Wikipedia article run through automated translation into Swahili or something...
Basically, you can think of a Markov chain as a state machine, with each state-to-state transition given a probability. So you might have a set of three states - A, B and C - which have the following probabilities for transitions:
A->B 80%
A->C 20%
B->A 50%
B->C 50%
C->C 20%
C->B 80%
Where - for example - if you're in state A, there's an 80% chance you'll move to B next, and a 20% chance you'll move to C. Note it's also quite possible to have a transition from an item to itself, e.g. C has a 20% chance of moving back to C.
Then, you can generate a series of items out of the Markov chain by doing a random test for each step. So we might get:
A (random: 73) -> B (random: 54) -> C (random: 12) -> C (random:49) -> B (random: 32) -> A
You can use this to generate all kinds of linear things in a patterned/structured manner, which makes them great for things like platformer level construction. Say you have four level components, a ramp up, a ramp down, a low bit of land and a high bit of land; if you just pick randomly from the list, you're likely to get all kind of weird-looking geometry, like a ramp up immediately following a ramp up, looking like sawteeth. On the other hand, you can construct a Markov chain, so that , say:
low ground -> low ground (70%)
low ground -> ramp up (30%)
ramp up -> high ground (70%)
ramp up -> ramp down (30%)
high ground -> high ground (70%)
high ground -> ramp down (30%)
ramp down -> low ground (70%)
ramp down -> ramp up (30%)
- like this, you'll still get a randomly-varying level, but the ground height won't have any sudden discontinuities in it (unless you add some discontinuous transitions to your chain, which you might want to do).
Also: Bloody hell. I just looked at the Wikipedia article to see what was so hard to understand about such a simple concept, and... that is probably the most impenetrable article I've read all week! Yay Wikipedia! ;-)