Author Topic: 2D or 3D?  (Read 10510 times)

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
2D or 3D?
« Reply #15 on: September 28, 2008, 05:15:49 PM »
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.
« Last Edit: September 28, 2008, 05:16:07 PM by Numsgil »

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
2D or 3D?
« Reply #16 on: September 30, 2008, 09:33:57 PM »
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.

Offline Cyberduke

  • Bot Builder
  • **
  • Posts: 88
    • View Profile
2D or 3D?
« Reply #17 on: October 01, 2008, 03:57:28 AM »
Quote from: Numsgil
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.
« Last Edit: October 01, 2008, 05:36:54 AM by Cyberduke »

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
2D or 3D?
« Reply #18 on: October 01, 2008, 01:26:17 PM »
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.

Offline bacillus

  • Bot Overlord
  • ****
  • Posts: 907
    • View Profile
2D or 3D?
« Reply #19 on: October 01, 2008, 07:24:50 PM »
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.
« Last Edit: October 01, 2008, 07:25:33 PM by bacillus »
"They laughed at Columbus, they laughed at Fulton, they laughed at the Wright brothers. But they also laughed at Bozo the Clown."
- Carl Sagan

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
2D or 3D?
« Reply #20 on: October 01, 2008, 08:13:32 PM »
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!
« Last Edit: October 01, 2008, 08:21:49 PM by Numsgil »

Offline Cyberduke

  • Bot Builder
  • **
  • Posts: 88
    • View Profile
2D or 3D?
« Reply #21 on: October 02, 2008, 04:28:16 AM »
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.
« Last Edit: October 02, 2008, 04:40:53 AM by Cyberduke »

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
2D or 3D?
« Reply #22 on: October 02, 2008, 04:44:30 AM »
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.

Offline Cyberduke

  • Bot Builder
  • **
  • Posts: 88
    • View Profile
2D or 3D?
« Reply #23 on: October 02, 2008, 04:45:09 AM »
Actually I have changed my mind, I doubt we can realistically afford sweep tests either
« Last Edit: October 02, 2008, 04:46:43 AM by Cyberduke »

Offline Cyberduke

  • Bot Builder
  • **
  • Posts: 88
    • View Profile
2D or 3D?
« Reply #24 on: October 02, 2008, 04:56:49 AM »
Quote from: Numsgil
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

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
2D or 3D?
« Reply #25 on: October 02, 2008, 07:00:57 PM »
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.
« Last Edit: October 02, 2008, 07:29:52 PM by Numsgil »

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
2D or 3D?
« Reply #26 on: October 02, 2008, 08:23:56 PM »
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).
« Last Edit: October 02, 2008, 08:24:53 PM by Numsgil »

Offline Cyberduke

  • Bot Builder
  • **
  • Posts: 88
    • View Profile
2D or 3D?
« Reply #27 on: October 03, 2008, 01:39:15 AM »
Quote from: Numsgil
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]
« Last Edit: October 03, 2008, 09:15:59 AM by Cyberduke »

Offline bacillus

  • Bot Overlord
  • ****
  • Posts: 907
    • View Profile
2D or 3D?
« Reply #28 on: October 04, 2008, 02:48:42 AM »
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.)
"They laughed at Columbus, they laughed at Fulton, they laughed at the Wright brothers. But they also laughed at Bozo the Clown."
- Carl Sagan

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
2D or 3D?
« Reply #29 on: October 04, 2008, 03:00:16 AM »
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]
« Last Edit: October 04, 2008, 03:04:20 AM by Numsgil »