3

I am trying to make an enemy node follow the player node in C# with A* algorithm. I have read the tutorials and downloaded some C# exmaples. I have got my A* algorithm working to a degree now. It will follow the player in an open space but hits a snag when trying to trace around an object.

So when my algorithm is checking and moving in a direction of lowest F value, it might come across a dead end, and at this point it needs to retrace its steps backwards, but it can't because my code tells it that a previously checked node is closed and can't be moved to, and therefore it gets stuck.

How do I recalculate a closed node to tell my algorithm that it is ok to go back that way.

Also, if I do tell my algorithm to go back on its self, what is to stop it from going back AGAIN to the better node it just came from; effectively going back between two nodes repeatedly.

I see that it should be able to check a node in the closed list and determine if it is better on this particular path, but I'm not sure how that is done.

The heuristics I'm using.

G = Math.Abs(StartNodeX - TargetNodeX) + Math.Abs(StartNodeY - TargetNodeY)

H = Math.Abs(CurrentNodeX - TargetNodeX) + Math.Abs(CurrentNodeY - CurrentNodeY)

F = G + H

Psuedocode.

  1. Add all adjacent nodes to the Open List
  2. Check all those nodes for lowest F score and add that node to the Best Path List
  3. Add all checked nodes to the Closed List (they've all been checked, don't want to check them again)
  4. Repeat until target is reached
  5. Move enemy 1 node in the direction of the best path
  6. Repeat all over again
Improve this question
1

4 Answers 4

Reset to default
7

How do I recalculate a closed node to tell my algorithm that it is ok to go back that way?

You don't because it's not OK. The optimal path never includes walking into a dead end and then walking back out again! That is by definition the suboptimal path. The A* algorithm finds the optimal path.

if I do tell my algorithm to go back on its self, what is to stop it from going back AGAIN to the better node it just came from; effectively going back between two nodes repeatedly.

Nothing stops that. That's why it is a bad idea to do what you are describing. If it hurts when you do that then do not do it.

The heuristics I'm using....

Seem pretty messed up.

You have G being the Manhattan distance from the start to the goal, H being the Manhattan distance from the current point to the goal, and F being their sum.

First off, the Manhattan distance is only a valid metric if the heuristic is for a square grid with no diagonal movement allowed. Do you allow diagonal movement? If you do, then this heuristic is wrong. Remember, the heuristic is required to underestimate the cost. If you can anywhere move diagonally then the manhattan distance overestimates the cost. Consider instead using the Euclidean metric.

Second, the distance from the start to the goal is a constant, so how is it relevant and why are you adding it to anything? It looks like what you are saying is that the cost of every path is increased by the distance from the start to the goal, which doesn't make any sense.

Based on your questions I think you do not understand the algorithm and why it works. My advice is to understand how the algorithm works before you attempt to implement it. Here is the algorithm in English:

The closed set is an empty set of points.
The queue is an empty queue of paths, ordered by path cost.
Enqueue a path from the start to the start with zero cost.
START: 
If the queue is empty, then there is no solution.
The current path is the cheapest path in the queue.
Remove that path from the queue.
If the last step on the current path is closed then 
    the current path is necessarily bad. (Do you see why?)
    Discard it and go back to the START of the loop.
Otherwise, if the last step on the current path is the destination then
    the current path is the optimal path to the destination, so we're done.
Otherwise, we have the cheapest path *to the last 
    point in that path*. (Do you see why?) 
Therefore, every other path that could possibly go through that point is worse.
Therefore, close off that point. Add it to the closed set so that we can 
    automatically discard any future path that goes through that point.
For each possible direction from the last point of the current path,
    make a new path that extends the current path in that direction.
    The estimated cost of that new path is the known cost to get 
    to its end from the start, plus the estimated cost to get from
    its end to the destination.
    Enqueue the new path with that cost.
Go back to the START of the loop.

Does that make sense?

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

My algorithm can only move up, down, left and right. So the manhatten distance should be ok. If the target and goal are only 2 nodes away from each other, but there is an object in the way that spans multiple nodes, how can it move around the object when it needs to move farther away from the goal in order to navigate the object?
@user1359819: It moves around the object by finding the cheapest path. If the cheapest path turns out to involve going backwards for a while to get around an object, the algorithm will find it eventually when it exhausts the paths that look like they ought to be cheap but in fact require backtracking. Those will be discarded.
@user1359819: My advice is to create a small situation and then actually on paper follow the instructions of the English version of the algorithm. Remember that the queue is a queue of paths. Also, when you do that, simply use "always zero" as the heuristic. That gives you Dijkstra's Algorithm, which is a simpler version of A* that is not quite as fast but does the same job.
Ok, that helps a lot thanks. I'll read up on it more. I think I'm not testing multiple paths, but actually just testing one and getting stuck on that without considering others.
@user1359819: Good idea. Remember that the cost of a path is the known cost of the entire path so far, including all of its twists and turns, plus the estimated cost of the distance from the end of the current path to the goal.
1

So if I understand your question correctly this is a case of something the base A* algorithm is not suited for. A* tells you given this world give me the shortest path from A to B. I assume things are changing in this world. A* does not handle dynamic worlds and so the only solution if you want to use A* is to re-run A* every time from scratch. Reset your queues etc.

Now there are some better solutions to this which I will let you explore further. I've linked a paper and some slides which show you one solution I worked on for these cases. You will find references to a lot of other algorithms in the paper as well.

http://www.cs.unh.edu/~ruml/papers/rtds-socs10.pdf

http://www.cs.unh.edu/~ruml/papers/rtds-socs10-talk.pdf

Improve this answer

3 Comments

I do re-run my A* algorithm from scratch every second, and the enemy moves each second if it has found the target. The lists are all initiated each time the A* runs, so they start empty each time and it tries to find the target each time it runs.
Ok, if that's the case the closed list should be reset each time you move. That should prevent you from getting blocked into a dead end. Are you resetting your closed node list?
Yes I do reset my closed list. Effectively, the algorithm searches for a best path, then it moves the enemy 1 node (the first best path node on the list) and then repeats. But the problem still arises as it gets stuck when trying to go back on its self during the search algorithm if it finds a dead end and has to move back over a previously closed node.
0

From wikipedia you can see that your heuristic function needs to be admissible. The admissible heuristic must never give a higher estimate than the true distance. Otherwise A* search will not work.

Your heuristic is not admissible. You should find a different heuristic.

Improve this answer

3 Comments

In-admissible heuristics will still return a solution, just not always an optimal one. So this is not the problem
It is,for instance weighted A* makes a heuristic in-admissible but in doing some it speeds up a search. You might take a terrible path but it takes lets say 10% of the time to compute that path. en.wikipedia.org/wiki/A*_search_algorithm#Admissibility_and_optimality
Right, I misread your comment. Yes A* will not return the shortest distance if an in-admissible heuristic is used. I do not know if in fact a broken heuristic will return a result.
0

I'm running around trying to close out old problems here on SO. I hope it still helps this late.

I tackled a similar problem in matlab a couple of months ago.

G is your problem. G tells you what the difficulty is to move from your starting location along a path, it is not a heuristic. It is knowable and you don't need to estimate it.

In your case of only moving in one of 4 directions, and under the assumption that it is just as easy to move left, right, up , or down i.e. you don't have "swamp" like areas that are harder to move through than other areas, you just need to count the number of squares along the path from where you came from.

Your G works in the open because the Manhattan distance (your G metric) is the shortest path in an unobstructed chase where you can only move in the 4 cardinal directions.

consider the following example where you are trying to go from A to B. The location T would according to your equation be G = 4, H = 2 & F = 4+2 = 6.

00000
00X00
00X00
00XT0
A0X0B

A real A* path would be represented by + with G=10, H=2 and F=12.

0+++0
0+X+0
0+X+0
0+XT0
A+X0B

calculating G this way should solve the problem.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.