2D or 3D?

[Cyberduke]

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.

[Numsgil]

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.

[Cyberduke]

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.

[Numsgil]

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.

[Cyberduke]

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://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.

[Numsgil]

http://www.codeplex.com/Wiki/View.aspx?Pro...=FarseerPhysics

Farseer I've played with a bit before.  I think it'd be a good place to start.

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.

[Cyberduke]

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.

[Numsgil]

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

[Cyberduke]

http://www.youtube.com/watch?v=SvqY_pgA6DU...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.

[Cyberduke]

or something like this
http://www.youtube.com/watch?v=gHPDJS74F70...feature=related
in a simulated fluid like this
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 Core

[Cyberduke]

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

[Cyberduke]

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]

[Numsgil]

http://www.youtube.com/watch?v=SvqY_pgA6DU...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.

[Numsgil]

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.

[Cyberduke]

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.