2

So let me explain my problem a little better now (please reopen this question). I heard of markov chain theory when thinking about a method to generate procedural lines to build terrain.

The main thing that's generated is the map which can extend to infinity. At first I've built a demo with perlin-based procedural maps having a lot of various terrain features. It was even meant to be isometric, more like Sentinel. This proved to be too confusing to play on with the movement mechanics I had in mind. I had to reduce it to a much simpler tile based system. It's not only easier to grasp and navigate but it's looking a lot better too.

The map is generated using the Markov chain. The algorithm is fed a short human made terrain sequence. It then goes on and produce a map of any size mimicking the structure of the input.

So an example visual output may look like you see in the following image

enter image description here

Actually I experienced a similar thing that is described in the quotation ending up with this random lines:

enter image description here

So instead of having this random line I look for a solution to create little canyons from the first picture. First time I read about markov chain I thought WOW, take a human made line as input and let the algorithm proceed, sounds brilliant.

So how does markov chain theory actually help on creating this kind of terrain? If you think there is a better way to do this please suggest.

The map is generated using the Markov chain.

...confused me and I tought their actually is a markov chain algorithm.

DarkLeafyGreen
  • 69,338
  • 131
  • 383
  • 601

1 Answers1

2

I'm not sure if you know what a Markov chain is. A Markov chain is a system defined by state transitions based on probabilities. The next state is (by definition) based on the previous state.

A Markov chain is not a transform. It's not an algorithm for the modification of a system, it merely describes the system.

To describe your line system, you need to look at individual indices in your array and calculate the probability of a "jump". In the end, you'll be left with something akin to this:

idx 1: 20% chance for a jump
idx 2: 0% chance for a jump
idx 3: 15% chance for a jump
idx 4: 55% chance for a jump
...

This is trivial to program, but it does not aid you in making the lines straight. To make the lines straight, you don't even need a Markov chain, just iterate over all indices and make them equal to the previous index. It's difficult to see exactly what you're trying to do here.

David Titarenco
  • 32,662
  • 13
  • 66
  • 111
  • What you describe is not a Markov chain. In an MC, you'd have a transition probability depending on the *state* (in this case likely either the height or its "derivative"), not the current *time* (index into the array). – Fred Foo May 29 '11 at 20:56
  • Actually I try to generate terrain and a developer said he is using the markov chain algorithm to generate procedural random lines like you see in my picture, since the line or the points are represented by coordinates I thought there is a algorithm that can accomplish that...by its idea the markov chain algorthim seems to be really suitable for that problem; @larsmans, why you not provide things you know as an answer intead of just vote to close this question...? – DarkLeafyGreen May 29 '11 at 21:07
  • 1
    @ArtWorkAD: I'm sorry, but in my opinion you did not put enough research into this yourself. "Manipulating an array" based on "the Markov algorithm" doesn't mean a thing. Had you said, "generate random output based on a Markov chain," then I might have given it a chance. – Fred Foo May 29 '11 at 21:18
  • @ArtworkAD: FWIW, I have already explained the Markov chain sampling algorithm elsewhere: http://stackoverflow.com/questions/5502688/using-markov-chains-or-something-similar-to-produce-an-irc-bot/5502971#5502971 (skip over the training algorithm if you want to put in the probabilities manually) – Fred Foo May 29 '11 at 21:20
  • I edited my question and hope for votes to reopen it... – DarkLeafyGreen May 30 '11 at 04:32
  • @larsmans et. al. do you feel this question is now worth being reopened? – John Saunders Jun 05 '11 at 01:37
  • Fair enough, voted for reopening. – Fred Foo Jun 05 '11 at 15:40