Skip to main content
gamedev.net
🔒 Locked

mass spring grid problem...

Started by ehudros May 13, 2006 at 2:39 PM 18 replies 2.6k views
Original Post
ehudros
ehudros
Hi everyone... I'm writing a shoot em up based loosely on geometry wars. one of the coolest things about it is a grid that's actually a mass spring system that is repelled when the player's ship moves (nodes are pushed away from the ship) and than get back to their original position when the ship is no longer there. I have implemented a mass spring system (a 2D one), and I'm using euler integration (it seems alright for this type of game, grid stays stable). Now the problem is that sometimes after nodes are pushed away by the ship (the ship applies a force away from it on all nodes in a certain distance), they stay stuck in place and don't get back to their original position. In debug mode i was able to see that the sum of forces on those nodes is almost zero, which means the forces applied on it are canceling each other out. The thing is, I cant for the life of me understand why... :) I'm not that great at physics, and i was wondering if someone here could take a look? I read somewhere that cloth simulation can "fold on itself" - maybe that's the case here? Oh, an important piece of info - each node in connected to the 8 nodes surrounding it (4 horizontal+vertical, 4 diagonal). I've read somewhere that it's better to also connect each node the the second level of neghibours (2 nodes away from the current node) to allow better simulation. k is set to 0.005. Any help/suggestions would be appreciated. I've attached a screenshot of the problem. notice the strange grid state on the top left (kind of hard to see)- it simply stays in this position Image Hosted by ImageShack.us
Zakwayda
Zakwayda
I don't know the answer to your question, but that looks cool - let us know when there's a version we can download :-)
Bob Janova
Bob Janova
Are your 'edge' nodes tied to a fixed frame by springs too? If you don't tie the grid down to something then the edges will become distorted over time.
Eelco
Eelco
this problem is more generally known as 'inverting' of a computational mesh. if a node that is 'supposed' to be on the right of another suddenly is pushed to the left of it, it might stay there because the spring also changes direction, pushes to keep it there, ie it is inverted.

i think the best solution here would be to modify the springs, so that they simpy cannot change direction: dont base their force on where the nodes are, but on where the nodes are supposed to be.

say you have a node in position x1 and x2. you want a force function that is zero in rest and otherwise monotomically increasing. simple: force = constant * ((x2-x1)-restlength).

this might seem less accurate than a hookean spring, but it will hardly matter, and will solve the inverting problem.
Dmytry
Dmytry
I wouldn't use mass spring system for such special effect.

I'd just use simple wave-ish equation for horizontal and vertical deviation of vertex from center point.
like
vel.x=vel.x*(1.0-damping_value*dt)+k*dt*(average of neighbouring x positions - p.x);
vel.y=vel.y*(1.0-damping_value*dt)+k*dt*(average of neighbouring y positions - p.y);
and make border points be fixed.
It is also faster to simulate than mass-spring system.
Eelco
Eelco
Quote:
Original post by Dmytry
I wouldn't use mass spring system for such special effect.

I'd just use simple wave-ish equation for horizontal and vertical deviation of vertex from center point.
like
vel.x=vel.x*(1.0-damping_value*dt)+k*dt*(average of neighbouring x positions - p.x);
vel.y=vel.y*(1.0-damping_value*dt)+k*dt*(average of neighbouring y positions - p.y);
and make border points be fixed.
It is also faster to simulate than mass-spring system.


given that you can derive the wave equation from taking the limit of a linearized mass spring system, whats the difference between discretizing the wave equation or linearizing a mass-spring system?

although starting from the wave equation does seem to be conceptually simpler, it should reduce to the same computations if both are optimized.
Dmytry
Dmytry
Quote:
Original post by Eelco
Quote:
Original post by Dmytry
I wouldn't use mass spring system for such special effect.

I'd just use simple wave-ish equation for horizontal and vertical deviation of vertex from center point.
like
vel.x=vel.x*(1.0-damping_value*dt)+k*dt*(average of neighbouring x positions - p.x);
vel.y=vel.y*(1.0-damping_value*dt)+k*dt*(average of neighbouring y positions - p.y);
and make border points be fixed.
It is also faster to simulate than mass-spring system.


given that you can derive the wave equation from taking the limit of a linearized mass spring system, whats the difference between discretizing the wave equation or linearizing a mass-spring system?

although starting from the wave equation does seem to be conceptually simpler, it should reduce to the same computations if both are optimized.

Indeed, the wave equation itself is same as limit of linearized mass spring system. (and indeed in real world there's no wave equation in mechanics but only mass spring systems).
The point is that it will not have problems like what OP is getting. I.e. for the task(waves ala game grid wars) it is better than the system of point masses connected by springs, and better than system of point masses connected by springs with additional springs attached to places where points must be.
Eelco
Eelco
Quote:
Original post by Dmytry
Quote:
Original post by Eelco
Quote:
Original post by Dmytry
I wouldn't use mass spring system for such special effect.

I'd just use simple wave-ish equation for horizontal and vertical deviation of vertex from center point.
like
vel.x=vel.x*(1.0-damping_value*dt)+k*dt*(average of neighbouring x positions - p.x);
vel.y=vel.y*(1.0-damping_value*dt)+k*dt*(average of neighbouring y positions - p.y);
and make border points be fixed.
It is also faster to simulate than mass-spring system.


given that you can derive the wave equation from taking the limit of a linearized mass spring system, whats the difference between discretizing the wave equation or linearizing a mass-spring system?

although starting from the wave equation does seem to be conceptually simpler, it should reduce to the same computations if both are optimized.

Indeed, the wave equation itself is same as limit of linearized mass spring system. (and indeed in real world there's no wave equation in mechanics but only mass spring systems).
The point is that it will not have problems like what OP is getting. I.e. for the task(waves ala game grid wars) it is better than the system of point masses connected by springs, and better than system of point masses connected by springs with additional springs attached to places where points must be.


i didnt actually want to suggest that, although i see how one might think so: my description wasnt exactly good. when i said: "dont base their force on where the nodes are, but on where the nodes are supposed to be.", i was thinking discarding 'where the nodes are' in terms of left/right of eachother relative to starting position, but instead take a linearized model, where the nodes stay in their 'supposed' ordering no matter what. but i see it is indeed highly ambigious, i should be more carefull what i write. :)

in retrospect, all i should have said is: linearize around the equillibrum position, which boils down to the same thing you are suggesting.
ehudros
ehudros
Ummm, thanks everyone for taking the time to answer...
I must say I'm a bit confused by your answers though :)
Do you all agree that switching to a different method than my current spring based one is a good idea?
If so, can you please elaborate a bit on the mechanism or point me to a search word i can look for more info?

I'm not that big an expert on physics as you see, so I'm learning as I progress...

Again, thanks very much for your time!
Dmytry
Dmytry
Basically, you can compute average position of four neighbouring points and use spring (with rest length =0) to attract each point there (don't worry, it is not a hack and waves will spread around). It will be essentially same math as what i and Eelco suggest.
As for search, try looking for wave equation; essentially it is wave equations for x and y.
Eelco
Eelco
Quote:
Original post by ehudros
Do you all agree that switching to a different method than my current spring based one is a good idea?

no, not really switching to a different method. its only a slight change you have to make really.

Quote:

If so, can you please elaborate a bit on the mechanism or point me to a search word i can look for more info?

instead of calculating springforces like you do right now, you should do something like this:

for horizontal springs:

force = (spring.rightnode.position.x - spring.leftnode.position.x - gridspacing) * someconstant

leftnode.force.x += force
rightnode.force.x -= force

and vice versa for vertical springs.

all thats changed compared to what you are (i assume) doing now, is that the springs are linearized around their rest position.

i might have mixed up a few +- there, but thats the general idea. what dmytry is suggesting is basically the same, only more optimized, but implementing it that way probably requires changing more code, so it might be a good idea getting it to work like this first.
ehudros
ehudros
thanks guys, this really helped get things cleared up a bit.
I'll get to work and let you know how it's going...
ehudros
ehudros
Uhhh...
I'm going crazy over here...
I've been trying to implement your suggestions for almost a day now and nothing seems to be working.
I'm using Eelco's equation, and strange things are happening.
Mainly, when i try to "explode" the grid things are not working properly (explode meaning I iterate through all nodes and mvoe their position to create an explosion/vibration like effect). nodes take ages to get back to their original position, and i can't seem to make them go faster. I'm already using a 1.0 constant and it's still going mighty slow. using a constant larger than 1 makes the grid unstable and it actually gains energy, destroying it's structure.

any ideas? I know it's almost impossible to try and help without actualyl looking at the code, but let's atl east make sure i understand the process correctly...

1. I create a grid of nodes and connect each node to it's four neighbours
2. i than iterate every game loop through all nodes and compute their force using eelco's equation, add/detracting the resultant force from the neighbours.

am i missing something here?
As always, any help would be greatly appreciated...

Ehud.
Eelco
Eelco
hmm.. nothing ive ever encountered before, so i cannot tell from your description what might be wrong.

mind posting the relevant code here? that would probably help.
ehudros
ehudros
thanks Eelco for takign the time to answer...
first, take a look at the attached image:
Image Hosted by ImageShack.us

This is what's currently bugging me. I was able to get over the problem of nodes getting back to slowly to their position by twiking the way i calculated velocity (in other words, there was a bug :) )

but strange things continue to appeart, like the image above. I'll describe what's happening here:
The ship radiates a repeling force on all nodes within a certain radius and pushes them away (this should form a nice looking circle around the ship).
Instead what's happening is that all nodes on the diagonal and vetical planes of the ship are affected someway, and are also pushed away. I assume this has something to do with the way i now compute forces (using a wave equation), but i can't understand why the grid is behaving like this.

posting the code here is not practical as it is pretty big.
here's the code i use to calulcate the force for each node:
Resultant.x = ((node_curr->Neighbours[RIGHT_NEIGHBOUR]->pos.x - node_curr->Neighbours[LEFT_NEIGHBOUR]->pos.x)/2 - 15) * 0.5;Resultant.y = ((node_curr->Neighbours[BOTTOM_NEIGHBOUR]->pos.y - node_curr->Neighbours[TOP_NEIGHBOUR]->pos.y)/2 - 15) * 0.5;		node_curr->Neighbours[LEFT_NEIGHBOUR]->force.x+=Resultant.x;node_curr->Neighbours[RIGHT_NEIGHBOUR]->force.x-=Resultant.x;// vertical forcesnode_curr->Neighbours[TOP_NEIGHBOUR]->force.y+=Resultant.y;node_curr->Neighbours[BOTTOM_NEIGHBOUR]->force.y-=Resultant.y;


I sent you the complete code to your hotmail account, although it really is quite big so I really doubt you can found the time to look through it.
Anyway, any guess or insight would help at this point :)

Thanks!
Ehud.
Eelco
Eelco
i see one problem there: you shouldnt take the average of neighbors to get the force, but the distance of a node to the average of its neighbors.

on top of that, i do now realize you should also take shear forces into account.

Vector average = (node_curr->Neighbours[RIGHT_NEIGHBOUR]->pos + node_curr->Neighbours[LEFT_NEIGHBOUR]->pos + node_curr->Neighbours[TOP_NEIGHBOUR]->pos + node_curr->Neighbours[BOTTOM_NEIGHBOUR]->pos) * 0.25f;

Vector force = (node_curr->pos - average) * something;

node_curr->force += force;

something like that should work better but im in a bit of a hurry so dont count on it. if this doesnt work, id advice going back to a mass spring model, where two neighboring nodes are connected by a linear spring and a linear shear spring, because its not trivial to see if action = - reaction is adhered to in my above suggestion, although i believe that it is.

[Edited by - Eelco on May 21, 2006 3:07:23 PM]
Dmytry
Dmytry
I wrote quick test, and it does work quite well:

class WavesTest{  public:  enum{    grid_res=64  };  double q,damping;  struct GridPoint{     Vec3d pos,vel;  };  GridPoint grid[grid_res*grid_res];  WavesTest(){    q=12.0;    damping=0.2;    int x,y;    for(y=0;y<grid_res;++y){      for(x=0;x<grid_res;++x){        grid[x+y*grid_res].pos=Vec3d(x,y,0);        grid[x+y*grid_res].vel=Vec3d(0,0,0);      }    }// start wave at center.    grid[(grid_res+1)*(grid_res>>1)].vel=Vec3d(40,20,10);  }  void DoStep(double dt){    double accel_c=-q*dt;    double damping_multiplier=exp(-dt*damping);    int x,y;    for(y=1;y<grid_res-1;++y){      for(x=1;x<grid_res-1;++x){        Vec3d avg_pos=0.25*(        grid[x+y*grid_res -1].pos+        grid[x+y*grid_res +1].pos+        grid[x+y*grid_res -grid_res].pos+        grid[x+y*grid_res +grid_res].pos);        grid[x+y*grid_res].vel+=accel_c*(grid[x+y*grid_res].pos-avg_pos);        grid[x+y*grid_res].vel*=damping_multiplier;        grid[x+y*grid_res].pos+=grid[x+y*grid_res].vel*dt;      }    }  }  void Draw(){    for(int j=0;j<grid_res-1;++j)    {      glBegin(GL_LINES);      for(int i=0;i<grid_res-1;++i){        int n=i+j*grid_res;        glVertex3d(grid[n].pos.x,grid[n].pos.y,grid[n].pos.z);        glVertex3d(grid[n+1].pos.x,grid[n+1].pos.y,grid[n+1].pos.z);        glVertex3d(grid[n+1].pos.x,grid[n+1].pos.y,grid[n+1].pos.z);        glVertex3d(grid[n+1+grid_res].pos.x,grid[n+1+grid_res].pos.y,grid[n+1+grid_res].pos.z);      }      glEnd();    }  }};WavesTest waves_test;

(it worked in first run without any debugging whatsoever)

See the DoStep function, that's where it updates grid.

I did it with 3D vectors just because this way it looks more interesting in my test app.(Maybe I'll write 3D game like this.)
You can use 2D vectors, it'll work the same. If you don't have vector class with vector operations, it is time to make one. :) Shortens the equations quite a lot.
ehudros
ehudros
Thanks Dymtry and Eelco!
You've been of great help to me...
I still have issues to resolve in my implementation, but your advice was truely invaluable....

I'll let you know how the game progresses :)
ehudros
ehudros
thank you very much, I'll take alook at it :)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.