reset password
Author Message
nhthanh87
Posts: 13
Posted 12:36 May 01, 2012 |

How can I prevent my ants from moving backward? Should I mark cells as "visited"? Thanks.

mrighetti
Posts: 20
Posted 17:06 May 01, 2012 |

You would have to first determine how would you define "backwards" .  Many implementations don't remember specific ant path info from turn to turn, calculating the best path each time.

Do you want to ensure your ants keep expanding their territory?  I've had the most luck with that by making unseen tiles more desirable to visit as the turns increase.

rabbott
Posts: 1649
Posted 17:12 May 01, 2012 |

You might explain how your algorithm for controlling your ants works.  Then it might be easier to suggest some changes.

nhthanh87
Posts: 13
Posted 17:30 May 01, 2012 |

Yes, i want to expand my ants' territory (going far away from my hill as possible). I've use BFS to explore unseen tile within 10 steps. If an ant can't see an unseen tile within 10 steps, I let him search for visible edges using BFS again. Since we have random walk, there will be a case that an ant will return to "visited" visible edges. In worst case, it can return to the hill. How can I avoid that?

mrighetti
Posts: 20
Posted 17:51 May 01, 2012 |

Can you explain what you mean by "visited" visible edge?  Are you keeping track of what you have explored each turn?

nhthanh87
Posts: 13
Posted 17:59 May 01, 2012 |

I'm trying to do that. In that case, we can know what we have visited from previous turns. And we don't go back to visited visible edges.

rabbott
Posts: 1649
Posted 21:33 May 01, 2012 |

It's possible for an ant to move in one direction and then to move back in the other because a cell it saw before is no longer visible. It depends on how you determine priorities. 

One way is to keep track of when each cell was last seen.  A cell's lastSeen value is the turn when it was last seen. Then move with highest priority toward cells with the smallest lastSeen values, i.e., that were last seen most turns ago.  For cells that were never seen, assign a lastSeen value of -1.

nhthanh87
Posts: 13
Posted 23:58 May 01, 2012 |

So I need a list/set to keep track of all cells' lastSeen values. However, should each ant have separate list of cells' lastSeen values? or they can use the same list?

rabbott
Posts: 1649
Posted 09:36 May 02, 2012 |

It's up to you to write the code.

abess
Posts: 26
Posted 21:11 May 04, 2012 |

Couldn't you js give preference for an ant to move towards a path that is away from the known location of the anthill, unless there's a wall in its path? And keep that preference until they're a certain amount of squares from the anthill?