simulating motion; varying speed vs a single time step

[daggaz]

So. I work in a nanotech lab and am currently investigating protein-membrane interactions. As such, I am deeply interested in the random lateral displacements of phospholipid molecules within phospholipid bilayers, e.g. the plasma- and other cellular membranes.

I am currently putting together a very course simulation in order to investigate some rate-dependent properties. The problem I am running into is that I need to have different rates of motion for particles (larger clusters move slower and single molecules have the fastest allowable speed), but position and time are distinctly quantized: there is a spatial grid and a time step.

Wow, I thought. This is exactly like Crawl.

One way to approach the situation is to set the fastest particles to one time step, and then require multiple steps for slower particles to move (I think this is the way you guys do it?). Another way is to set the slowest motion equal to one time step, and have the fast particles move farther. I am leaning towards the second one, as the actual animation of the paths is not as important, it is the interactions that occur on average and I can just math that out at the end. Cutting the animation would be much, much faster as well, computationally.

Anyhow, I was just curious if anybody had any comments or expertise in this kind of thing, seemed like a good place to ask. For the record, I am currently looking at a square grid (hexagonal I think would be preferable but I dont think it is easy to graph/animate in IGOR, the program I am using) and movement rates of 8, 4, 3, 2, 1, and 0 total pixels per step.

[galehar]

crawl's time model isn't great so I wouldn't directly draw from it. We have an asymetric system, the player acts first, this takes a number of Absolute Unit of Time (aut), usually 10. This is time_taken. Then, all the monsters gain some energy: time_taken * monster_speed. After that, one after the other, they act until they have no more energy. Each action takes a certain amount of energy, so we can have fast monsters that attack slowly or the opposite.
Anyway, this system has some drawbacks. When the player acts very slowly (example: Chei), each monster acts several time before the next, which might create some bizarre things. A monster with a low ID will act first and maybe it will attack another monster several times killing it before it can act. It would be better if they could act alternately. It can also creates strange things with damage over time (clouds, tornado, poison,...).
This is sufficiently rare as to not get in the way of gameplay, but still. It would be better to have a queue of events and treat all actors (player and monster) the same way. Whenever someone acts, depending on the duration of the action, it is placed in the queue so we know when its next action takes place.

[daggaz]

I run into similar problems with particle interactions. in real life everything occurs simultaneously, but in the simulation each particle needs to be treated individually, which necessitates an order of actions at some level. For example, what happens if two particles both randomly try to occupy the same space at the end of their movement? You can make some determination regarding which one wins, but this might set off a chain reaction regarding the losing particle and everything that interacts with it. It gets messy.

The que idea is something I was toying with as well.. for example having all the 8 step particles act one step at a time (in order, but the changes go into effect simultaneously), resolve any conflicts, take the next step, etc.. then when you hit the 4th step, the next speed particles join into the list. No matter what you end up with resolution difficulties, but I think you can minimize them at least, so you dont get really hurky jerky movement and the accompanying anomalies. This is computationally expensive, however.

EDIT: Oh god. Just realized if I allow particle groups to gain/lose edge molecules at any rate lower than their own action rate, then I have a brand new gigantic problem regarding how big is a group and just when does it get to move? My brain is so pissed at me right now.

[Galefury]

Re OP: if there is interaction between the particles you will probably get much larger numerical errors with the second method, and some interactions that would usually take place might be skipped. It is equivalent to greatly increasing the length of your time step (by a factor of 8 in your case), which means a much coarser simulation (which of course requires less time to compute, as you have mentioned). I don't know how much accuracy you need, but this is something to keep in mind.

[daggaz]

Hmm. Just had a brain fart/idea. Fastest particles have 100% chance of action. Slower particles have accompanying lower chance of action. Roll to see if you get to go. This does away entirely with fixed speeds and introduces randomization which is both natural and results in the correct average outcome. Also removes the entire issue of when does a turn start/end.

[Galefury]

Random numbers are somewhat expensive. Depending on how long each movement takes to compute, adding a random number generation to it (or several, for slower particles) might considerably increase your computation time. If you really want to add randomness, it may be better to randomly pick the next particle that moves, and the slow ones get picked less often. This means you only need exactly one random number for each particle movement. Only if the majority of your particles is of the fastest speed the way you suggested would probably be faster to compute because with 100% chance you can skip the randomness for those.

Edit: also depending on how you represent and organize your particles picking one of them X times might be much slower than going through a list sequentially and doing an operation on each. Probably this doesn't matter though.

Why not just ask your supervisor/professor/whatever you have where you work for advice? Or colleagues? Unless you're the first one in your group to work on something like this, someone who works with you has probably already thought about your problem a lot.

[daggaz]

Well, the vast majority of the particles will be single (fast), although there is a parameter i aim to incorporate which will modulate this. I also have to use random walking for all motion (it is brownian) so regardless I am going to be tossing a lot of dice in this simulation. I like your idea tho about randomly picking from a weighted list. That kind of 'solves' the whole simultaneous issue while at the same time handling the speed differences. I think I will go in that direction, thanks.

As for my group. Lol.. they are all biology majors, I am the only person with any kind of math/hard physics in the whole lab. My PhD supervisor asked me to prove some basic differential equations for her own paper on my first day here. MATH HARD! Computers for that matter, are indistinguishable from magic for this group.

EDIT: hmmm. randomly picking from the list introduces other problems as well now that I think of it. Hrmmmmmmdeedrrrrrmmmmhrmmmmm....

[Galefury]

This seems like a fairly common and old problem, so most plausible solutions will have been tried by someone. It should be possible to find some literature dealing with this, or at least to find someone who has worked on a similar problem and ask them for advice (or literature) by email. Unless you are in a very competitive field of research people also generally really like to collaborate, and your group can probably bring considerable biological expertise or data to the table.

[daggaz]

Yeah, that is what I thought as well but I have had a hard time finding descriptions of these simulation problems. Thought I would just bounce the idea off of some of you guys, maybe get a little bit of fresh insight or out of the box ideas and that has actually paid off.

[yogaFLAME]

In my academic experience, to not try to do optimize-first design when you don't know how big of a factor performance will be. Code it up in the simplest, brute-forciest way you can think of and get it working. Optimize later. Or never.