2010-01-23
峠のTaisaiがナイズルを（ｒｙ
某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のはず)
これが必要なところだけに収縮してくれれば良いのだが。
いろいろいじってみたがちゃんと勉強してから書き直した方がいいみたいだ。
現状は迷路いっぱいに広がるか、スタートゴールの２点に分裂するかになってしまうので、
ループ解消の何らかの機構が必要かも。