Author Topic: Darwinbots 3 Progress  (Read 28986 times)

Offline Prsn828

  • Bot Destroyer
  • ***
  • Posts: 139
    • View Profile
Darwinbots 3 Progress
« Reply #30 on: April 22, 2009, 01:35:15 PM »
Actually, I have a few zero-bot sims where the bots used venom quite quickly. Also, have you ever heard of the 'Falling Sand Game'? It uses clever tricks to quickly simulate thousands of particles of different elements, as well as their interactions, and does it extremely fast. I have actually made a version of it my-self, so I know it is actually quite simple. Further note that most are run in Java, the slowest of the High-level languages. A C++ version I know of can run 10,000 particles at 1,000 frames per second on a grid of 8,000 by 10,000 pixels (values are approximated).

You just have to think outside the box.

Oh, and DNA will be much more robust this time around.
So, what will it be? Will you submit to my will, or must I bend reality to suit my needs?
Better answer before I do BOTH!

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Darwinbots 3 Progress
« Reply #31 on: April 22, 2009, 08:15:13 PM »
Don't they work by having a huge matrix (*gasp*) of particles, and then defining a kernel (*gasp*) which acts on that grid?

I thought about doing something like that for the environment grid.  Or more precisely that was the environment grid.  But it's a huge amount of data usually.  And while the kernel operation is O(nm) for the dimensions of the matrix (n rows m cols, or whatever), O(8000 * 10000) is still a huge number.  Even if a clever algorithm can take advantage of the sparseness and get you down to O(n) for n particles, you still need a lot of particles.

So I dunno.  There might be some clever answers.  Will need to spend some time thinking about it.  An ideal solution would scale more or less linearly with the number of bots, regardless of sim size, just by clever coincidence.

Offline Prsn828

  • Bot Destroyer
  • ***
  • Posts: 139
    • View Profile
Darwinbots 3 Progress
« Reply #32 on: April 22, 2009, 11:54:46 PM »
Quote from: Numsgil
Don't they work by having a huge matrix (*gasp*) of particles, and then defining a kernel (*gasp*) which acts on that grid?

I thought about doing something like that for the environment grid.  Or more precisely that was the environment grid.  But it's a huge amount of data usually.  And while the kernel operation is O(nm) for the dimensions of the matrix (n rows m cols, or whatever), O(8000 * 10000) is still a huge number.  Even if a clever algorithm can take advantage of the sparseness and get you down to O(n) for n particles, you still need a lot of particles.

So I dunno.  There might be some clever answers.  Will need to spend some time thinking about it.  An ideal solution would scale more or less linearly with the number of bots, regardless of sim size, just by clever coincidence.

You use a giant int[][] where each int represents an element, and you go through the array performing local operations on small sections. You get to skip any empty/blank sections, so that greatly speeds up the process.  You can usually just use a dictionary to apply results, and results only occur within certain random probabilities, which further shrinks the task.  Often you must lock positions that have been edited, again decreasing the number of things left to iterate. All in all, it is a game of getting away with doing as little as possible, and ordering if statements as strategically as possible.

If we want to implement this in DB3, we will need to modify how it works, but it is doable, and it wouldn't really have an impact on the simulation speed since I doubt much would be moving around without gravity to influence things.
So, what will it be? Will you submit to my will, or must I bend reality to suit my needs?
Better answer before I do BOTH!

Offline Moonfisher

  • Bot Overlord
  • ****
  • Posts: 592
    • View Profile
Darwinbots 3 Progress
« Reply #33 on: April 23, 2009, 08:42:35 AM »
Took a look at those falling sand games, pretty cool demo's. Couldn't find the source though, but had a look at the forums.
Am I correct to understand that these particles will only interact with eachother, and that bots wouldn't collide or see them?
Or are you planning to change the way collision works for bots aswell? And if so... is there another clever way to avoid heavy costs in this area aswell?
Also on a sidenote if the bots can see the particles then they'll probably have a hard time navigating (Maybe instead of actualy seeing the particle the eye could see past them but still register the presence of a particle in the eye, or something like that)

Offline Prsn828

  • Bot Destroyer
  • ***
  • Posts: 139
    • View Profile
Darwinbots 3 Progress
« Reply #34 on: April 23, 2009, 01:33:31 PM »
Quote from: Moonfisher
Took a look at those falling sand games, pretty cool demo's. Couldn't find the source though, but had a look at the forums.
Am I correct to understand that these particles will only interact with eachother, and that bots wouldn't collide or see them?
Or are you planning to change the way collision works for bots aswell? And if so... is there another clever way to avoid heavy costs in this area aswell?
Also on a sidenote if the bots can see the particles then they'll probably have a hard time navigating (Maybe instead of actualy seeing the particle the eye could see past them but still register the presence of a particle in the eye, or something like that)

The reason for using these particles, I believe, is to allow them to act as environmental factors, such as sand, salt, water, etc. that bots could eat or absorb and use for various biological (or maybe it should be 'botological') processes, such as making shell, venom, etc.

Bots would be able to interact with the particles, and I believe they would likely need to break these particles off of solid, polygonal chunks of material in order to use them.
In this way, only the broken-off pieces would really interact with anything on a particle level, and the remaining polygon chunks will still be treated as a single object.

Speaking of polygonal chunks, I am proud to announce that I have had the pleasure of seeing just what a bot will look like (OK, maybe it isn't even close yet, but it IS the outline of the outer shell of the bot). In the past twenty-four hours, I have completed what is the majority of graphics commands that are necessary for the visual end of DB3 (The part you guys will be seeing the most of).

Now, I will explain how interactions will be handled:


Every physical thing in the simulation will be a type of SHAPE, which is to say, a thing with defined form(shape), but without a position and/or orientation.
A BODY is a collection of SHAPEs, and also defines the position and orientation of each of it's shapes relative to itself, as well as its own position and orientation relative to the simulation space.

Every SHAPE is able to give a BoundingCircle, which is centered at the center of mass of the shape, and within which the entire shape resides.

Since a circle can only overlap another circle if the SUM of their RADII is LESS than the distance between their CENTERS, it is fast and easy to tell if any two shapes MIGHT be colliding.

If it is found that two shapes might be colliding, then a vector that is said to be projected to the normal relative to each shape, as seen from the opposite shape this vector is coming from, is found, and can be used to determine how the collision is occurring, if it occurs at all. Don't quote me on this, I probably jumbled some of the descriptions in a bad order :/

Not only are these special vectors easy (for the computer) to compute, but the ones that are most commonly used are stored in a cache for near instant access, such that the value need only be computed once, and can be retrieved at any time afterwards.

Because of all of these methods (and some more that are a little confusing to myself, even though I may have been the one to program them in), it is expected that DB3 will be quite fast, despite the seemingly large amount of work it has to process.  Trust us when we say that we are going for speed, because even things like Area and Circumference are stored in memory to prevent recalculating them.

So far we don't yet have any sysvars, or any definitive format for the DNA, but I plan to work on that some more today.

Also, sorry if my capitalization earlier sounded a little harsh, I was just pushing some subliminal messages into your heads to help you understand easier

As always, any questions or comments are welcome, this thing is (hopefully) many years from being completed (meaning it will be maintained and improved for a very long time after its initial release as a usable program.)
So, what will it be? Will you submit to my will, or must I bend reality to suit my needs?
Better answer before I do BOTH!

Offline Moonfisher

  • Bot Overlord
  • ****
  • Posts: 592
    • View Profile
Darwinbots 3 Progress
« Reply #35 on: April 23, 2009, 09:01:11 PM »
Ehm, I'm a litle confused, you mention having water and air as particles, but then you also mention breaking particles off of polygons in order to use them.
If the entire environment is particles then it would no longer be cheap to process since you need to go over every pixel, and from looking at the sand games the method doesn't seem well suited for simulating large masses of particles blending together. I'm sure a lot could be done to improve performance and make the particles switch place if one is heavier than the other and stuff like that... but I think it would be a lot cheaper to have air and watter as a field and only simulate sand and minerals as particles.
I also think the way the sand physics works would have to be improved a lot in order for it to be realy usefull, or it'll just end up at the bottom as a rock hard wall.

But if you're planning to break the sand off of polygons to use them, then do we actualy need the particles ?

Also in case you haven't already done this, you can also find the radius for an entire body, this way you only need to check polygons within the radius against the polygons in the body.
Btw do you have t a link to some reference material you're using for collision?

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Darwinbots 3 Progress
« Reply #36 on: April 23, 2009, 10:38:20 PM »
Leaving aside computational costs for the moment, combing the sand games with alife would be cool.  Bringing back computational costs, well, ugh.  It is highly parallelizable, which is nice.  But it's just too much overhead for the present.

That said, I really don't know how the break off bits of polygons to allow for tunneling and mining.  It's not something other games do usually.  Dig Dug is still pretty much state-of-the-art.  So I'll need to figure out some options when I get that far.  The only two options I know of at the moment involve using a grid of particles or using unions of shapes and negative space.

Offline Prsn828

  • Bot Destroyer
  • ***
  • Posts: 139
    • View Profile
Darwinbots 3 Progress
« Reply #37 on: April 24, 2009, 01:30:04 AM »
Quote from: Numsgil
Leaving aside computational costs for the moment, combing the sand games with alife would be cool.  Bringing back computational costs, well, ugh.  It is highly parallelizable, which is nice.  But it's just too much overhead for the present.

That said, I really don't know how the break off bits of polygons to allow for tunneling and mining.  It's not something other games do usually.  Dig Dug is still pretty much state-of-the-art.  So I'll need to figure out some options when I get that far.  The only two options I know of at the moment involve using a grid of particles or using unions of shapes and negative space.

You don't have to know of a technique, just create one.

Most of the shapes are polygons, so break off a triangular section, turn the original into two valid polygons (since it probably just became part concave), and viola, you have your origonal, plus a loose chunk.  The math for it is extremely simple, basic algebra at the most; and you could specify, say, the area, or the mass, of the chunk you break off, to be a certain mass/size.

As far as dig-dug, me thinks they use a boolean grid for the dirt

Not that complicated, especially when compared to a falling-sand game.

And, now that you mention it, combining a falling-sand game with something like DB3 is something I have always wanted to do/see done.  Perhaps we will in another release (but DEFINITELY NOT in M1!!!)
So, what will it be? Will you submit to my will, or must I bend reality to suit my needs?
Better answer before I do BOTH!

Offline Prsn828

  • Bot Destroyer
  • ***
  • Posts: 139
    • View Profile
Darwinbots 3 Progress
« Reply #38 on: April 24, 2009, 08:50:28 AM »
Sorry about the double post, but an edit on the last one would have been unnoticeable.

There is a link HERE at the top of the page that will take you to the chat Nums and I use to collaborate.  If you want a real-time chat about DB3, that is the place to go.
So, what will it be? Will you submit to my will, or must I bend reality to suit my needs?
Better answer before I do BOTH!

Offline Arzgarb

  • Bot Neophyte
  • *
  • Posts: 8
    • View Profile
Darwinbots 3 Progress
« Reply #39 on: April 27, 2009, 01:32:56 PM »
Quote from: Prsn828
Oh, and DNA will be much more robust this time around.

One thing that currently reduces DNA evolvability is the mod:ing of values. For example, if a mutation changes a number to a logic operator, its value gets mod:ed to the number of values in the "logic operators" class. Since the amount of commands in other classes than number and *number is quite low (under 20 in all, I think), evolved DNA seldom contains large numbers. This could be fixed by not mod:ing the value of the base pairs and maybe storing the mod:ed value somewhere for faster use. What I mean is that while a bp now looks like (type, value), it should be changed to (type, value, modvalue), where modvalue only needs to be recalculated when a mutation occurs.

Quote from: Prsn828
Bots would be able to interact with the particles, and I believe they would likely need to break these particles off of solid, polygonal chunks of material in order to use them.
In this way, only the broken-off pieces would really interact with anything on a particle level, and the remaining polygon chunks will still be treated as a single object.

If particles can be broken off of shapes and then consumed by bots, you'll also want to allow them to be released again (maybe when the bot dies?) and to get packed together and transformed to a shape again. Otherwise you'll eventually end up with all material being chopped to particles and eaten up.

Offline Prsn828

  • Bot Destroyer
  • ***
  • Posts: 139
    • View Profile
Darwinbots 3 Progress
« Reply #40 on: April 27, 2009, 02:58:40 PM »
I don't quite get what you mean with the whole Mod:ing of base-pairs thing.

Right now, a point mutation call involves specifying the probability of each type of base-pair being the result.  For instance, one might choose that for a particular species, a point-mutation returns 25% numbers, 50% operators, 10% commands, and 15% (insert the other thing I can't remember here).

In this way, you could specify a larger % of numbers to be returned, and you would increase the proportion of numbers in the mutation results.

As far as shapes and stuff goes, don't expect to see chunks appearing anytime soon, but reforming will definitely be a factor when we get there.
So, what will it be? Will you submit to my will, or must I bend reality to suit my needs?
Better answer before I do BOTH!

Offline Arzgarb

  • Bot Neophyte
  • *
  • Posts: 8
    • View Profile
Darwinbots 3 Progress
« Reply #41 on: April 27, 2009, 03:21:38 PM »
Quote from: Prsn828
I don't quite get what you mean with the whole Mod:ing of base-pairs thing.

Right now, a point mutation call involves specifying the probability of each type of base-pair being the result.  For instance, one might choose that for a particular species, a point-mutation returns 25% numbers, 50% operators, 10% commands, and 15% (insert the other thing I can't remember here).

In this way, you could specify a larger % of numbers to be returned, and you would increase the proportion of numbers in the mutation results.

Well, that's not what I meant  

Another example: I created a tester bot whose DNA was a single pb, the number "345". I then set point mutation frequency to 1 and type-value slider to "100% type", put one bot to the simulation and watched. The "345" mutated to "~", then to "cond", then to "~" again. But when it got back to a number, it changed to 1. No value mutations occurred at any point.

What I think happened was that the bp was first of type "number" and value "345". When it mutated to "~", it was changed to type "bit command" and value "345 % X", where X is the amount of different bitwise commands in the program, because there is no bitwise command linked with the value 345. I can't read VB, so I have no idea how all this is actually implemented, but it seems to work this way.

Conclusion: numbers greater than about 50 are quite rare to occur in evolved DNA, because type changes will likely reduce them again.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Darwinbots 3 Progress
« Reply #42 on: April 27, 2009, 04:50:38 PM »
The DNA's underlying framework has changed.  In DB2, each element was a pair of numbers representing the type and the value.  Which lead to small numbers like you pointed out.  In DB3, the representation is fundamentally different.  A store command is just a store command.  There's no underlying numerical representation.  Which is actually a good thing, because it means when changing a store to a number, we just choose a random number.  Big numbers are as likely as small numbers.

Also, I do plan on trying to figure out how to have broken shape pieces glue back together.  Probably on contact.  So that shapes tend to be large instead of numerous and small.

Offline Botsareus

  • Society makes it all backwards - there is a good reason for that
  • Bot God
  • *****
  • Posts: 4483
    • View Profile
Darwinbots 3 Progress
« Reply #43 on: May 02, 2009, 12:44:48 PM »
btw: How do you update the "https://svn2.hosted-projects.com/Numsgil/Darwinbots3/" Because I see no Tags or Branches, do you commit all the changes directly to the trunk?

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Darwinbots 3 Progress
« Reply #44 on: May 02, 2009, 05:08:30 PM »
We update directly to Trunk atm, but there's a Branches and Tags folder.  I played with branching a few weeks ago to get the hang of it actually.