It is currently Sun May 29, 2016 1:22 pm Advanced search

Ignoring path finding and using collaborative diffusion

Share and discuss ideas for your entries here.

Ignoring path finding and using collaborative diffusion

Postby icefox » Thu Nov 03, 2011 12:23 am

For my solution I took a look at collaborative diffusion rather than doing any shortest path finding. I ended up writing up a whole fun blog about this strategy (sorry no code or advanced diffusion strategies until after the end of the challenge). So if your tried of implementing A*, shortest path caching, or just looking to check out a different approach: http://benjamin-meyer.blogspot.com/2011/11/using-collaborative-diffusion-rather.html
icefox
Cadet
 
Posts: 9
Joined: Wed Oct 26, 2011 6:08 pm

Re: Ignoring path finding and using collaborative diffusion

Postby ChrisH » Thu Nov 03, 2011 4:33 am

Based on your blog post this sounds like an enhanced version of breadth-first-search, would you agree?
ChrisH
Colonel
 
Posts: 57
Joined: Tue Nov 30, 2010 8:54 pm

Re: Ignoring path finding and using collaborative diffusion

Postby Narsis » Thu Nov 03, 2011 4:47 am

this strategy is actually the very first thing that came to my mind, but i didn't know much about it so put it off. after reading the blog post(and linked article) i've decided to try this again. one question though:

You mention that the runtime is O(rows*cols). how is that faster then the time required for pathing algorithms?
Narsis
Cadet
 
Posts: 3
Joined: Thu Nov 03, 2011 4:34 am

Re: Ignoring path finding and using collaborative diffusion

Postby icefox » Thu Nov 03, 2011 4:55 am

ChrisH wrote:Based on your blog post this sounds like an enhanced version of breadth-first-search, would you agree?


A bfs is just a graph search algorithm. The typical implementation is to find the shortest path from a root node to a destination node. Collaborative diffusion using agents and an anti-object is useful for when you are not trying to find a path from a specific node to another specific node. You could of course keep enhancing and mutating a BFS algorithm to get something like an anti-object, but I would have to say that on a whole collaborative diffusion using anti-objects are not an enhanced version of breadth-first-search.
icefox
Cadet
 
Posts: 9
Joined: Wed Oct 26, 2011 6:08 pm

Re: Ignoring path finding and using collaborative diffusion

Postby erdman » Thu Nov 03, 2011 5:14 am

Interesting. Got link to games played by collaborative-diffusing anti-objecting antbot?
erdman
Major
 
Posts: 34
Joined: Thu Oct 27, 2011 12:52 am

Re: Ignoring path finding and using collaborative diffusion

Postby icefox » Thu Nov 03, 2011 5:18 am

Narsis wrote:You mention that the runtime is O(rows*cols). how is that faster then the time required for pathing algorithms?


There are many "pathing" algorithms, using A* very much depends on variables, but worst case can be exponential, BFS is O(b*d), etc. Some are better than others. A typical use for "pathing" algorithms is as each node (or ant in this case) needs to decide what to do it and has to calculates from scratch its best path. As the number of ants grows so does the computation time. The the diffusion example after the entire map is diffused there can be 1 ant or 200 ants, and while the cost of the additional ants is not zero it is negligible compared to the single O(b*d) diffusion process and wont be making any exponential calls based upon the size of the map and for example in my demo code only did a lookup in the four surrounding squares per ant.
icefox
Cadet
 
Posts: 9
Joined: Wed Oct 26, 2011 6:08 pm

Re: Ignoring path finding and using collaborative diffusion

Postby icefox » Thu Nov 03, 2011 5:33 am

erdman wrote:Interesting. Got link to games played by collaborative-diffusing anti-objecting antbot?


Ah well I left out the fun part which is the fighting. The games played by the stripped down diffusion code shown on my blog are pretty boring as they only go after food and hills have no idea how to defend/attack and are picked off very quickly by most any of the bots with basic tactic logic. The paper I linked to showed off some collaborative diffusion ideas that can be applied in battles. A nice bit of the diffusion route is that it gives a nice constant cpu time operation for all of the ants that are not in battles, but need to get somewhere leaving you with plenty of cpu time for battle planning. For the battles there are some diffusing advantages you can use as hints, but some localized planning seems to give the best bang for the buck.

At this point in time I just wanted to highlight it as a simple alternative for those who need a path finding solution (Such as the posts about how to make a cache for the shortest path between every node...) and so I didn't show off or discuss any of the attacking code. That can be for another discussion.
icefox
Cadet
 
Posts: 9
Joined: Wed Oct 26, 2011 6:08 pm

Re: Ignoring path finding and using collaborative diffusion

Postby dabino » Thu Nov 03, 2011 8:30 am

Interestingly, I have started with almost the same approach, though I called it Field / Potential. In my model each object(s) "casts" a field on the mao, which potential is a function of pathlength from the object(s). Then ants just go into direction of potential decline. Now I have up to 7 diferent fields, which define such behaviors like food gathering, attack, defence, exploration etc, and I can combine them accoridng to strategic situation.
Unfortunately, this approach is nothing without good tactical algorythm.
dabino
Major
 
Posts: 36
Joined: Thu Sep 09, 2010 9:52 pm

Re: Ignoring path finding and using collaborative diffusion

Postby CrazyMLC » Thu Nov 03, 2011 3:32 pm

Man, gotta love emergent solutions.
This means I can be my usual non-program savvy self and still make smart AI, as long as I model the problem right. The ants do all the work!

Only catch: How efficient is this, as far as turn time is concerned?
CrazyMLC
Cadet
 
Posts: 1
Joined: Thu Nov 03, 2011 3:26 pm

Re: Ignoring path finding and using collaborative diffusion

Postby pedrosorio » Thu Nov 03, 2011 3:35 pm

CrazyMLC wrote:Man, gotta love emergent solutions.
This means I can be my usual non-program savvy self and still make smart AI, as long as I model the problem right. The ants do all the work!

Only catch: How efficient is this, as far as turn time is concerned?


The basic diffusion approach takes less time than doing path-finding.
pedrosorio
Lieutenant-Colonel
 
Posts: 42
Joined: Sun Oct 30, 2011 4:24 pm

Next

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron