 |
Author |
Topic: Spring-and-Mass Physics (Read 4831 times) |
|
mflux
|
Re: Spring-and-Mass Physics
« Reply #1 on: Apr 26th, 2004, 10:31pm » |
|
Hey Mike
I've been thinking/working/planning on doing an evolving system with soda-play-style physics before. I think I'm partly along the way, but you're much farther than me on the physics programming.
The structure of forms in my system is much like a skeletal structure heiarchy in 3d graphics. The "creature", or whatever form that's created, consists of nodes (masses) and springs. Every node is linked in a parent-child system. The network starts from a "root" node. The root node has several children, which in turn has other children. Each node records the "preferred" angle and distance away from its parent.
I programmed the system with a linked list.
Root has one child, but the child can have siblings like so:
Root ->child ->sibling ->sibling ->sibling
| | | |
child child child child->sibling
That's one example..
So the data structure for each child is only:
class segment
{
segment child;
segment sibling;
}
Taking a human being for example, the waist would be root, and its children the spine and two additional leg segments, the children of the leg segments would have an additional segment until the foot. The wrist would be the parent of five finger segments, etc etc.
So far this has worked. I'll post code and actual programs up when I get home. >_<
|
|
|
|
|
Mike Davis
|
Re: Spring-and-Mass Physics
« Reply #2 on: Apr 26th, 2004, 11:23pm » |
|
Thanks mflux, that's an interesting way to look at it. I was focusing on having a string of characters that get interpreted into a graph, and then mutating the string between generations. But I think your method would work better, as the structures would be copied to new generations and directly altered for mutation.
One thing is, though, that your method means that the overall structure is always a tree. I don't have anything in my system for handling springiness in the angle between springs (I'd love to put this in, though; do you have any sources about the physics involved with this?) so my structures have to be graphs and not trees or else they collapse, like in sodaplay.
For your work, you might want to look at L-Systems as a method for generating hierarchies; they mutate fairly well and your creatures can evolve with recursively-defined parts.
|
|
|
|
|
mflux
|
Re: Spring-and-Mass Physics
« Reply #3 on: Apr 27th, 2004, 6:15am » |
|
Heya Mike
Can you explain this "graph" system a bit more for me please? Also, I'm confused what this "adjacency matrix" is. I'm not classically trained in CS or physics, so forgive me. My knowledge of physics is actually quite limited and when I program it's usually based on intuition.
Here's an old program I wrote in C++ which used a similar method that I described. It worked fairly well, but had a really weak physics simulation.
The creatures' "genetic code" is a one dimensional array (like your string). Each creature, when dividing/giving children, produces two identical copies and one mutated copy. "Natural selection" picks the fittest designs.
This is an early attempt by me at programming something like this.
http://www.design.ucla.edu/~mflux/interactive/evolva/Evolva.zip
Here's my current version done in processing. Now I know a LOT more about programming, but my physics still sucks:
http://www.design.ucla.edu/~mflux/p5/evolva2/applet/
source:
http://www.design.ucla.edu/~mflux/p5/evolva2/applet/evolva2.pde
Sorry for the super verbose code. I write things that are reusable so that I can port them into new programs that I write.
In short, a simple test code generates the creature shown:
void constructSegments()
{
child=new segment(45,20,this);
child.child=new segment(15,20,this.child);
child.child.child=new segment(15,20,this.child.child);
child.child.next=new segment(-25,35,this.child.child);
child.next=new segment(-45,50,this);
child.next.child=new segment(15,50,this.child.next);
}
A function can be written to read a string and execute that arrangement of functions.
Yeah, this is basically an L-system. I've no clue how your system (connected nodes of solid mass) works. Time to read your souce 
Anyways, hopefully someone more profficient in physics can help you out.
|
|
|
|
|
narain
|
Re: Spring-and-Mass Physics
« Reply #6 on: Apr 27th, 2004, 4:36pm » |
|
on Apr 27th, 2004, 6:15am, mflux wrote:| Can you explain this "graph" system a bit more for me please Also, I'm confused what this "adjacency matrix" is. |
|
Well, in computer science, a graph is just a set of points - vertices - that are connected to each other by edges. If you've seen the first applet Mike posted to this thread, that's just a graph with all vertices connected all others.
An adjacency matrix is a way of representing a graph without having to draw a picture.  Imagine you've numbered all the vertices of the graph (say there are n of them). Then all you need to know to reconstruct a reasonable facsimile of the graph is which nodes are connected to which. So you make a n*n matrix, and if vertices i and j are connected, you set the location (i, j) in the matrix to 1, otherwise set it to 0. This contains all the information about the structure of the graph.
|
|
|
|
|
narain
|
Re: Spring-and-Mass Physics
« Reply #7 on: Apr 27th, 2004, 5:24pm » |
|
on Apr 26th, 2004, 11:23pm, Mike Davis wrote:| I don't have anything in my system for handling springiness in the angle between springs (I'd love to put this in, though; do you have any sources about the physics involved with this) |
|
Well, I have no sources, just my own ideas...
You could add a restoring force on each pair of edges on a vertex, that pushes the edges together or apart depending on the ange between them. (Actually, this isn't a force, it's a "torque". Forces move things without turning them. Torques turn things without moving them.)
Of course, you can't push on edges directly, so the torque would have to be transmitted to the vertices as a force perpendicular to the edge. This will have to be divided by the distance between them, because torque is supposed to be force times distance.
It all works out to this:
Consider two vertices v1 at (x1,y1) and v2 at (x2,y2) connected to a central vertex v0 at (x0,y0). Suppose the angle between the edges is t (in radians), and "wants to be" t0.
The restoring torque is (some factor) * (t - t0). This will apply equally on both edges (in opposite directions).
Take the edge between v0 and v1. The magnitude of force is torque / dist(v0,v1).
Equal and opposite forces of this magnitude have to apply on v0 and v1. The forces are perpendicular to the edge between them. You know the direction and magnitude; figure out the vector.
Now you have to do this for the edge between v0 and v1 too. So v0 will end up experiencing two forces.
|
|
|
|
|
Mike Davis
|
Re: Spring-and-Mass Physics
« Reply #8 on: Apr 27th, 2004, 8:28pm » |
|
Thanks for all of the ideas. It looks like we're discussing two basic kinds of models:
Sodaplay style provides physics for graphs, using forces in a spring and mass setup.
Sims/Framsticks style provides physics for trees, using forces and torques that propagate through the structure maybe using either reverse or forward kinematics.
I can see how one would program either one; I just don't know how to integrate them . They seem to be fundimentally differant approaches; the sodaplay physics rely more on the emergent behavior of the system while the Sims physics are more intentionally applied.
The sodarace site has some good links to work down with genetic algoritms and simulated annealing.
|
|
|
|
|
narain
|
Re: Spring-and-Mass Physics
« Reply #9 on: Apr 28th, 2004, 10:57am » |
|
I was just thinking about it, and I realised all that I was saying about torques isn't at all necessary. You can do it right within the existing spring-and-mass framework.
Instead of a single edge, you can use something that has thickness. Widen the connection between two places by splitting both vertices into pairs, and connecting them a pair of edges going straight and a pair of edges going crosswise. It would look like a long rectangle with diagonals, call it a "beam" if you will. There must be some examples at the Sodaplay site. (I'm posting from a place where the browser can't run Java, so I can't find them.)
I think this can work to integrate the two approaches. To bend a beam, or to transmit torque, just pull on one side and push on the other. The way muscles work. Joints could be triangles or squares, with some sides connected to, um, beams. Ugh. I want to call them limbs now.
Say, this is looking more and more interesting. Sodaplay organisms with muscles. That would be cooool.
What about the genotype encoding you were talking about? I have no idea how such things work, so I need some explanation.
|
| « Last Edit: Apr 28th, 2004, 10:59am by narain » |
|
|
|
|
mflux
|
Re: Spring-and-Mass Physics
« Reply #10 on: Apr 28th, 2004, 11:42am » |
|
awesome idea narain. It's a combination of sodaplay "structures", using them as muscles/bones, and using an IK/skeletal system for a higher level construction.
the evolution stuff works like this:
you have a dataset that "represents" the physical make-up of a creature.
you have the creature compete against another creature, basically stress-testing the dataset in an actual "environment".
the better creature will survive. the loser will get dumped.
make a copy of the creature that survived, and mutate it a little bit, and repeat the process.
in essence, a structure will emerge that will be most suitable for the environment, be it walking, running, swimming, fighting for food, reaching sunlight, growing tentacles.... etc....
SIGH! I wish I know more about physics!! This is my greatest regret ever.
|
|
|
|
|
narain
|
Re: Spring-and-Mass Physics
« Reply #11 on: Apr 28th, 2004, 5:49pm » |
|
Yep, physics sure is fun.
I knew that stuff about artificial evolution. What I wanted to know was how you can encode a whole organism's structure and behaviour in a single string, and how you can mutate it a little and get another organism just a little different...
I mean, obviously you can dump the whole thing into a file in some arbitrary format, and a file is nothing but a giant string of bytes, so instead of dumping to file you can dump to string. But what kind of format will allow little mutations without breaking?
|
|
|
|
|
TomC
|
Re: Spring-and-Mass Physics
« Reply #12 on: Apr 28th, 2004, 6:01pm » |
|
Quote:| But what kind of format will allow little mutations without breaking? |
|
HTML!
But obviously, that's not going to help you
If you don't want the headache of a robust recursive encoding scheme why not just have a fixed length one, with e.g. max 16 masses (could be null) and max 64 springs/muscles (could be null). This might be expressive enough to get something interesting running.
|
|
|
|
|
mflux
|
Re: Spring-and-Mass Physics
« Reply #13 on: Apr 28th, 2004, 9:46pm » |
|
oh...!
What's the advantage of expressing the construction data as a string? Faster? Smaller? .......?
|
|
|
|
|
TomC
|
Re: Spring-and-Mass Physics
« Reply #14 on: Apr 29th, 2004, 1:51am » |
|
If you express it as a Java String it will be easier to debug But I think narain is probably just talking about a string meaning any list of values. It could be a bit string, if values were true and false, or it could be a "string" of floats representing positions and rest lengths and amplitudes and phases.
On another note, I have made a loader for the Soda XML format using Mike's code as a starting point...
http://www.tom-carden.co.uk/p5/soda_rip/applet/index.html
Still can't get friction to work properly though, so Dirk Jiggler won't stand for long (no smirking at the back) and Dainty Walker won't walk properly... any clues?
|
|
|
|
|
|
