Maze AI

If your agent that is hunting the target has access to the map of the maze, then you need to use a pathfinding algorithm to determine the correct path from the agent to the target. Pathfinding in mazes can be done efficiently using the Distance Transform algorithm. If the agent does not have access to the maze map, then it needs a means by which it can store information about paths it has considered. Essentially, it needs to build its own internal representation of the maze from the areas it has explored. This is the mapping problem commonly faced in robotics. It's far easier to do in a game environment though where you can assume perfect sensors, etc. Before an appropriate solution for your problem can be proposed, we need to know a little more about what your agent knows and what information it has access to.

Cheers,

Timkin

Quote:

Original post by Timkin If your agent that is hunting the target has access to the map of the maze, then you need to use a pathfinding algorithm ...

I don't see this as a requirement or 'need' at all.

The various path-finding algorithms are a powerful tool for sure, but their power can also be a drawback.

In many games a (near) flawless path to the target is perfectly acceptable. It is unfortunate that such (near) flawless path-finding has become the baseline on which almost all games are designed.

It both cripples the game designer as well as the game player when all the game entities know exactly how to get from A to B in the fewest number of steps. There becomes no room for error, simulated or otherwise.

This flaw doesnt stand out in first person shooters because everything is happening in a small area where it is reasonable to suppose that a game entity can see how to get around an obstacle.

But take a maze situation and it becomes unrealistic. The maze game designer who is limited to only path finding algorithms is going to be quite frustrated trying to dumb down his game entities (how exactly do you dumb down the perfect path??) As well the game player could easily be frustrated by the magical abilities of his opponents who not only find him, but also take the fewest number of steps to do so.

Quote:

Original post by ksintath -if a road does not have any exit,i do not want to enter there again. -For example the target is in the right but there is a wall in the right and the true way is in the left.My functions always crash the wall go back and try again to go to right:):):) how can i fix it?

You can take a lesson or two from ants, who drop pheromones wherever they go.

Suppose your hunter dropped a little packet of information wherever it goes - one value is fine.

This single value is, for all intents and purposes, all he ever need to completely explore any maze, map, or world. The value is simply the number of steps he has taken so far.

On his first step he drops a 1, on his second step he drops a 2, and so forth. Places he has never been are initialized to a step count of 0, meaning no pheromone dropped yet.

This trail of values isnt going to give you flawless path-finding, but it will give you rational maze-exploration.

So Mr Hunter finds himself at some arbitrary location. Around him are these step-counters (or time-stamps, if you prefer) telling him when he was last at the locations that surround him.

If he simply chooses to always go towards the lowest step-counts, he will eventualy visit every place in the maze. This is an important property to have as it means, given this simple movement rule, he will not get 'stuck' nor will he find some reachable place unreachable.

Extending the movement rule.. when he is in an unexplored area, multiple directions can have no step-count at all. The direction he takes can be randomly chosen from the set of unexplored directions, or he can use some heuristic such as always taking the unexplored direction that is closest to the prey (divine guidance?)

Extending the rule still further, when the prey is in the hunters line-of-sight he can ignore the pheromones and simply start rushing the prey.

This sort of movement strategy doesnt completely eliminate your chief complaint, which is that your hunter goes down a dead-end multiple times. But it does limit the number of times he will go down a dead-end before exploring the entire map at least once..

It is very easy to impliment on grid-based and node-based mazes, while a bit more difficult on mazes constructed from polygon soup (such as ones created in a 3D polygon modeler)

Is is also extremely efficient..

Quote:

Original post by Rockoon1 I don't see this as a requirement or 'need' at all. The various path-finding algorithms are a powerful tool for sure, but their power can also be a drawback. In many games a (near) flawless path to the target is perfectly acceptable.

... and you've assumed that by path-finding, I meant 'globally optimal' path... your mistake, not mine. Path-finding is merely the task of determing operators to affect movement, given goals. There are a wealth of algorithms and varied methodologies (local vs global, approximate vs exact).

As to your comments about 'flawless path-finding crippling designers and players'... I think that's a little narrow in perspective. Having perfect information about how to act is a good starting point for 'dumbing down' the abilities of agents in simplified virtual worlds. Certainly, for beginners (which the OP appears to be), it's an appropriate first approach from which more realistic behaviours can be generated. As to how to "dumb-down" a perfect path, that's a trivial exercise, particularly if you performed a search on a graph/tree to find the path.

Cheers,

Timkin

First thank you guys i read your helps and which became very useful.Now there is another problem.My target can move and my robot can hear it.In the situation below my robot can do nothing to find the correct way.Think 'R' as robot 'X ' as walls and 'T' as target:

and target goes down and up and down and ......How can my robot understand that it is a trick and find the correct way?

From your example I presume that your robot is trying to move to the source of the sound. If that's not the case, please elaborate on what the pathfinding goal is. If you're using a local solution for pathfinding (for example steering behaviours, gradient methods, potential field methods, local search, etc) then your agent has found a local minima of its utility function (even if not explicity represented as such) and it won't leave its present state unless you give it a reason to (by identifying a state with better utility). The only way to avoid this scenario is to perform search over a broader horizon.

Timkin