algorithm - How to calculate time of passing the discrete path of cells? -

let's have field of descrete cells (2d array or table). have finite path inside of no self-crossings , no diagonal connections. particle starts way in point , follows pattern point b. 1 step can done in finite amount of time = t. time whole path t = t * l, l = number of cells in path. but! have cells in field marked 'h' , 'v'. if particle hit 'h' cell divides 3 particles. 1 continue moving path. second starts move left 'h' cell left border of field. third starts move right 'h' cell right border of field. analogically 'v' cell, instead of left/right, 2 particles start move up/down. particles moving simultaneously same speed. additional particles can collect 'h' , 'v' , can divided , spawn more particles. need write function in lua calculates time moment of first particle starts way moment of particles finished ways. see related illustation. note once 'h' or 'v' cell have been collected becomes simple cell , other particles doesn't divide if hitting it.

there's not of algorithm can done here apart direct running of simulations. there can no apriori knowledge of simulation time since movement of different particles alters conditions other particle movement (as in during harvest act).

if v , h tiles remained after interaction process perform simple raytracing i.e. scan route, find v , h tiles scan lines drawn v andh tiles, find v,h or border tiles, calculate longest path, draw lines newfound v,h , scan those, , on until lines hit border or lock loop. ignore looped results memorize tiles have been visited examined ray , predecessors.

obviously, special tiles (v,h) can prolong simulation time, result above give upper limit of time in simulation disappearing special tiles. calculate exact runtime, you'd need take account moment in time @ particular tile triggered. surely, possible rays, little of thought needed it'd equivalent direct simulation of particles.

the code pretty simple , briefly outline algorithm:

%make array particlesenter code here particles={}  %define initial particle route route={{x1,y1},{x2,y2},...}  %probably should have field defined somewhere here v_tiles={{x1,y1},{x2,y2}...} h_tiles=...  %make particle, possible implementations numerous %for example represented position  %and function gives next position, based on current 1 %for main particle search route table current position , return next element,  %or use external counter variable keep track of propagation particle={position={x,y}, propagator=function({x,y}) ....}  %put particles array  %initialize counter t=0 %run cycle until there particles while #particles>0      %perform single step particles     _,p in pairs(particles)         %move them         p.position=p.propagator(p.position)     endfor     %then check them     i,p in pairs(particles)         %check special tiles          if is_v(p.position)             %make new particle             table.insert(particles,{                 position={p.position.x, p.position.y+1},                 %for secondary particles propagator constant addition single coordinate                 propagator=function(pos) return {pos.x,pos.y+1} end                 })             %make second new particle          %same h tiles         if is_h(p.position) ...          %check border tile         if is_border(p.position)             %remove @ border             table.remove...             %for original particle you'd have check              %whether has reached destination             %probably should check somewhere around here     endfo     %do we're here for: increase counter     t=t+1 endwhile %when reaches end t answer 

it when you're solving problems in lua, have machine powerful enough not worry memory footprint , fire away variable size array. current task possible rough upper limit memory : 1+2*( num_v+num_h ). once again, in direct simulation might have less particles, since every interaction special tile removes special tile , adds pair of particles, never have more that.