Geek asks and answers

Algorithm A * no calculation

I am trying to make the enemy node follow the node player in C # with the A * algorithm. I read the tutorials and downloaded some C # examples. Now I have an A * algorithm. It will follow the player in open space, but will fall into the trap when trying to trace around an object.

So, when my algorithm checks and moves in the direction of the smallest value of F, it may run into a dead end, and at that moment it needs to repeat steps backwards, but this is not possible, because my code says that the previously checked node is closed and cannot be moved and so he is stuck.

How to recalculate a closed node to tell my algorithm that it is normal to go back.

In addition, if I say that my algorithm returns to itself, then that should prevent it from returning to a better node, it has just appeared; effectively returning between two nodes repeatedly.

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

Heuristics that I use.

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

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

F = G + H

Psuedocode

  • Add all adjacent nodes to the Open list.
  • Check all these nodes for the smallest value of F and add that node to the list of best path
  • Add all checked nodes to the closed list (all of them have been checked, do not want to check them again)
  • Repeat until you reach your goal.
  • Move enemy 1 node towards the best path
  • Repeat again and again
+3
source share
4

node, , , ?

, . , ! . A * .

, , node, ; .

. , . , , .

, ...

, .

G - , H - , F - .

-, , . ? , . , . , . .

-, - , ? , , , .

, , . - , , . :

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.

?

+7

, . , . A * .

. .

0

, , SO. , .

Matlab .

G - . G , , . , .

, , , , .. "" , , , .

G , ( G) , 4 .

, A B. T G = 4, H = 2 F = 4 + 2 = 6.

00000
00X00
00X00
00XT0
A0X0B

A * + G = 10, H = 2 F = 12.

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

G .

0

More articles:


All Articles