I think I've had something of a breakthrough on this project. Think about this for a bit:
Ultimately, the simulation is just a kind of inefficient sorting operation. Fluids travel from higher places to lower places. Other things get in the way. If things aren't falling, then they might migrate side to side.
Sorting is a hard problem, but it's one that a lot of effort has been poured into. Python particularly has some good sorts written in optimized C.
We already use Python's sort functions in the code, to arrange the positions of different slices of liquid in a single cell. My idea is to extend it beyond that cell -- to sort whole columns of fluid at once.
The biggest problem with this is that sorting works too well -- heavy fluid will transmigrate from the top of a column to the bottom instantly, with no possibility of affecting anything along the way. There needs to be some way to limit how far an individual slice of fluid can travel in its passage. There are no sorts that I'm aware of that support this kind of travel limiting, but it might be doable using a Python trick more frequently used back in older versions, called Decorate-Sort-Undecorate. That is, you first modify the contents to encode additional information into it that weights each item in the sort by some variable, in this case that would be initial position in the column. The weights would have to be chosen in such a way that the fluid weights would overpower the positional weights over short distances but not long ones. Then we sort the column, then remove the extra information (or in our case, overwrite it with new positional information the next time we do a sort).
Another problem is that we would still need to make another pass through each column to handle sideways motion.
How does that sound to you folk?
You can try using only a few passes of Bubble Sorting each cycle.
ReplyDeleteSince Bubble sort does move each element up or down at most one cell per cycle you can easily control how far and how fast fluids can move.
I considered that, but the problem is that bubble sort is like the *least* optimized kind of sort possible.
DeleteThis comment has been removed by the author.
DeleteThat sounds really intriguing, actually!
ReplyDeleteI think you're all on crack, but this line of discussion could still lead to something useful.
ReplyDeleteThe trouble with Bubble Sort is that, depending on the direction you take it, it always moves the least or greatest unsorted element in the list to its correct position. You could fix that by e.g. checking the pairs starting at an even element first, then checking the pairs that start at an odd element. But then maybe you have something conceptually not very different from the way it works currently. Also, elements will move by either one or two spaces depending on which direction and whether they're at an odd or even index.
What you do within a cell sounds kinda like https://secure.wikimedia.org/wikipedia/en/wiki/Counting_sort, which is actually O(n) (only sorting algorithm I know that's better than O(n log n)). This suggests that maybe you should be storing counts in your cells instead of individual droplets. I don't know how that affects the inter-cell math, but maybe it's simpler?
Random thought: Do a sort (perhaps of the counting variety) in all the cells that contain fluid, THEN do a sort in those same cells but offset it by half a cell. That gives you something resembling a bubble sort and with all the same limitations but maybe with fewer passes for the liquid to cover the same distance?
ReplyDelete