個別の細胞経路を通過する時間を計算するにはどうすればよいですか？

Question

ここでは、ディクリートセルのフィールド（2次元配列またはテーブル）があるとします。私たちは自己交差がなく、斜めに接続されていない有限のパスを内部に持っています。パーティクルはA点で始まり、B点までパターンをたどります。1つのステップは、有限時間= tで実行できます。したがって、パス全体の時間はT = t * lとなります。ここでl =パス内のセルの数です。しかし！フィールドには、「h」と「v」とマークされたセルがいくつかあります。パーティクルが 'h'セルに当たった場合、パーティクルは3つのパーティクルに分割されます。 1つはパスで移動し続けます。 2番目のフィールドは、「h」セルからフィールドの左端に向かって左に移動し始めます。 3番目のフィールドは、 'h'セルからフィールドの右端に移動します。同様に 'v'セルと同様に、左/右の代わりに、別の2つのパーティクルが上下に動き始めます。すべてのパーティクルが同じ速度で同時に移動しています。追加のパーティクルも 'h'と 'v'を集めることができ、分割してより多くのパーティクルを生成することもできます。最初のパーティクルが始まる瞬間からすべてのパーティクルが完了した瞬間までの時間を計算する関数をLuaに書く必要があります。関連するイラストを参照してください。 「h」または「v」セルが収集されると、それは単純なセルになり、他のパーティクルはそれを打つと分裂しないことに注意してください。

Answer 1

シミュレーションの直接実行とは別にここで実行できるアルゴリズムはあまりありません。 異なる粒子の動きが他の粒子移動の条件を変えるので（収穫時のように）、シミュレーション時間の前知識はありません。 vとhタイルが対話プロセスの後に残っ

なら、あなたはただつまり、単純なレイトレーシングを行うルートをスキャンし、vとhタイルがvとhタイルから引き出された走査線を見つけ、v、hやボーダータイルを見つけることができます最長のパスを計算し、newfoundから線を引くv、hそしてそれらをスキャンし、すべての線が境界線に当たったり、ループにロックされるまで続きます。ループされた結果を無視するために、現在検査されているレイとその先行オブジェクトによって既にどのタイルが訪問されたかを記憶することができます。明らかに、特別なタイル（v,h）は、シミュレーション時間を延ばすことができるだけであり、上記の結果は、消える特別なタイルを有するシミュレーションの時間の上限を与えることは明らかである。正確なランタイムを計算するには、特定のタイルがトリガーされる瞬間を考慮する必要があります。確かに、それを光線で行うことは可能ですが、粒子の直接シミュレーションと同等であるという考えが少し必要です。

はそのためのコードは非常に簡単ですし、私は簡単にアルゴリズムを概説します：

%make array for particlesenter code here 
particles={} 

%define initial particle route 
route={{x1,y1},{x2,y2},...} 

%probably you should have your field defined somewhere here too 
v_tiles={{x1,y1},{x2,y2}...} 
h_tiles=... 

%make particle, possible implementations are numerous really 
%for example it could be represented by its position 
%and a function which gives next position, based on current one 
%for main particle it could search the route table for a current position and return next element, 
%or just use external counter variable to keep track of propagation 
particle={position={x,y}, propagator=function({x,y}) ....} 

%put that into particles array obviously 

%initialize counter 
T=0 
%run a cycle until there are particles 
while #particles>0 do 

    %perform a single step for all the particles 
    for _,p in pairs(particles) do 
     %move them all 
     p.position=p.propagator(p.position) 
    endfor 
    %then check them all 
    for i,p in pairs(particles) do 
     %check for special tiles 
     if is_v(p.position) then 
      %make new particle 
      table.insert(particles,{ 
       position={p.position.x, p.position.y+1}, 
       %for secondary particles propagator would be just a constant addition to a single coordinate 
       propagator=function(pos) return {pos.x,pos.y+1} end 
       }) 
      %make second new particle 

     %same for h tiles 
     if is_h(p.position) then ... 

     %check for border tile 
     if is_border(p.position) then 
      %remove those that are at the border 
      table.remove... 
      %for the original particle you'd have to check 
      %whether it has reached destination 
      %probably you should check that somewhere around here too 
    endfo 
    %do what we're here for: increase counter 
    T=T+1 
endwhile 
%when this reaches the end T will be the answer 

あなたがLUAで問題を解決しているとき、あなたはメモリを心配しないように十分に強力なマシンを持っていることは良いですそして可変サイズの配列でただ消してください。しかし、現行のタスクでは、メモリの上限を1 + 2 *（num_v + num_h）とすることは可能です。 直接シミュレーションではパーティクルは少なくなるかもしれませんが、特殊なタイルとのやりとりごとに特殊なタイルが削除され、1つのパーティクルが追加されるため、それ以上はありません。