Darwinbots Forum
Code center => Darwinbots3 => Topic started by: Cyberduke on September 27, 2008, 05:19:12 PM
-
Hi, getting interested in this now, I have spend a good few hours now reading though the wiki and the forum for DB3 and I assumed it was going to be 2D but in the wiki it talks about a 3D simulation and plants with roots etc?
What is the current expectation for the physics simulation? And how advanced will it be?
The last time I played about with physics in a game each object in the world was approximated with a small collection of a primitive AABB ridged body’s with an Octree for spatial partitioning as used in the broad phase collision detection. Then you can go crazy with what it actually looks like later on when rendering in the client (it was a networked game). Though it would be cool to have a cell approximated as an OBB Polyhedron then it could really change shape and to join two cells you would pick the nearest face on each cell and join up the 6 vertexes.
As for digging, I have seen the fully destructible world demos but I wouldn’t know how to implement an ant digging a tunnel without creating the ground/wall from lots of smaller ‘blocks’ that can be excavated/destroyed.
2D would be simpler, by not a lot in any one area just overall, mainly it’s a little bit simpler and quicker for graphics (lots of objects onscreen), Collision detection, Quad tree instead of Octree.
Having said that 3D would be cool, but you have just given yourself a load of UI issues as I found out with my space RTS, you’re forced into coming up with some really innovative control schemes just to keep the UI usable if its not FPS based.
-
I was playing around with the idea of 3D at some point, but I abandoned it when I couldn't think of a decent way to present it to the user or the bots. The technical challenges aren't hard, it's more a UI and DNA thing.
The physics... this is complicated. I've been back and forth trying to decide between using an existing library and building my own. Most existing libraries don't quite work like I want them to. I understand most of the basics of physics engines so it's tempting to build my own, but things like joints can be confusing and deal with a level of math I never learned (Jacobian matrices). The bots themselves will be represented in physics by capsules: essentially two half circles of potentially different radii joined by a quad. Or two full circles joined by a quad. Same thing really.
Digging would probably be done with lots of smaller blocks, yeah. Maybe individual pixels even. Or maybe something that isn't square: have a hex grid for digging.
-
I thought chipmunk was the undisputed current flavour of the day in regards to 2D physics libraries I think I have seen an XNA port floating about somewhere too. From the demos I have seen it should be able to handle 2000 objects with ease, say a 1000 for cells and a 800 for clutter/structure in the environment and 200 for projectiles. I have only played about with 3D physics libraries and my own very basic 2D physics before though.
-
Chipmunk was one of the first I played with. I was initially impressed but something turned me off, I don't remember what (this would be over a year ago, so it's probably evolved since then). I think it was stacking. My expectations for stable stacking are probably too high. I briefly left some comments in their forum I think, so maybe I can go back and figure out what my issue was.
At another point I played with building a .Net wrapper around Box2D (Eric Catto's C++ library that Chipmunk is loosely based on, IIRC). Something turned me off this path, too. Might have been stacking again, but I can't remember. It also wouldn't have been XBox friendly (no unmanaged code allowed).
Then I spent about 8 months off and on (mostly on) playing with the idea of a non step based physics engine. Basically I'd calculate exact times of impact for all collisions projected indefinitely in to the future. It works pretty well for circles moving without drag (involves solving some quartics), but anything more complicated is difficult to impossible with present technology (a great deal of original research would need to be done. It's probably a masters or PhD thesis amount of work.)
So now I'm back full circle to thinking about a premade library. It needs to be all done in .NET so that I can load it on to my XBox, which leads back to Chipmunk probably.
BTW, it's nice to have someone else who's physics knowledgeable. When I started with Darwinbots I knew absolutely nothing about physics (my first big breakthrough was realizing you didn't need a square root to compare distances between points with other distances between points. And using vectors was big, too.) That was maybe 4 years ago or more, and I've learned a lot, but I'm still just playing it by ear.
ah, I figured it out. Chipmunk isn't native .NET, so you need either a port or a wrapper for it to work. I got part way through a wrapper, then got frustrated and went to build my own. Then got frustrated and went to Box2D for some reason and built another partway wrapper. Then got frustrated and went to build my own again, then got frustrated and here we are.
-
Well ok let’s try listing all the 2D managed physics libraries we can find then go though each one and review it.
Starting with...
http://www.codeplex.com/Wiki/View.aspx?Pro...=FarseerPhysics (http://www.codeplex.com/Wiki/View.aspx?ProjectName=FarseerPhysics)
http://physics2d.googlepages.com/ (http://physics2d.googlepages.com/)
My quad tree used the geometry from Physics2D.net (again with its roots in Box2D)
Ideally it would be good to have the physics as a completely separate module that could be swapped out for another one on a whim. That way you could play-test them all
Also in regards to stacking, I don't think I have ever seen a physics engine do it perfectly. it's normally a matter of playing about with the parameters until you get something you can live with.
-
http://www.codeplex.com/Wiki/View.aspx?Pro...=FarseerPhysics (http://www.codeplex.com/Wiki/View.aspx?ProjectName=FarseerPhysics)
Farseer I've played with a bit before. I think it'd be a good place to start.
http://physics2d.googlepages.com/ (http://physics2d.googlepages.com/)
My quad tree used the geometry from Physics2D.net (again with its roots in Box2D)
I think I played with this and it just wasn't feature complete enough.
Ideally it would be good to have the physics as a completely separate module that could be swapped out for another one on a whim. That way you could play-test them all
My goal is for all the modules to work like this actually. So you could swap out the DNA module for something that uses neural nets. Or swap out the graphics module for something that uses DirectX19 or whatever. At some point I'm just going to write some interfaces and that's how all the modules will communicate.
Also in regards to stacking, I don't think I have ever seen a physics engine do it perfectly. it's normally a matter of playing about with the parameters until you get something you can live with.
No, most of them don't handle it well. But I think it could be handled better than most do, especially in 2D. You can essentially reduce it down to a huge matrix inversion if you ignore things like a circle rolling down another circle (I could never figure out a clean way to handle that other than pushing them out from each other when they intersect).
Most users don't seem to mind a bit of stacking issues, though, so maybe it just doesn't matter.
-
Well I don’t know if you’re the same but for personal projects I have an annoying tendency to get hung-up about a particular feature and want to keep re-working it until its perfect, which of course just means that the project doesn’t get completed in anything like a reasonable timescale. At work I just get told to leave it be and move on. Get the project up and running so the testers can start playing with it, then come back to look at bits I am not happy with and are in need of some adjustments or refactoring.
Half the time when you come back to it you end up agreeing it’s probably fine as it is anyway.
-
Yes, that is my problem. Mentally I understand the idea of getting it minimally working so you can start getting testers on it, but in practice it's a hard pill to swallow
-
http://www.youtube.com/watch?v=SvqY_pgA6DU...feature=related (http://www.youtube.com/watch?v=SvqY_pgA6DU&feature=related)
http://www.youtube.com/watch?v=DFnmnMK1Yvw...feature=related (http://www.youtube.com/watch?v=DFnmnMK1Yvw&feature=related)
Heh Jello Physics would be cool, it's a soft body simulator, but it only looks to be capable of a few dozen active objects.
-
or something like this
http://www.youtube.com/watch?v=gHPDJS74F70...feature=related (http://www.youtube.com/watch?v=gHPDJS74F70&feature=related)
in a simulated fluid like this
http://www.youtube.com/watch?v=9oGnCeE5wFM...feature=related (http://www.youtube.com/watch?v=9oGnCeE5wFM&feature=related)
*puts reality goggles back on*
I would say we already have an upper limit of say 800 cells, if each one is described by 3 ridged bodies then we are talking a max of 2400 for the cells and say 200 for particles and projectiles, and that is probably our limit. 2600 objects constantly subjected to various forces and around say 15% of them involved in narrow phase collision detection at any one time is probably nearing the full load of 1
-
I know you have probably been around this cycle of thinking before but bear with me.
Can we not simulate the cells as a circle?
They don’t have to actually look like a circle they could be a roughly circular polygon to allow for direct joining etc.
It would put alot less stress on the physics side of things. As it's the narrow phase collision detection that really screws you.
In fact the physics simulation could look a lot like the current DB2 simulation, circles joined to each other with a tie of varying stiffness; you could then display that as a lattice of polygons all neatly sealed up. The physics underneath just needs to approximate how you wish the objects to behave.
Which do you want this to be closer too, a scientifically accurate simulation, or a game?
If you want accuracy you either need to limit yourself to about a dozen objects or buy some time slots on a super computer
-
When you come to draw the environment nothing stops you from embellishing it slightly.
Ok so they will still only get hit if something hits one of the bounding circles. But if they (your embellishment and reality) are close enough its ok, the bots won’t know any different. And since the player isn’t trying to shoot at them they won’t notice either.
You will have the position and size of all the cells, so from their you draw a more pleasant looking cell (Instead) over the area the real simulated one is, and if there is a join then you can just join up the exterior of the clump of cells if you like.
[attachment=1005:Drawn_Cell_Example.png]
-
http://www.youtube.com/watch?v=SvqY_pgA6DU...feature=related (http://www.youtube.com/watch?v=SvqY_pgA6DU&feature=related)
http://www.youtube.com/watch?v=DFnmnMK1Yvw...feature=related (http://www.youtube.com/watch?v=DFnmnMK1Yvw&feature=related)
Heh Jello Physics would be cool, it's a soft body simulator, but it only looks to be capable of a few dozen active objects.
Yes, I was also playing with the idea of soft body physics at one point. But they're just way too computationally expensive. For something like this the more bots you can simulate the better.
-
I know you have probably been around this cycle of thinking before but bear with me.
Can we not simulate the cells as a circle?
They don’t have to actually look like a circle they could be a roughly circular polygon to allow for direct joining etc.
It would put alot less stress on the physics side of things. As it's the narrow phase collision detection that really screws you.
In fact the physics simulation could look a lot like the current DB2 simulation, circles joined to each other with a tie of varying stiffness; you could then display that as a lattice of polygons all neatly sealed up. The physics underneath just needs to approximate how you wish the objects to behave.
Which do you want this to be closer too, a scientifically accurate simulation, or a game?
If you want accuracy you either need to limit yourself to about a dozen objects or buy some time slots on a super computer
The problem comes from trying to design a creature like a squid and control it through DNA. If bots are circular, they are the joints, and connect to each other with bones (for lack of a better word). If they're long capsules, they're the bones and connect to each other with joints. The former was my original thinking, but it poses a few problems:
1. You have to simulate the bones anyway, and make sure that they're stiff. Meaning lots of constraints between bots to keep them just the right distance apart, which makes for complex physics anyway. You only save time on the narrow phase to pass it on to the constraint solver phase. Anyway, capsules aren't too bad at the narrow phase. You can implement a SAT (separating axis theorem) test fairly easily.
2. In order to have bots control the motion of the larger multibot, they need to be able to do things like apply a force to change the angle between two bones. Suppose you have a bot with 10 bones connecting it to other bots. It would need to specify two bones and then a force to change the angle between them (or maybe specify a delta angle and a max amount of energy to spend or something). Something like that isn't terribly likely to evolve. In contrast, if bots are the bones and connect to each other with joints, a bot only needs to specify a single joint and a force. Which is far more likely to happen.
When you come to draw the environment nothing stops you from embellishing it slightly.
Ok so they will still only get hit if something hits one of the bounding circles. But if they (your embellishment and reality) are close enough its ok, the bots won’t know any different. And since the player isn’t trying to shoot at them they won’t notice either.
You will have the position and size of all the cells, so from their you draw a more pleasant looking cell (Instead) over the area the real simulated one is, and if there is a join then you can just join up the exterior of the clump of cells if you like.
[attachment=1005:Drawn_Cell_Example.png]
Sure, there's lots of fun things you can do graphically.
-
The problem comes from trying to design a creature like a squid and control it through DNA. If bots are circular, they are the joints, and connect to each other with bones (for lack of a better word). If they're long capsules, they're the bones and connect to each other with joints. The former was my original thinking, but it poses a few problems:
1. You have to simulate the bones anyway, and make sure that they're stiff. Meaning lots of constraints between bots to keep them just the right distance apart, which makes for complex physics anyway. You only save time on the narrow phase to pass it on to the constraint solver phase. Anyway, capsules aren't too bad at the narrow phase. You can implement a SAT (separating axis theorem) test fairly easily.
2. In order to have bots control the motion of the larger multibot, they need to be able to do things like apply a force to change the angle between two bones. Suppose you have a bot with 10 bones connecting it to other bots. It would need to specify two bones and then a force to change the angle between them (or maybe specify a delta angle and a max amount of energy to spend or something). Something like that isn't terribly likely to evolve. In contrast, if bots are the bones and connect to each other with joints, a bot only needs to specify a single joint and a force. Which is far more likely to happen.
In regard to point 1) without testing and profiling I am not currently sure which would turn out to be the biggest cumbrance.
I just wanted to make sure we really are at the simplest we reasonably can be in regards to the physical simulation, because as you know it’s very easy to get carried away with all the neat things you can do, whilst forgetting the need to strike a balance with performance at scale. And so much will be underpinned by the basic cell structure and the way the joints work.
But it sounds like you have already put a lot of thought into this.
You make a very good point though in regards to removing the additional ‘bone’/tie as not only would something interesting be more likely to happen from an artificial evolution standpoint but capsules with direct joints would also scale better performance wise if the majority of organisms where multi cellular. Capsules would of course scale worse if most where single celled.
As a side note, I think some thought might want to go into crafting a ‘nursery’ environment with constant but bearable selection pressures to get evolution to produce something that utilizes some of these neat opportunities, since so much is being designed with that goal in mind.
-
Capsules aren't too hard. If you're doing a SAT test, you just have to test the interval of the centers of the two circles. Which is as cheap as a rectangle, for instance. If you're doing a circle-circle radii test, then you have to do a full two circle vs. two circle test, which is a bit more expensive. But on the whole I think it's manageable. And with any luck something else will end up being the bottleneck anyway
As far as nursery environments, there's been a lot of work in that regard on the forums with the current version. Check out some of the zero bot sim threads, for example.
-
Dug around in my notes. This is what I wrote to myself (since I keep ping pong-ing on the issue):
"Other simulators lack key requirements for Darwinbots:
1. Shapes changing size or even shape (both increasing in volume/area and changing shape (circle to capsule))
2. Drag to allow for swimming bots
3. Reversible time step (would be cool, but not required)
4. Stacking (very tall) (for use in something like a plant)"
#3 is entirely ignorable. It was my thinking that debugging bots would be much easier if you could step forwards and backwards in time in the simulation, but it probably has to be implemented using a cache of previous cycles anyway, since things like DNA are NOT reversible.
#2 involves simulating the forces needed for a swimming multibot. You need drag simulated in such a way as to produce torque. Most cheat and do something like velocity *= .99f, which won't work.
#1 is just something I don't think any engines support. They probably should, though.
So really there are 3 core issues that need to be addressed in any library we use, or any library we build.
-
Dug around in my notes. This is what I wrote to myself (since I keep ping pong-ing on the issue):
"Other simulators lack key requirements for Darwinbots:
1. Shapes changing size or even shape (both increasing in volume/area and changing shape (circle to capsule))
2. Drag to allow for swimming bots
3. Reversible time step (would be cool, but not required)
4. Stacking (very tall) (for use in something like a plant)"
#3 is entirely ignorable. It was my thinking that debugging bots would be much easier if you could step forwards and backwards in time in the simulation, but it probably has to be implemented using a cache of previous cycles anyway, since things like DNA are NOT reversible.
#2 involves simulating the forces needed for a swimming multibot. You need drag simulated in such a way as to produce torque. Most cheat and do something like velocity *= .99f, which won't work.
#1 is just something I don't think any engines support. They probably should, though.
So really there are 3 core issues that need to be addressed in any library we use, or any library we build.
1 and 2 are fair points, and I would be tempted to look into creating a physics interface first to allow for swapping between implementations (either custom ones or mainstream libraries) this then gives a bedrock upon which other features can then more confidently be independently developed and tested whilst the physics behind the interface are honed/swapped out completely.
You are talking me around to the idea of a custom ‘tailored’ physics engine though, which I would normally be hesitant of due to fact I have a feeling it could become a large and frustrating time sink, and especially in light of recent talks of vapourware.
But it would mean that we could play about with using a quad tree (I like quad trees) for the broad phase for both the collision detection and the sensor lookup spreading the cost of maintaining a quad tree across both features. (Yeah I am not sure how that plays with the interface idea yet either)
3 would also be good if we ever wanted to produce a multi-user single instance sim for correcting client side prediction faults, but I think we can forget that.
4 hmmmmm, I would be very tempted to just cheat on that one. I would be very impressed if you got that working satisfactorily.
-
My view towards interfacing the modules is to hold off until there's something working. That way practical need drives the interfaces instead of the other way around (I want to avoid the "hmm, we might need this" trap.)
I've worked out stable stacking for squares and other polygons on paper. Well, so long as their angular velocity per cycle is not too high. Circle-circle stacking, though, is considerably harder, especially if you want one circle to roll down the other without slipping. But you're right, it's a huge time sink.
Maybe we just take an existing engine as a base and modify the crap out of it. That gives us something that works, for the most part, right away, and lets us add features as necessary.
-
My knowledge in this field is quite close to zero, but it seems that all is needed to hold two circles in place is to calculate the amount of force that is tangential to the static circle (a kind of x-y coord taking the radius as x and the tangent at the pint they meet as y), then calculating the friction between the two circles that the tangent force needs to overcome. And if it comes to that, bots could just stick themselves together in a certain form, sort of like squashing together snow to make a snowball.
-
Here's the problem: imagine you have a huge circle and a smaller circle. Maybe the smaller circle is 1/10th the radius of the larger circle.
The smaller circle is on top of the larger circle, and starts to roll down. I can calculate tangent and frictional forces fairly easily. Anyone who's had an intro to physics course should be able to do that part. The hard part is then what to do with that information. If I step the simulation forward even 1/10000th of a second, the smaller circle will have moved in a ballistic path, which does not exactly follow the curve of the larger circle (it underestimates it in this case). It will have left the surface of the larger circle; it is now floating a few inches (or whatever) above the surface of the larger circle. If I step the simulation forward another 1/10000th of a second, the smaller circle is now inside the larger circle, since the tangent and friction forces no longer apply since they are no longer touching, and gravity rules supreme. The simulation detects that a collision between the two has occurred, and applies the proper impulses to both bodies. This process continues, and what you end up with is a bouncing, spinning circle on top of a larger circle, when the correct behavior is for the smaller circle not to bounce at all, but to smoothly roll down the larger circle.
It might not matter, of course. You might be able to ignore it in issues like this. But it isn't correct, and worse(!), the end behavior depends immensely on the step size. If I use 1/100th of a second instead of 1/10000th, I'll have a completely different motion. But by contrast I can model exactly the behavior of a square sliding down a ramp for some given time interval (until the square reaches the end of the ramp). It boils down to a polynomial. If I have two squares sliding down the same ramp, and one is stickier than the other and sliding slower, I can calculate the exact moment of collision by solving a 4th degree polynomial. Most physics engines work by moving the objects in the world some fraction of a second, then testing for collisions and resolving, then moving another fraction of a second, etc. I was imagining a system that didn't need to be stepped at all. Each body would know it's exact state at any time between now and when it eventually collided with something. I called this time interval an "epoch", but it might have a real name. After collisions, new epochs would be calculated for all bodies involved, (resulting in a possible cascade of collision calculation as these new epochs invalidated other epochs, etc. etc.).
It works fine for some very limited cases. As long as these hold true, it works:
1. Bodies are composed of unions of polygons. No curves. I can't simulate sliding along a curve, since the curve motion isn't polynomial. That is, I can't solve an equation like sin(x) - f(x) = 0, at least not without resorting to numerical methods.
2. Bodies do not rotate (although I was playing with the idea of approximating rotations with quadratics) or are limited to only circles (conflicts with #1).
3. All motion consists of discrete time periods of constant acceleration, so that the motion can be represented as a piecewise quadratic. Like, from 0 to 1 seconds acceleration is <0, 10, 0>, and from 1 to 5 seconds it's <10, -20, 0>, etc. That eliminates drag forces, spring forces, etc. etc.
Basically all three boiled down to the same issue: at some point I have some function, dependent on time, which represents the motion of a body. Colliding two bodies together requires subtracting the motion of one body from another, and finding the smallest positive zero, if it exists. I can do this extremely easily with the 3 limitations above since it just becomes a vector quadratic minus another vector quadratic. That is, something like this: At^2 + Bt + C = 0, where A, B, and C are vectors. In order to solve it, you square both sides, which gives a quartic equation that can be solved analytically (it's known how to solve up to quartics analytically. Something with degree 5 or higher isn't known (or might not be possible, I forget which)).
But there are lots of motions that can't be simulated well with a quadratic. Springs and viscous or turbulent drag, and lots of others. There might be some tricks I'm unaware of (I played with taking an arbitrary equation of motion, bounding it's first zero, and fitting a quadratic to the motion just during that window, for instance), but I realized that getting it working would probably be on par with a PhD thesis, which is more work than I wanted to do. Plus if I have to use iterative methods to find the time of impact, I basically am reinventing the wheel with existing methods for swept collision detection (I think there's an algorithm called conservative advancement which does this, and is employed in most physics engines).
Heh, that was probably a more long winded explanation than anyone wanted. To sum: physics simulations are hard!
-
Well we have officially gone beyond the realms of my knowledge but, I get the feeling you might be getting carried away with the elegance of the maths and ignoring the practicalities of actually implementing it, yes some kind of projection model has a huge accuracy benefits and solves all the problems inherent with a fixed step model using static collision tests such as object penetration or skipping over objects entirely in the duration of a frame and building up precision errors and has such should stack/rest perfectly but I can’t help feeling you would be over complicating things. Don’t forget this has to work with over 1000 bodies that don’t just collide but need to sense other objects and all inside something like 50ms.
Ok I give you that since we could have very small objects we could do with using some kind of sweep test though I suppose.
I think we might be better just playing about with a few systems to get a feel for what the real issues might be in practice and what we feel we can live with rather than just speculating though.
-
Yes, I'm done playing with my ideas for physics engines, for a while anyway. Something more traditional is far easier to find and set up.
-
Actually I have changed my mind, I doubt we can realistically afford sweep tests either
-
Yes, I'm done playing with my ideas for physics engines, for a while anyway. Something more traditional is far easier to find and set up.
Well that’s the beauty of this modular approach
-
I think I'm just going to make my own physics engine, but do it like the current version where it's all spring based. It's not a great solution, but it's easy to set up quickly and I can wash my hands of the whole affair until I can stomach playing with physics more in depth. Plus, it'll be easier to leverage broad and narrow phase collision detection for things like vision if it's built with that in mind, instead of trying to leverage an existing library in.
-
I also think I'm going to use isosceles trapezoids at first, instead of capsules. It makes for much easier calculations. And the two are very close in shape (the trapezoid will overestimate the size on the caps of the capsule essentially).
-
I also think I'm going to use isosceles trapezoids at first, instead of capsules. It makes for much easier calculations. And the two are very close in shape (the trapezoid will overestimate the size on the caps of the capsule essentially).
Now that sounds like a plan...
You don’t have to hit upon the perfect solution first time around, just implement something and play around with it. I like this idea as it keeps everything simple for now. And it’s even something I could live with long term.
Polygon_Capsules
[attachment=1028:Polygon_Capsules.png]
-
I think that would look cool, especially with some sort of interpolate draw mode where the bots and multibots could be drawn smoothly as one big shape (optional, of course, else it would be too memory-consumptive.)
-
Hmm... octagons would work pretty well actually.
Quick point: both ends don't have to be the same size (I'm trying out my wacom tablet, which I still haven't gotten the hang of):
[attachment=1031:Capsule.png]
So you could make something like this:
[attachment=1032:Eye.png]
-
Ok, so back to the semicircle-quad-semicircle model, We could replace the semicircles with two semi-hexagon approximations of different radii, then connect them using a quad.
/-------------------\
/ \
/ \
| |
| |
| |
\ /
\ /
\____________/
-
Yeah, I think I'm going to play with that idea. Polygons make lots of issues easier to deal with.
BTW. you need to use code tags ([ code ] [ /code ] but without spaces) for ascii art. I added them to your post for you However, it seems that when you're composing a post it's using a different font from when you submit the post, so things still get messed up. Maybe if you set the font to something monospaced, like arial.
-
No, I tries to fix it using tabs, that'll be the problem.