# Algorithm for exploring/filling grid map

I'm working on a small game that takes place on a grid map. I'd like to write an AI that is able to explore the grid map by filling as much of its available space as possible.

From any given position there are four possible moves (north, south, east, west), but some of these may be blocked by walls. Also, once I visited a cell I don't want to visit it again. What's more, I want to avoid getting stuck: if moving in one direction means I'm going in a dead end, I'd rather not fill out that part of the grid.

-

A flood fill algorithm might be what you are looking for:

http://en.wikipedia.org/wiki/Flood_fill

This particular algorithm could provide your AI with a "map" of coordinates it would be allowed to travel to. Given the proper instructions, your customized flood fill algorithm would fill based on the rules of your gameboard.

If you are looking for a smarter pathfinding solution, you will be more interested in a A* algorigthm.

http://en.wikipedia.org/wiki/A*_search_algorithm

-
And if you want to use something as simple as flood fill, but want to avoid dead ends, then maybe use some heuristic that prevents you from ever entering "narrow" areas (the definition of which is up to you). This will at least catch some cases, if not all, and may be good enough for the OP. – Arcane Engineer May 12 '13 at 13:55

You can't "avoid" dead ends. Without looking forward, you'll not know its a dead end... I guess you just don't want your exploring vehicle / person / whatever to stop when a dead end is reached, right? So, I suppose that the "avoid dead ends" rule is meant as "if possible".

I assume you want to develop some kind of strategy game, where one needs to first send some troops to "unknown" areas to know what kind of resources are there etc. And your question is about how to naturally explore this unknown area quickly.

About 15 years ago invented some algorithm that's based on animal behavior. I jokey called it the "Algorithm of the 'shitting' hamster". The name just explains the algorithm quite easily: Imagine a hamster would explore your maze and on every field on the map it moves to, it shits. And well, now it stinks there! The hamster of course doesn't like that and always moves next field it can reach that stinks the least. This ways it will explore the map quite quickly. To give you a better understanding: At each map position it will first move in one of the directions where it did not come from (as it stinks most from there). When it reaches the map field a second time it will take one of the other two directions first. And when it visits the field quite often, it will even go back the way it initially came from. Which means that it will leave the dead ends.

It will even work very well with multiple "hamsters". Or better: imagine it were ants... They will spread into different direction themselves. For the implementation you only need a counter for each field on the map, which counts the number of "visits" (the same counter is used for the entire group).

You can even extend this algorithm to let them find the quickest way back home, by letting each "ant" (or "hamster") count up a "step counter" for each step since it left it's start position. On each map field you store the minimum "step counter" values as following: Initialize the map-values with "maximum". While exploring: If you reach a new map field check if your "step counter" is lower than the stored value on the map, if so ... store your value there. To find a short way home: look for the lowest "step counter" value of the neighboring fields and following the path...

There are lots of ways to extend this to fit special tasks. For example: I adapted this kind of algorithms in the early 90s to simulate some kind of anthill, where ants were exploring a random map that contained some sugar. In the simulation the ants explored the map, until they found sugar and brought it to the anthill (fastest way back home). They also directed the other ants to the sugar they found (by placing some markers on the map that burred out, as soon others were following the path). Eventually, the sugar at one position was depleting and the ants were automatically stopping to follow the "markers" (as they blurred out) and were looking for new resources. So, the basic algorithm has been really practically tested... You just need to be a bit creative to adapt this to your problem.

Okay... I hope you got the key idea and that it hopefully helps you.

Stefan

PS: Let me know if you need more detailed explanations...

-