峠のTaisaiがナイズルを(ry
某MMOとは関係ナイです。
粘菌っぽい動きをする何かを迷路に置いて挙動を観察してみるプログラムです。
プログラムの理論的な根拠はありません。
大雑把に連立拡散方程式で粘菌の伸び縮みと餌信号伝達を時間発展してみただけ。
densityが大きいと粘菌が濃く見えるような感じです。
迷路条件
- 粘菌は初期時刻でスタート位置にいます。
- 餌はスタート位置とゴール位置に等量置かれます。
粘菌の挙動
- 時間が経つごとに伸びていく
- あんまり伸びるとマズイのでそれなりに形を保とうとする(自己組織化っぽく)
- 餌があると信号を体内に伝達していく(信号は時間で減衰する)
class Nenkin class Point attr_accessor :x, :y def initialize(x, y) @x = x; @y = y end def ==(other) other != nil && @x == other.x && @y == other.y end end # 進行方向 @@directions = [Point.new(-1,0), Point.new(1,0), Point.new(0,-1), Point.new(0,1)] # イプシロン @@eps = 1.0e-10 # 進行時間単位 [時間] @@dt = 0.1 # 拡散速度 [時間^-1] @@velocity = 1.0 # 餌減衰係数 < 1.0 @@decay_food = 0.75 # 餌シグナル伝達相対速度 @@trans_food_signal_weight = 100 # 粘菌減衰係数 < 1.0 @@decay_density = 0.999 def initialize # マップ構造 @map = [] # 粘菌密度[無次元]:xy積分で1 @density = [] # 粘菌拡散速度 [時間^-1] @d = [] # 粘菌密度時間発展差分[距離^-2]:Δx=Δy=1.0として陽には現れない @density_delta = [] # 餌シグナル強度 @food = [] # 餌シグナル強度時間発展差分[距離^-2]:Δx=Δy=1.0として陽には現れない @food_delta = [] end def run load_map total_count = 1000000 output_count = 10 (total_count/output_count).times {|i| output_count.times{|j| decay_and_rethrow_food_signal @@trans_food_signal_weight.times{|k| trans_food_signal } move_density decay_and_reborn } printf "[Time=%5.5f]\n", i*output_count*@@dt print_map } end def load_map DATA.read.each_line {|line| @map.push line.chomp.split(//) } @map.each_with_index{|line,i| line.each_with_index{|c,j| case c when 'S' @start_point = Point.new(j,i) @map[i][j] = ' ' when 'G' @goal_point = Point.new(j,i) @map[i][j] = ' ' end } } @map.each{|m| @density.push Array.new(m.size, 0.0) @d.push Array.new(m.size, 0.0) @density_delta.push Array.new(m.size, 0.0) @food.push Array.new(m.size, 0.0) @food_delta.push Array.new(m.size, 0.0) } @d.each_with_index{|line,i| line.each_with_index{|c,j| @d[i][j] = is_passage?(Point.new(j,i)) ? @@velocity : 0.0 } } # 粘菌はスタート位置に配置される @density[@start_point.y][@start_point.x] = 1.0 # 餌はスタート位置とゴール位置に配置される @food[@start_point.y][@start_point.x] += 1.0 @food[@goal_point.y][@goal_point.x] += 1.0 end # 餌シグナルを全体に伝える # 拡散の重みとして粘菌密度比が掛けられる def trans_food_signal for y in 1..@density.size-2 for x in 1..@density[0].size-2 diffusion = 0.0 diffusion += (@food[y][x-1]*@density[y][x]/(@density[y][x]+@density[y][x-1]+@@eps)-@food[y][x]*@density[y][x-1]/(@density[y][x]+@density[y][x-1]+@@eps)) *@d[y][x-1] *@d[y][x] diffusion += (@food[y][x+1]*@density[y][x]/(@density[y][x]+@density[y][x+1]+@@eps)-@food[y][x]*@density[y][x+1]/(@density[y][x]+@density[y][x+1]+@@eps)) *@d[y][x+1] *@d[y][x] diffusion += (@food[y-1][x]*@density[y][x]/(@density[y][x]+@density[y-1][x]+@@eps)-@food[y][x]*@density[y-1][x]/(@density[y][x]+@density[y-1][x]+@@eps)) *@d[y-1][x] *@d[y][x] diffusion += (@food[y+1][x]*@density[y][x]/(@density[y][x]+@density[y+1][x]+@@eps)-@food[y][x]*@density[y+1][x]/(@density[y][x]+@density[y+1][x]+@@eps)) *@d[y+1][x] *@d[y][x] @food_delta[y][x] = @@dt * diffusion * @@velocity end end for y in 1..@density.size-2 for x in 1..@density[0].size-2 @food[y][x] += @food_delta[y][x] end end end # 一定確率で寿命となりスタート地点に再生成される def decay_and_reborn for y in 0..@food.size-1 for x in 0..@food[0].size-1 @density[y][x] *= @@decay_density end end @density[@start_point.y][@start_point.x] += (1.0-@@decay_density) * 1.0 end def decay_and_rethrow_food_signal for y in 0..@food.size-1 for x in 0..@food[0].size-1 @food[y][x] *= @@decay_food end end @food[@start_point.y][@start_point.x] += (1.0-@@decay_food) * 1.0 @food[@goal_point.y][@goal_point.x] += (1.0-@@decay_food) * 1.0 end def normalize_density s = 0.0 for y in 0..@density.size-1 for x in 0..@density[0].size-1 @density[y][x] *= 0.0 if @density[y][x] < 0.0 s += @density[y][x] end end for y in 0..@density.size-1 for x in 0..@density[0].size-1 @density[y][x] /= s end end end # 詳細釣り合い条件を満たす拡散方程式に従い粘菌密度が動く # 拡散の重みとして餌シグナル強度比が掛けられる def move_density r_walk = rand(10000)/100000.0 for y in 1..@density.size-2 for x in 1..@density[0].size-2 # 単純拡散 diffusion = 0.0 diffusion += (@density[y][x-1]-@density[y][x]) *@d[y][x-1] *@d[y][x] diffusion += (@density[y][x+1]-@density[y][x]) *@d[y][x+1] *@d[y][x] diffusion += (@density[y-1][x]-@density[y][x]) *@d[y-1][x] *@d[y][x] diffusion += (@density[y+1][x]-@density[y][x]) *@d[y+1][x] *@d[y][x] # 餌シグナルによる収縮(重み付き拡散方程式) food_shrinkage = 0.0 food_shrinkage += (@density[y][x-1]*@food[y][x]/(@food[y][x]+@food[y][x-1]+@@eps)-@density[y][x]*@food[y][x-1]/(@food[y][x]+@food[y][x-1]+@@eps)) *@d[y][x-1] *@d[y][x] food_shrinkage += (@density[y][x+1]*@food[y][x]/(@food[y][x]+@food[y][x+1]+@@eps)-@density[y][x]*@food[y][x+1]/(@food[y][x]+@food[y][x+1]+@@eps)) *@d[y][x+1] *@d[y][x] food_shrinkage += (@density[y-1][x]*@food[y][x]/(@food[y][x]+@food[y-1][x]+@@eps)-@density[y][x]*@food[y-1][x]/(@food[y][x]+@food[y-1][x]+@@eps)) *@d[y-1][x] *@d[y][x] food_shrinkage += (@density[y+1][x]*@food[y][x]/(@food[y][x]+@food[y+1][x]+@@eps)-@density[y][x]*@food[y+1][x]/(@food[y][x]+@food[y+1][x]+@@eps)) *@d[y+1][x] *@d[y][x] # 自己組織化による収縮(物理的根拠無しな適当方程式) self_shrinkage = 0.0 self_shrinkage -= (@density[y][x-1]*@density[y][x-1]/(@density[y][x]+@density[y][x-1]+@@eps)-@density[y][x]*@density[y][x]/(@density[y][x]+@density[y][x-1]+@@eps)) *@d[y][x-1] *@d[y][x] self_shrinkage -= (@density[y][x+1]*@density[y][x+1]/(@density[y][x]+@density[y][x+1]+@@eps)-@density[y][x]*@density[y][x]/(@density[y][x]+@density[y][x+1]+@@eps)) *@d[y][x+1] *@d[y][x] self_shrinkage -= (@density[y-1][x]*@density[y-1][x]/(@density[y][x]+@density[y-1][x]+@@eps)-@density[y][x]*@density[y][x]/(@density[y][x]+@density[y-1][x]+@@eps)) *@d[y-1][x] *@d[y][x] self_shrinkage -= (@density[y+1][x]*@density[y+1][x]/(@density[y][x]+@density[y+1][x]+@@eps)-@density[y][x]*@density[y][x]/(@density[y][x]+@density[y+1][x]+@@eps)) *@d[y+1][x] *@d[y][x] @density_delta[y][x] = @@dt * (diffusion + food_shrinkage *2.73 + self_shrinkage/2.73) * @@velocity end end for y in 1..@density.size-2 for x in 1..@density[0].size-2 @density[y][x] += @density_delta[y][x] end end normalize_density end def print_map total_density = 0.0 @map.each_with_index{|line,y| line.each_with_index{|c,x| if @start_point.x == x && @start_point.y == y print 'S' elsif @goal_point.x == x && @goal_point.y == y print 'G' elsif c == ' ' if @density[y][x] > 1.0e-1 print '1' elsif @density[y][x] > 1.0e-2 print '2' elsif @density[y][x] > 1.0e-3 print '3' elsif @density[y][x] > 1.0e-4 print '4' elsif @density[y][x] > 1.0e-5 print '5' elsif @density[y][x] > 1.0e-6 print '6' elsif @density[y][x] > 1.0e-7 print '7' elsif @density[y][x] > 1.0e-8 print '8' elsif @density[y][x] > 1.0e-9 print '9' else print ' ' end else print c end total_density += @density[y][x] } print "\n" } printf "-- total density = %5.5f \n", total_density print "==density==\n" @density.each{|line| line.each{|c| printf "%1.5f\t", c } print "\n" } print "==food==\n" @food.each{|line| line.each{|c| printf "%1.5f\t", c } print "\n" } end def is_passage?(point) @map[point.y][point.x] == ' ' end end Nenkin.new.run __END__ ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * **************************
実行するとこんな感じの出力が続きます。
[Time=2200.00000] ************************** *S*3*33344444455555566666* *2*3*33*44*************66* *2*233*4444************66* *2222*4444445555566666666* **************5*********** *777777666666666666667777* **7*********************** *776666*65555554444444G44* *77*666666***********4*44* *7766*66666655*******4*44* *7766666*6665555554444444* ************************** -- total density = 1.00000 ==density== 0.00000 0.00000 0.00000 ... 0.00000 0.10715 0.00000 ... ... ==food== 0.00000 0.00000 0.00000 ... ...
迷路の数字は粘菌の密度1(濃い)〜9(薄い)を表わしています。
densityは各点における粘菌密度の実データ(全点足すと1)
foodは各点における餌シグナル強度(全点足すと2のはず)
これが必要なところだけに収縮してくれれば良いのだが。
いろいろいじってみたがちゃんと勉強してから書き直した方がいいみたいだ。
現状は迷路いっぱいに広がるか、スタートゴールの2点に分裂するかになってしまうので、
ループ解消の何らかの機構が必要かも。