Ignoring path finding and using collaborative diffusion

[stupidquestions]

Well, I'm just starting out really... I tried putting my "move to" locations in a vector and checking if a location was "taken" before assigning it to another ant's move (something similar to what's in the tutorial)... It didn't really work well, I realized how I could improve it but concluded that it would be a bit of a drag coding that stuff. And it's not really in the spirit of diffusion.

Aaand I tried simply assigning food value (and all the other values, but I still didn't write the code that makes these values relevant, my ants are constantly in "food mode") 0 to my ants' locations, but the problem with that was that my ants (obviously) didn't want to even come close to each other, plus it sometimes stopped them in getting food which was close to them.

[mac]

And it's not really in the spirit of diffusion.

I don't know how you implemented your diffusion algorithm, but - generally speaking - the following rules apply to diffusion in the ants game:

• The scent is emitted by some kind of entity (food, enemy, hill...)
• The presence of your own ants close to an emitter should - in most cases - dampen its scent.
• "Smelly entities" interact automatically with your ants (food is collected, battles are fought, hills are razed) if these come at a certain distance from it.

This considered, if you implemented your algorithm correctly, the amount of ants clashing with each other should be minimal, already, as the scent perceived by two ants proceeding towards the same goal in parallel will be stronger on "the other side" and the entity emitting the scent will stop doing that the moment an ant will be close enough to interact with it.

There is nothing wrong with the method of collision avoidance of the starter kit (although it can be improved upon by - for example - evaluating which of two ants wanting to go to the same location should have the precedence) but the amount of ants wishing to collide in the first place should be low!

HTH!

[stupidquestions]

Well, if I set my ants to dampen the smell a lot, they won't approach each other, which means they'll be isolated and easier to destroy by the enemy. On the other hand, if I set them to dampen the smell too little, they'll collide with each other a lot.

Anyway, thanks for the answer.

[erdman]

After reading this thread and the original linked paper, I implemented something that I called 'diffusion', but reading elsewhere, others call what I have implemented 'wavefront search'.

What is the 'collaborative' part of collaborative diffusion? How does it compare to wavefront search?

[bluegaspode]

the collaborative part is by the 'dampening' described above.

Two ants side by side will soon go into two different directions to gather food. Or avoid enemies automatically while still heading for the food tile (with a very limited set of diffusions per round).
A good example is in the paper from the first post from the PacMan game, where two enemies of PacMan will automatically choose different ways to circle the PacMan.

Here are some cool animations: http://scalablegamedesign.cs.colorado.e ... _Diffusion

Wavefront Search will find you shortest paths, so (based on your implementation) two ants might always follow the same food.
If you want to avoid that you'd need multiple waves for each ant and will lose a lot of computation time of you a loads of ants.

[tokugawa]

The only concern is that now the diffusion map keeps getting hotter and hotter (because the water squares are no longer functioning as a sink), and at some point that means that information is lost, because the number of steps between high and low gets smaller over time. But I suppose I could just divide all values on map by 2 every so many turns if it becomes a problem.

This is the problem I've dealing with now. After I raze an enemy hill, the hill scent lingers and my ants stay in the area. In more open maps, it's not a big problem, but in tight maze-like maps, the scent will remain for a very long time. I'm trying out a few strategies for dealing with this, but none have proven optimal quite yet.

[Darhuuk]

This is the problem I've dealing with now. After I raze an enemy hill, the hill scent lingers and my ants stay in the area. In more open maps, it's not a big problem, but in tight maze-like maps, the scent will remain for a very long time. I'm trying out a few strategies for dealing with this, but none have proven optimal quite yet.

I'm also having this problem, although not a whole lot. Three very easy things you can do about it are:

- Fiffuse more per round: right now, I have multiple potential field grids, some of which are only diffused 1 time per round, while others are diffused 12 times. Ideally, I would diffuse 40-50 times, but this uses more than 500ms on the official server (though it's perfectly feasible to do so in under 500ms on my own PC)

- Reset your fields: if you have a separate field for hills for example, you could reset it after a hill has been razed. This will completely remove any lingering scent from the razed hill. The only problem it might cause is that the scent from another hill gets lost, but most probably you already have other ants nearby, so a few diffusion iterations should fix any pathfinding problems they might have.

- Increase your diffusion rate: the higher your diffusion rate, the quicker a scent will go away once it's source is gone. Don't go over a factor 0.25 though or you won't be diffusing anymore.

[tokugawa]

- Fiffuse more per round: right now, I have multiple potential field grids, some of which are only diffused 1 time per round, while others are diffused 12 times. Ideally, I would diffuse 40-50 times, but this uses more than 500ms on the official server (though it's perfectly feasible to do so in under 500ms on my own PC)

I'm doing this now. I diffuse as many times as I can for half the turn time and then use the other half for moving ants. On an average map on my PC, I can usually get 15+ diffusions per turn, but on the bigger maps I'll get only 5 or so. I really don't have any way of knowing how many times I'm diffusing on the official server.

- Reset your fields: if you have a separate field for hills for example, you could reset it after a hill has been razed. This will completely remove any lingering scent from the razed hill. The only problem it might cause is that the scent from another hill gets lost, but most probably you already have other ants nearby, so a few diffusion iterations should fix any pathfinding problems they might have.

This is probably the best solution, but I hate losing my diffusion history. Especially the hill scent where it may take several turns to get the scent to diffuse through the map.

- Increase your diffusion rate: the higher your diffusion rate, the quicker a scent will go away once it's source is gone. Don't go over a factor 0.25 though or you won't be diffusing anymore.

I fiddle with the rate but usually set it between 0.2 and 0.25.

[zanirzrold]

First of all, you should be able to have a minimum of 100 diffusions a turn with no problem (I can do about ~300 although only do 200 to make sure I don't time out). If you're doing multiple maps for different scents, thats~20-30 diffusions per map. If you're not this efficient, figure out a better way to do it. I'll leave the implementation to you.

Second, if you're having problems with enemy hills, here's a suggestion, but certainly not the only way. Think of ways you can figure out if you just killed a hill. If you did, reset your enemy hill scent to 0 across the map, reset your enemy hills, and diffuse 30-40 times to get the scents back out (this shouldn't take a very long time, because most of your map will be 0s). Conversely, you could also give a negative scent to the hill just captured (which then as it diffuses should go to zero and pull everything around it to zero as well). Experiment!

[Darhuuk]

I'm doing this now. I diffuse as many times as I can for half the turn time and then use the other half for moving ants. On an average map on my PC, I can usually get 15+ diffusions per turn, but on the bigger maps I'll get only 5 or so. I really don't have any way of knowing how many times I'm diffusing on the official server.

Profile your code. If you're using Linux, I suggest having the python scripts call your bot with: "valgrind --tool=callgrind <your bot executable here>". That way, you don't have to add any profiling/debug code which might skew measurements. The easiest way to inspect your code would be with KCachegrind, very nice gui and certainly heaps and bounds beyond profiling with gprof.

You really shouldn't need half the turn time to calculate the movements of your ants. You're not doing A* here, you just have to look at neighboring squares for each ant, decide which moves would be best and do some collision avoidance. All of that takes 0.03% of the time in my implementation (half of which is spend finding moves, the other half doing collision avoidance).