I''m making a game where you bury people under piles of sand. It is a 2D side-view game, so sand will pile up into what looks like upside-down V''s on the screen. I need an efficient algorithm to make the sand fall into piles. I''ve tried many different things, but each of them is too slow for a screen full of sand. Any ideas? And, would a vector of existing sand or a matrix of both sand and air be more efficient? Thanks! The sand falls from above, kinda like this: . . . .. .... ...... ........ ..........

I also just realized that it is mostly the DirectX writing that is slow. I''m looping through my matrix of sand, and each grain is a structure that holds a color. I am then copying this color to the active surface. I''m going to put in some double buffering eventually, but I believe it will still be too slow then. I''ll search and post on the DirectX forum, but any help would still be appreciated.

Thanks!

very simple, I should think

bool UpdateParticle(float &x, float &y){    // nothing under the particle, keep falling     int under = pixel[y-1][x];    if (!under)    {         y--;         return true;    }    // test left and right supports under the particle     int left  = (int) (pixel[y-1][x-1] != 0);    int right = (int) (pixel[y-1][x+1] != 0);      // Hit a stable ground (left/right/underneath supports), return that the particle is finished    if (left & right)        return false;   // one of the support is missing, tumble the particle towards it     if (left ^ right)        x += right - left;    y--;    // particle still active    return true;}

by never killing the particles when they are finished, you can dig sand and the particles will try to fill the gaps. could be fun.

a more optimised algo for that case, but a bit more cryptic

   inline bool UpdateParticle(float &x, float &y){    int* pixel = &(pixel[y-1][x-1]);     // test left and right supports under the particle     int left  = (int) (*(pixel++) != 0);    int under = (int) (*(pixel++) != 0);    int right = (int) (*(pixel  ) != 0);    int bitfield = (left | (under << 1) | (right << 2);    switch(bitfield)    {    case 0: // ___    case 1: // x__    case 4: // __x    case 5: // x_x       y--;        return true;    case 3: // xx_       y--;       x++;        return true;    case 6: // _xx       y--;       x--;        return true;    case 2: // _x_       y--;       x+= ((rand() & 1) << 1) - 1; // 'randomly' go right or left        return true;    case 7: // xxx        return false;    }    return false;}

note that, to avoid unpleasant crashes, your screen should be surrounded by a (possibly invisible) rectangle of sand (due to the (x-1), (y-1) indices.


[edited by - oliii on June 28, 2003 9:40:13 PM]

There''s some clever stuff going on in the optimized algorithm. The one thing I don''t get about it is the first line. What does that do? How are you storing your particles?

Do you want to sand to fall in real-time? If you don''t you could instead have an array only of the width of the screen, each value holds the height of the sand underneath it. Now it''s just a case of dropping the sand down instantly, which should be quicker than all those separate iterations.

Of course this approach is easily adapted to real-time and should have a lot of performance savings. Having to test the area under the particle once, instead of as many times as the number of iterations has obvious benefits. In fact the performance gains are even greater than that because you only have to create the array once, then modify it after each particle is done.

The only problem with this is for when you ''dig'' out a bit, then you would be better reverting to a more brute force algorithm.


Finally, I don''t know much about how you''re plotting your points on the surface, but if you''re doing it per-pixel, I''m sure you could speed that up by drawing rectangles instead. A quadtree would be the most simple way, maybe even an irregular quadtree. I''d assume there''s a function for drawing rectangles that''s faster than doing it per-pixel, but as I said I have zero experience.

That''s an interesting idea, but I don''t think it will work for what I have in mind. I do want it in real-time, and also wanted to add some other particle types, such as water (which would fall into a flat "pile"). But first, I wanted to get the sand working right.

I looked up what a quadtree is, and that looks like it would be faster. Let me make sure I understand: I would recursively cut the screen into quarters until I found enough rectangle entirely full of sand, then draw those rectangles and fill in the few remaining points individually. Right?

How do I post a screenshot? I made several console sand simulations to test different algorithms. They all work just the way I want, even at about the right speed, but the resolution is much lower then I want (because it''s in the console). Anyway, I could post a few screenshots to show exactly what I''m aiming for in the DirectX version.

that column array algo is fine, but if you have blocks or ledges, it would not work. And digging of course. However, if you have 1000s of particles, you''ll need to do some more clever stuff. I''d say, once a particle is stable, destroy it and leave a ''pixel'' in its place in the collision array.

When digging, you take out a chunk of sand (pixels in the collision array), and on the edges of the chunk you just took out, clear the pixels and create particles in their place. When those particles fall, and if there are grains of sands above (above left, above right and straight above) in the sand pile, clear the pixels and create new particles in place of the pixels, ect... That would create a chain reaction, and make a portion of the sand pile fall. However, the bigger the chunk, the more processing required.

back to your question, I assumed you stored the world into a 2D kind of bitmap, as a list of rows of pixels. The first line of code points to the bottom-left pixel under the particle, and give a more direct access (faster). Indexing into arrays is expensive, and should be the first thing to optimise, really.

That suggestion sounds good, oliii. I''m guessing you meant the "collision array" to a single-dimensional array of moving particles, and the pixels to be stored in a bitmap that is blitted to the screen each frame? That sounds like it''ll work, so I''ll go code it.

I''ll tell you how it turns out.

Thanks again!

2d array (a bitmap of pixels), and the sand particles, added to the bitmap only when they are stablised, when update() returns false. The bitmap only needs on/off pixels, so a single byte per pixel would do.

you can use that bitmap to create a texture and upload it to the video card every time a pixel gets added to the bitmap. quite costly.

or the dynamic quadtree approach. like a warnock 2D algorithm. It would split the 2D array into filled-unfilled rectangular areas, and you render those areas as sprites or colored rectangles. Could be costly too.

if you can scanline the 2D array, render rows of contiguous grains as a line or a thin quad with slanted edges, and add a simple texture to it, you can do a fake lighting effect that way (darker at the edges, and getting brighter in the middle of the texture, and a ''grainy'' texture to improve the looks). The quad approach is good if your sand particles are several pixels in size. Boulders more like

Scanlines would be my choice, they are quite elegant. You can easily add/remove pixels from a scanline, by using boolean operators and inserting a row of deleted/created pixels, merging scans, ect...

just a few thoughts.