Ignoring path finding and using collaborative diffusion

[Darhuuk]

I'm asking because the whole evening I started to optimize as well, because I had timeouts on the new cell_maze maps as well.

Wrote a testcase for myself:
200*200map (everything visible - so a full diffusion) with
100 enemy ants
100 friendly ants
100 food tiles

I'm getting 200diffusion-rounds in 330ms now.
(Unoptimized I took 1100ms)

Using Java, on a MacBookPro (2,4Ghz, Intel Core i5)

Wow, very nice! That's almost 5x faster than what I have. Do you do anything specific that I didn't mention in my list of tips? At the moment, I don't really see how I can optimize my code more, so all tips are welcome .

Edit: How do you create such a test map? Do you mind sharing it? It would be nice to do comparative benchmarks.

[bluegaspode]

I also 'just' moved a lot from the innerloop to the outside, so actually don't have any particular tip.
I don't know how you calculate the positions of the neighbour squares, but only for the tiles on the map edges you need to consider the world wrap.

With Java I could use good profiling tools so knew exactly what function I had to optimize next.

Here is the code to create a sample map.
Pretty simple and unrealistic actually, it just places enemies, frieds + food in row 0, 30 and 60 on every second field.
This is good enough for just measering a diffusion.

Code: Select all

public class GameStateBuilder {

   public static GameState create200x200() {
      GameState gameState = new GameState(1, 1, 200, 200, 2, 1, 1, 1, null);
      for (int row = 0; row < 200; row++) {
         for (int col = 0; col < 200; col++) {
            gameState.update(MapType.LAND, new Point(row, col));
            if (row == 0 && (col % 2) == 0) {
               gameState.update(MapType.ENEMY_ANT, new Point(row, col));
            }
            if (row == 30 && (col % 2) == 0) {
               gameState.update(MapType.MY_ANT, new Point(row, col));
            }
            if (row == 60 && (col % 2) == 0) {
               gameState.update(MapType.FOOD, new Point(row, col));
            }
         }
      }
      return gameState;

   }
}



[Darhuuk]

I also 'just' moved a lot from the innerloop to the outside, so actually don't have any particular tip.
I don't know how you calculate the positions of the neighbour squares, but only for the tiles on the map edges you need to consider the world wrap.

Ah, yes, thanks for the tip! Using a fully unwrapped diffusion function (250 lines of code, ugh), so that I don't have to do modulus calculations to wrap correctly, does improve the speed some more. For some reason, calculation time varies wildly, even between two subsequent rounds, but I can now get between 50-200 diffusion on a 200 x 200 grid per round.

[blue_iris]

(summarizing actual quote) People with slow languages might want to try fake diffusion like icefox suggested, it works pretty well.

What you are suggesting is not diffusion and will cause your ants to do strange/very non-optimal movements. Furthermore, it will work very badly in mazes. And you would need to diffuse from right -> left, top -> bottom & bottom-> top as well to get at least a reasonably working potential field in the presence of water. Plus, water will stop the "fake" diffusion anyway, so you're going to need multiple passes over your grid no matter what.

Your criticisms are valid.

I reviewed my bot's code, and my fake diffusion code was about as expensive as 16-pass regular diffusion.

So, err, never mind, probably not worth doing. Possibly useful in wide-open maps.

[mac]

what type of computer?
which language?
size of map?
how much of the map is visible (if this influences the calculations)?

Reading at other respondent type of configuration (and above all languages!) I feel pretty confident I squeezed all that I could from my implementation then! I'm running Ubuntu 11.10 on a Core 2 Duo T7400 2.16GHz with python, and on a 200x200 map I get 200/300 diffusion steps in ~400ms.

[zanirzrold]

I can't imagine why you'd need more than 200 iterations anyways (assuming it would be for unseen tiles)

[mac]

I can't imagine why you'd need more than 200 iterations anyways (assuming it would be for unseen tiles)

With my present implementation I don't in fact. However scents are the only way to drive an ant towards a target, so - say I want to attract all my ants towards the one and only enemy hill on the map - I won't be able to do that if an ant is more than X steps away from the target, where X is the number of diffusion steps [On 1500 turns game on maze maps, 200 turns to reach the the destination is not unimaginable.]

[zanirzrold]

I can't imagine why you'd need more than 200 iterations anyways (assuming it would be for unseen tiles)

With my present implementation I don't in fact. However scents are the only way to drive an ant towards a target, so - say I want to attract all my ants towards the one and only enemy hill on the map - I won't be able to do that if an ant is more than X steps away from the target, where X is the number of diffusion steps [On 1500 turns game on maze maps, 200 turns to reach the the destination is not unimaginable.]

right, but you don't want it diffusing too far anyways otherwise you get all your ants going towards the hill and no one getting food / defending.

Quick question: (if this gets too personal about your code, don't worry about it), have you implemented a caste system / do you think it's going against the "spirit" of col. diffusion to do so? I can see a lot of times where it would be useful, and I'm having to fake it by going off of time i.e. before the 20th turn, set the food threshhold higher, between turns 20-40 focus explore if you're so many spaces from the base, etc, but it's not that great, although considerably less work than doing a caste system as far as I can see.

[mac]

Quick question: (if this gets too personal about your code, don't worry about it), have you implemented a caste system / do you think it's going against the "spirit" of col. diffusion to do so?

Are you asking if I maintained a way to tell individual ants to perform a specific action regardless of the hormone configuration around them, based on other parameters? If this is the question, the answer is yes, although I substantially limit this mode of operating the ants for local tactical scenarios (fighting).

[zyberkiddy]

I am currently working on my diffusion for effective exploration. I have my food gathering working using diffusion but when it comes to exploration, its not effective.. Group of ants move towards unexplored area.. How can I make diffusion exploration similar to one that we get using plain bfs search for unseen area? What about weakening scent when an ant is encountered? I like to have uniform distribution of ants towards unexplored area.. Some one achieved this using diffusion?