AI Challenge - Ants

[Max Wolter]

Ola.

Well, my A* algorithm is already working very nicely - and imo there 
isn't any problem-specific optimization left to implement other than the 
data structures holding the nodes themselves. So the question is only 
whether it would pay off to switch to D* instead.

Second, I'm aiming for the #1 spot :D. I have a lot of strategy in mind 
that I haven't seen implemented by anyone else yet and I think a TOP 10 
spot should definitely be possible. Minimizing the impact of the 
path-finding on computing requirements is thus certainly a priority.

/Max

On 10/29/2011 9:26 PM, Lishaak Bystroushaak wrote:
> Hi.
>
> I don't think, that you have to use some advanced strategies and path
> finding. I'm currently 261 with this simple code:
> http://pastebin.com/1Nsb81rj With hill defense and ant grouping, you
> could be imho easilly in first 100 without A* :)
>
> 2011/10/29 Sean Kelly<sean at invisibleduck.org>:
>> If you want to cheat, there have been books published on ant colony optimization.  I'm sure the related papers could be dug up.
>>
>> Sent from my iPhone
>>
>> On Oct 29, 2011, at 3:12 AM, Max Wolter<awishformore at gmail.com>  wrote:
>>
>>> On 10/25/2011 1:44 PM, Trass3r wrote:
>>>>> I'm working on a bot in D. I'm currently done implementing the A*
>>>>> algorithm for path finding
>>>>
>>>> Dump A*, D* Lite ftw ;)
>>>
>>> Hellooo.
>>>
>>> Correct me if I'm wrong, but in A*, I can just find a path, store it (let's say as a string) and find a new one if it's blocked for some reason.
>>>
>>> As far as I could see from what I've read about Lifelong A*, D*, Focused D* and D* Lite, I would have to store all nodes used in the algorithm - so, as opposed to A*, I have to conserve the state of the entire search algorithm throughout ticks, for each ant.
>>>
>>> Is the environment in this AI challenge really noisy enough to warrant this? Obviously, if the path needs to be re-planned almost every tick, D* Lite seems like a better choice to me. But if you have 100+ ants, that would be a lot of allocated heap memory, wouldn't it?
>>>
>>> I really don't have a clue how the processing vs allocating should be weighed here performance-wise.
>>>
>>> /Max
>>