Rock Climber - Part 8

Español | English

Por fin pasaron los exámenes, aunque todavía quedan trabajos por entregar y dentro de poco comienzan de nuevo más exámenes.

Desde que me liberé de estudiar estuve trabajando (y jugando al Witcher 3) en hacer de nuevo la generación de las montañas para obtener un resultado más natural.

Me encontré con un algoritmo que era justo lo que quería hacer, se llama MidPoint Displacement (Desplazamiento del Punto Medio) que consiste en hallar el punto medio en un segmento, desplazarlo y repetir el proceso en los nuevos 2 segmentos que se generaron hasta que se cumpla una condición.

Una vez que leí y entendí la funcionalidad general del algoritmo, lo implementé de manera recursiva basándome en lo que alguien había hecho que tenía la ventaja de poder indicarle cuantos puntos tiene que haber en la recta en total. Al final si bien el algoritmo funcionaba, no daba los resultados esperados:

 

La línea verde es un Edge Collider 2D sobre el cual aplicaba el algoritmo, se puede ver como en el centro hay una línea recta eso no debería pasar.

Si bien podía haber seguido modificando el algoritmo, quería ver otra solución que alguien había propuesto (Ada Lovecraft) en la plataforma CodePens: 

http://codepen.io/ada-lovecraft/pen/jEPWBO

Como pueden ver, el resultado es mucho más natural, pero tenía un problema, estaba en JavaScript y pensado para Web, por lo que no podía simplemente copiarlo y pegarlo en Unity.

Así que me tomé el tiempo de analizar el código y ver que hizo, de esta manera pude traducir el código a C# y hasta ver posibles optimizaciones.

(Nota: el código si bien funciona, es ineficiente, se puede ver simplemente si cambian el valor "Iterations" de 5 a 9 y ver como se traba la PC un poco. Aunque cabe destacar que normalmente no se usaría un valor mayor a 8).

Aunque no podía ser todo tan simple, ya que no se muy bien manejarme con colecciones dentro de C# y no encontraba el equivalente a ArrayList de Java, por lo que decidí hacer mi propia colección genérica de elementos en las que luego iba a guardas los Vectores 2D para trabajar sobre ellos.

Por si hay alguno interesado, la optimización que le encontré al código es usar una Lista Ordenada (que agregue los elementos en orden) en vez de simples vectores, si bien no testie que de verdad sea una solución, a simple vista fue lo primero que noté.

Así que ahora puedo tener resultados mucho más naturales:

Otra observación sobre este último algoritmo es que este se basa en cantidad de iteraciones que se hacen sobre la recta, no como la implementación anterior, por lo que si ponemos un valor de 9 para iteraciones, podemos tener más de 200 puntos.

Por lo que ahora lo que hace falta es cambiar el código para que el terreno se haga verticalmente y crear un mecanismo del cual pueda, una vez generado un terreno, poder guardarlo. Esto va a ser lo más importante del generador de niveles ya que va a ser lo que me va a dejar elegir y guardar los niveles que más me hayan gustado.

-L

----------------------------------------------------------------------------------------------------

English

Finally the exams passed, although I still have work to do and a new set of exams are coming shortly.

Since I was available after the exams, I've been working (and playing Witcher 3) with a new way of making the generation of mountains to obtain a more natural result

 

I found an algorithm that did just what I wanted, It's called MidPoint Displacement and its job is to find the midpoint of a segment, move it and then repeat the process with the new 2 segments until a criteria is met.

Once I read and understood the general functionality of the algorithm, I implemented it recursively following an approach I've seen online which has the advantage of indicating exactly how many points you want the segment to have in total. Finally the algorithm did work but it didn't give the expected results:

 

 

The green line is an Edge Collider 2D, to which I applied the algorithm, It can be seen in the center that there is a straight line, which shouldn't happen.

 Although I could keep working and modifying the algorithm to make it work, I wanted to check another solution that someone proposed (Ada Lovecraft) on the platform CodePens:

http://codepen.io/ada-lovecraft/pen/jEPWBO

As you can see in the link, the result is much more natural but I had a problem, it was made in JavaScript and made for Web, so I couldn't just copy it and pase it to Unity.

So I took the time to analyze the code and see what she did, this way I was able to translate it to C# and even see possible optimizations.

(Note: The code although it works, is inefficient, you can see it if you change the parameter "Iterations" from 5 to 9 and see how your PC takes a time to process it, although it's important to mention that someone wouldn't use values bigger than 8).

But it couldn't be so easy, as I don't know yet how to handle correctly with Collections in C# and I couldn't find a proper equivalent to an ArrayList from Java, so I decided to create my own generic collection which I would later use to store the 2D Vectors to work with them.

If there is someone interested, the optimization I found to the code is to use an Ordered List (which adds elements in order) instead of simple vectors, I didn't test this theory but it was the first thing I noticed when I looked at the code.

Now I can have much more natural results:

Another observation about this last algorithm is that its based on the number of iterations it does to the original segments rather than on the number of total points, like previous implementation, so if we put an iteration value of 9, we might have more than 200 points

So now I need to change the code so that it makes the terrain vertically and create a mechanism that will enable me to save the terrain once it's generated. This is going to be the most important aspect of the level generator, as it will let me save the levels I chose to be the best from all the generated ones.

-L