Flying memes

Grazie all’appuntamento settimanale con i Ruby Quiz oggi sono venuto a conoscenza del Midpoint displacement algorithm, utilissimo per la generazione di una spezzata che simuli la silhouette di una catena montuosa.

Questo algoritmo basa la sua operatività essenzialmente su di un array contenente le altezze dei punti che compongono la spezzata. Tale array all’inizio presenterà solamente due valori (capo e coda dell’intero profilo che vogliamo creare), entrambi settati a 0.

Il cuore del Midpoint displacement algorithm si basa sull’iterazione sull’array sopra indicato calcolando per ogni coppia di punti un nuovo elemento contenente la media delle altezze dei due punti vicini variata di un certo valore random. Eseguendo quest’ultimo passaggio un numero sensibile di volte otterremo una linea spezzata molto simile alla seguente:

Il risultato appena mostrato pur non essendo del tutto deprecabile mostra comunque una linea che difficilmente si adatterebbe al profilo di una catena montuosa (forse delle Dolomiti); quello che ora dobbiamo fare è ‘smussare’ gli sbalzi di altezza tra i vari segmenti e il modo migliore per ottenere questo risultato è sicuramente quello di ridurre il range di valori dell’apporto random ad ogni interazione.

Prima di mostrare il risultato finale vorrei condividere il codice sorgente dell’applicativo (scritto in Ruby); il programma si divide in due sezioni: la prima genera l’array delle altezze, la seconda lo stampa utilizzando Shoes.

require 'enumerator'

# ==== PRIMA PARTE  ====
# calcolo delle altezze

segments = [0.0,0.0]; midpoints = []
max_randomness = 40
times = 5
app = {:width=>600, :height=>200}
boundary = 10

while times > 0  do
  segments.each_with_index do |b,i|
    next if i == 0; a = segments[i-1]
    midpoints << ((a + b / 2.0) + (rand(max_randomness) - (max_randomness / 2.0)))
  end
  segments = segments.zip(midpoints).flatten.compact
  max_randomness -= 5; times -=1;
end

segment_width = (app[:width] - boundary*2) / segments.size.to_f

# ==== SECONDA PARTE ====
# stampa delle altezze con shoes 

Shoes.app (:title=>'Dreaming mountains', :resizable=>false, :width=>app[:width], :height=>app[:height]) do
  stroke white
  strokewidth 2
  background black

  segments.each_with_index do |b,i|
    next if i == 0; a = segments[i-1]
    line (f = (segment_width*(i-1) + boundary)), a + app[:height]/2.0, (f + segment_width), b + app[:height]/2.0
  end
end

Ed ecco il risultato dell’algoritmo appena mostrato, notate come la spezzata sia meno ‘spigolosa’ della precedente.

Alla prossima!

Tags: Midpoint displacement algorithm, Ruby Quiz, Shoes