The week after I posted "Dealing with Randomness", our prof brought with her a guest who is working in artificial intelligence with the downtown prof. In the hopes of finding a solution to the level generation problem, I and another group member asked if there was anything we could do to solve our issue.
"This sounds like a Markov Model," was the reply.
I didn't know what she meant by that, other than it had something to do with artificial intelligence (I later discovered it would be covered in a course I was not taking). So I had to go search on the topic online, hoping I would find the cure-all to our problem.
After researching for a full day on Markov Models, I finally found something similar enough to our problem to work with. From what I gathered a Markov Model usually deals with determining the next state of something from the state it is right now and not from the states it was before. Upon looking at the algorithms I knew I would be beat; using linear algebra to calculate something I thought would be as simple as tiles just added to my headaches.
The models did not seem to have any correlation to what I had in mind for level generation until I found out about Hidden Markov Models (they really were hidden from me for a while!). One Hidden Markov Model is called the Virterbi Decoding Algorithm (VDA). VDA doesn't know or assume the actual state of something, it instead relies on the previous sequence of states the something had to calculate the most likely state it should be in now. That seemed more on the lines of determining which tile should be placed beside which! The challenge now was to translate the VDA formula into code I could use to make the level generation.
It took the remainder of the week to learn from YouTube videos VDA and write similar code needed to do the job of level generation for our game (though it is not perfect by any means). All I have to do now is tweak a few variables and I could make a water level, a mountain/grass land, etc.
The code eventually came down to four percentages, based off the four tiles that make up each level. If I wanted more Grass, for example, I would increase the Grass percentage and the map would shape differently. It isn't perfect, and the results are not always as expected, but that is the way with randomness, right?
