Gravity Wells

[Memetix]

When I first heard about the contest a month ago and put some thought into how to approach the problem I made a fundamental decision to avoid pathfinding for individual ants. I realised that, if you were doing well and your number of ants was growing, your code would slow down to the point of timing out as the game progressed.

I decided to use the concept of gravity wells and I wanted to share my findings with the community. I suspect a top 20 position is possible using this technique, though my programming skills are very rusty (its been over 15 years) so I'm learning Java as I go and tending to produce code with bugs.
Version 12 of my software got to rank 23 and it had very buggy combat code.

Gravity Wells.
I imagine the map to be a large rubber surface. Then I place conceptual ball bearings of differing weights onto the rubber surface at key points (i.e. food, enemy hills, unexplored locations) and watch the rubber surface deform. Some balls are heavier than others (i.e. food is heavier than unexplored locations). Using a ripple out routine from each point of interest I score the tiles reached depending on the distance travelled from the ball bearing (using 1 over distance squared, just like gravity). The higher the score, the nearer you are to a point of interest.
This gives every tile on the surface a score and all we need to do to get effective exploration is to move each ant to the adjacent tile with the highest score (or stay still if it is in the best place already).

I got this working by adding about 200 lines of code to the starter package and at the start of a game, the code keeps up its growth rate with the best of them, only getting into problems when it meets other ants.

Once you have this map of scores the strategy can be improved by
1. Working out the best set of moves for your ants to maximize the total score after all the moves are done (rather than maximizing each ant individually)
2. Adding in some sort of combat code to work out if an enemy ant should act as an attractor (a ball bearing) or a repeller (helium balloon).

I'm stuck on how to approach option 1, any ideas?
Having recently discovered the tcp servers I've been able to improve my code for option 2 and I'm seeing some good results (See CombatAnts on fluxid if you are interested). I may post later on my approach to combat if people want.

[mac]

This sounds strikingly similar to diffusion (if you search for this term or "collaborative diffusion") you will find a few hits on the forum.

If I got how your code works, diffusion has the advantage of taking in consideration impassable tiles (water).

...but maybe I missed some nuance of how your algorithm works?

[deccan]

How do you prevent all your ants from simply converging in the area with the heaviest ball bearings?

[Memetix]

[Parasprites]

1. is a simple matter of constraint optimization. Combat is the hard part.

Anyway, the term for what you're doing is a influence map. Personally, I don't bother weighting. I just use min distance.

[dimkadimon]

[Memetix]

[ikaros]

What I wonder is:
How often do you run the bfs? One time for all food at once? Another one for exploration targets and so on? Or do you put everything into one bfs?
Do you add up the different weights ?
For example if you start in the middle of unexplored/unseen area would every tile there just have the base value for "unexplored tile" or would they add up to a very heavy weighted big area?

[Memetix]

[ikaros]

Thanks for the explanation.

I have implemented this myself now and try to use it for exploration only so far. In general it seems to work with some little flaws. There is one question remaining from my side

You say you put all tiles to explore in the bfs queue at once(which makes sense) but also your weighting function is weight/dist^2.

I understand how that works if you have one source .. like a food location. If the food is weighted with 100 you have a value of 100/4 two tiles away and 100/9 three tiles away and so on.

But with multiple sources how can I be sure about the source(and so the distance)? Because every visited tile has 4 influences(its neighbors) how do i determine which is the source?
I assume the exploration targets have different weights.. if not everything would be clear