HiEv wrote:I'm also a bit confused, but might it make things a bit easier to turn your system inside out? Instead of taking each atom and figuring out where it can go, could you find all of the locations that could receive an atom initially, and then each time an atom moves you would only need to change the data in the area where the last atom moved from and moved to. That way you'd only need to rebuild the data for two areas instead of the whole system. This may require some complex indexing initially to prevent it from becoming equivalently difficult as your original problem though.
Of course, depending on how you need the locations stored this may not be possible. If you could give a tiny example of the data and a few of the potential movements for each it might be easier to understand. (If the atom positions are stored as integers instead of doubles/floats then it makes things easier.)
Also, if you could explain why you need to recompute the other atoms that don't move each time. Couldn't you keep the same lists for the other atoms that didn't move, and if they attempt to make an "illegal" move, simply try a different move? It should be faster to determine if a single move is "illegal" than recompute the list of all legal moves each time, right?
The best method probably also depends on whether the number of atoms is larger or smaller than the average number of possible moves for each atom. Is one of those usually larger than the other? Do all atoms technically have the same list of potential moves (ignoring "illegal" moves)? How big is the potential volume that needs to be dealt with? Is it possible for two atoms to "swap" positions?
Seems like a fun problem, but we need a bit more information.
bitwiseshiftleft wrote:I think I basically get it. Since moves depend only on local information, you basically need to have a way to find all atoms near one location. If they aren't already sorted by location, you can use an oct-tree or a hash table for this. I'm not sure which is the better solution, but I bet the hash table is easier to implement.
Users browsing this forum: thoughtfully, Yahoo [Bot] and 5 guests