Environment Grid - Revision history

PhiNotPi: Fixed typos

2014-02-15T01:08:42Z

Fixed typos

Numsgil: /* Resources */

2006-02-07T20:36:52Z

‎Resources

Numsgil at 22:02, 5 February 2006

2006-02-05T22:02:58Z

Numsgil: /* Uniform Density Point/Sphere Based Method */

2006-02-05T21:52:35Z

‎Uniform Density Point/Sphere Based Method

Numsgil: 3 methods are proposed for physically modelling the environment grid

2006-02-05T21:44:18Z

3 methods are proposed for physically modelling the environment grid

New page

The Environment grid is the combination of two ideas:

#Metabolites (nrg, poison, etc.) can exist outside of bots, and can pollute/change the environment for the bots.
#Physics constants can be different for different parts of the environment, allowing different areas for bots to hopefully adapt differently to.

The following are ideas on implementation that should be considered. All have pros/cons

== Don't Pee in the Pool (DPP) Method ==
The Environment is a single, large grid square, which all organisms interact with. Diffusion is assumed to be instantaneous.

'''Pros'''
* Is both memory and CPU time cheap.
* Allows the interaction between bots and environment pollution, hopefully meaning a virtuous feedback loop can be achieved.
'''Cons'''
* Location based effects are impossible. This means pheremone trails, "black smokers", and any other location based effects are simply not possible, thus eliminating a large number of possible environment interactions.

== Constant Sized Grid Squares ==
The environment is split up into a series of square/cubic grids, each of which has an amount of each substance and its own physics constants.

'''Pros'''
* Allows the interaction between bots and environmental pollution and resource depletion on a local level, which would have drastically different effects on evolution.
* Is roughly in the middle ground for CPU intensiveness. Diffusion would be a large calculation, but can be done every few cycles instead of once a cycle.
* Allows for broad pheremone trails (depending on the size of the grids).
* Allows for "Black Smokers"

'''Cons'''
* Absolutely insane memory requirements compared to the rest of the program.

:Lets assume 100 substances and no physics constants list. Lets assume 2 bytes for storage of the amount of each substance. This doesn't allow us decimal values, but let's ignore that for the moment. This means each grid is 200 bytes large. On largest size, a darwinbots field is 600 by 450 robot lengths. Such a grid would require about 52 Megabytes of RAM. This doesn't sound too bad, until we realize that this is strictly a 2D world. And we haven't added the physics constants which are mostly floats, which are roughly 8 bytes each.

:Should we ever want to go 3D (which I do), this would be 52 MB per level of depth.

* A 'Grid'y resolution. There will be a very distinct change in environment as a bot crosses a grid threshold. This may or may not matter to evolution, it's hard to say exactly. This problem can be eliminated by thinking of the amounts in each grid as being strictly applicable at the center of the grid, and fading between grids as a bot travels across them. The cost of this is a slightly increased CPU load.

* Diffusion becomes difficult to code. There are issues with updating a grid before reading from it. This can be alleviated by creating a double buffer for the grid, at the expense of double the RAM. Another way to alleviate this is to create a grid layer that buffers each layer as it is updated. This lowers the RAM overhead from the previous method.

== Uniform Density Point/Sphere Based Method ==
Every time a substance is released into the environment, it is represented by a sphere whose radius depends on time (radius increases due to diffusion over time). Inside this sphere it is assumed that the substance released has uniform distribution. The amount of substance at any point inside the sphere is given by the density times the area in question. That is: substance amount / substance's sphere's volume * volume of area in question (say, the volume a bot occupies, or perhaps the surface area of the bot, or something similar).

When a sphere enlarges to the point that it encompasses the entire play field, it's added to a giant grid square similar to the DPP method outlined above.

Physics constants are likewise represented by large spheres, though these spheres are of fixed size (or not, depending on what you're doing).

'''Pros'''
* Much RAM cheaper than the Uniform Grid Method, since we're basically only storing a collection of position vectors, radii, substance IDs, and amounts. Therefore, is scalable indefinately.
* Diffusion calculations are quite easy, you just increase the radii of the spheres.
* Eliminates the issues of grid locality. Substances smoothly transition from high to low concentrations.
* Allows for location based effects quite well (much better than the Unfirom Grid method).
* Allows for very specific pheremone trails to be laid.
* Allows for "Black Smokers" in a very natural formation, without the "Grid"-y resolution.

'''Cons'''
* Every substance sphere must be calculated against every bot every cycle. Possibly CPU intensive, though some collision detection algorithms might be applicable here. Complicated by the fact that substance spheres range in size from nothing to the entire field.
* I have no idea how accurately this models actual diffusion patterns.
* More research still needs to be done to verify the best way to handle this.

==Followup==
Numsgil likes the Uniform Density Point/Sphere Based Method at first glance, but more research is needed into the best way to handle it.

If you have any other ideas, feel free to post them in the [http://forum.darwinbots.com/index.php?showforum=11 Suggestions forum]

@@ Line 59: / Line 59: @@
 ==Resources==
 [http://www.double.co.nz/dust/GDC03.pdf Real-Time Fluid Dynamics for Games] - Possibly very useful.  It examines how you could have diffusion and fluid current interacting using a uniform grid approach.
 ==Followup==

@@ Line 13: / Line 13: @@
 * Allows the interaction between bots and environment pollution, hopefully meaning a virtuous feedback loop can be achieved.
 '''Cons'''
-* Location based effects are impossible.  This means pheremone trails, "black smokers", and any other location based effects are simply not possible, thus eliminating a large number of possible environment interactions.
+* Location based effects are impossible.  This means pheromone trails, "black smokers", and any other location based effects are simply not possible, thus eliminating a large number of possible environment interactions.
 == Constant Sized Grid Squares ==
@@ Line 21: / Line 21: @@
 * Allows the interaction between bots and environmental pollution and resource depletion on a local level, which would have drastically different effects on evolution.
 * Is roughly in the middle ground for CPU intensiveness.  Diffusion would be a large calculation, but can be done every few cycles instead of once a cycle.
-* Allows for broad pheremone trails (depending on the size of the grids).
+* Allows for broad pheromone trails (depending on the size of the grids).
 * Allows for "Black Smokers"
@@ Line 27: / Line 27: @@
 * Absolutely insane memory requirements compared to the rest of the program.
-:Lets assume 100 substances and no physics constants list.  Lets assume 2 bytes for storage of the amount of each substance.  This doesn't allow us decimal values, but let's ignore that for the moment.  This means each grid is 200 bytes large.  On largest size, a darwinbots field is 600 by 450 robot lengths.  Such a grid would require about 52 Megabytes of RAM.  This doesn't sound too bad, until we realize that this is strictly a 2D world.  And we haven't added the physics constants which are mostly floats, which are roughly 8 bytes each.
+:Lets assume 100 substances and no physics constants list.  Lets assume 2 bytes for storage of the amount of each substance.  This doesn't allow us decimal values, but let's ignore that for the moment.  This means each grid is 200 bytes large.  On largest size, a Darwinbots field is 600 by 450 robot lengths.  Such a grid would require about 52 Megabytes of RAM.  This doesn't sound too bad, until we realize that this is strictly a 2D world.  And we haven't added the physics constants which are mostly floats, which are roughly 8 bytes each.
 :Should we ever want to go 3D (which I do), this would be 52 MB per level of depth.
@@ Line 43: / Line 43: @@
 '''Pros'''
-* Much RAM cheaper than the Uniform Grid Method, since we're basically only storing a collection of position vectors, radii, substance IDs, and amounts.  Therefore, is scalable indefinately.
+* Much RAM cheaper than the Uniform Grid Method, since we're basically only storing a collection of position vectors, radii, substance IDs, and amounts.  Therefore, is scalable indefinitely.
 * Diffusion calculations are quite easy, you just increase the radii of the spheres.
 * Eliminates the issues of grid locality.  Substances smoothly transition from high to low concentrations.
-* Allows for location based effects quite well (much better than the Unfirom Grid method).
+* Allows for location based effects quite well (much better than the Uniform Grid method).
-* Allows for very specific pheremone trails to be laid.
+* Allows for very specific pheromone trails to be laid.
 * Allows for "Black Smokers" in a very natural formation, without the "Grid"-y resolution.
 * Lends itself easily differing diffusion rates for different substances.

@@ Line 56: / Line 56: @@
 * More research still needs to be done to verify the best way to handle this.
 * Does not lend itself easily to the idea of localized temperature interacting with diffusion speed.  Although Darwinbots does not presently have temperature, this could be a potential issue should temperature ever be implemented.
 ==Followup==