A specific PathFinding approach

Question

I am working on Unity, using C# for a project that should be quite simple. I am stuck to pathFinding .

I have Looked at Dikjstra's and A* for reference, but for some reason I still can't adopt them to work in my case. I guess my brain :=while(1);

Here is the Idea:

From a textfile I import a "map" where each "*" means Wall, and each " " walkarea. In the map there area randomly placed 2 objects: a bomb and an agent.

The agent must investigate the map (which forms a maze) and discover the bomb. The agent may move to his 8 neighbour tiles if they are NOT Wall. In my code , the agent class hold his own map. for every tile that he visits, he asks the "world map" for info, about his 8 neighbour tiles.

On his own map then he takes a note of the known tiles type(wall / walkpath) , and if it is a walkpath, he also notes, how many times he has visited it. The agent also has a "Prefered direction " list. This tells which tile to choose next to move to, if more than 1 have not been visited.

Up to this point, I have set it up all good and running, and if I let it run, he eventually finds the bomb. The Issue is that because he only runs on a Prefered direction according to the least visited tile , he has to re-visit some tiles too many times like a moron. So what

I must do is this:

If the agent reaches a tile for which, every nighbour is either wall or already visited, then he should investigate his own map, and the notes from the past to find an unvisited tile , and walk to there. Every walk direction has the same weight/cost, so we don't need to consider cost of path.

In my opinion, Dijkstra's is the closest to apply , but I still can't get it right .

Any Ideas or help would be much appreciated.

Thank You

Alex

All heuristic search algorithms use some sort of open/closed list strategy, where initially, the current agent's position is in the open list. When a node is evaluated (that means: all it's neighbours are considered and maybe put in the open list) the node itself is put in the closed list. Nodes in the closed list should never be evaluated again. If the intend is to do agent-based search iteratively every frame, WHILE the agent is moving, then you have to 'version' the open/closed nodes based on an always increasing 'request id' of the search. — StarShine

jhyatt jhyatt · Accepted Answer · 2014-02-18T17:58:47

Part of the issue is how much information you want to allow your agent. If you're willing to let him know where the target is, or at least its general direction in relation to himself, then you can use that to help influence the agent's decisions. This would allow you him to always favor moving in the direction that gets him closest to the goal while taking the least visited path.

Otherwise I'd keep track of each place he visited in a separate map, as well as the 8 neighboring tiles since he has "seen" them, with something like -1 indicating a wall that has been seen, -2 indicating an unseen location, and 0 indicating seen but unvisited. I'd then use A* or a variant on it that would move him to the closest unvisited point based on number of tiles traversed, breaking ties randomly. This would lead to a more trial and error rat in a maze approach.

A specific PathFinding approach

1 Answers