Recently, a lot of friends asked me about a * algorithm, the purpose is to write a program for searching for the shortest path. This is in the game of the mouse Controlling Elf Sports (not less than the wisdom RPG with the mouse as the keyboard direction " A large number of uses, especially instant strategy. But I personally think that the A * algorithm is only suitable for processing static paths, when a large number of objects in the instant strategic game, it is difficult to implement (nor not achievable, this requires one Pretty good valuation function and cannot search the path once)
I am strange that A * algorithm should be the basics of the algorithm class. Anyone who has learned algorithms should know. I shouldn't write here. Everyone will flush the book of computer algorithms. It should be seen. (Lecting AI's book is less less than) Since many friends ask, in various discussion groups, the BBS and other places have repeatedly mentioned that the special flowers have completed this article and included programs in the afternoon, satisfaction Our major amateur game creation enthusiasts, professionals are free to see, so as not to avoid the door ax ^ _ ^ But if there is a mistake, you must point out.
If your Internet time is very valuable, please download the source code (3K) offline research I have noted.
Before introducing the A * algorithm, first mention a broad priority search, and the breadth priority search is to expand each time the policy of possible development, such as one map, the object is allowed to move in the four directions, then, it will place the location Step of the object to each other, save the four states in memory, and then move again from the four starting points to the respective four directions ... (of course, it can remove unreasonable mobile methods, such as Not allowed to move back) In fact, the entire search seems to be unfolded outward until it reaches the destination, it is clear that it can find the optimal solution, but the number of nodes is increasing, true In the game, the player will complain that the memory 128m is not enough to use ^ _ ^ and the increase in the number of nodes to be processed, the processing speed will slow down ... can be said that this algorithm is not practical.
The A * algorithm is actually a heuristic search. The so-called heuristic search is to use an appraisal function to evaluate the value of each decision, decide which solution is tried first. This can greatly optimize the common range of priorities. In general, from the shortest distance from the starting point (a) to the destination (B) is fixed, we can write a function Judge () estimate the shortest distance of A to B, if the program has tried from the starting point (a) Holding a route to the C point, then we believe that the estimated distance between the AB of this program is A to C actually walking the distance H plus the distance from c to b with judge (). So, no matter us Which step is to be found, it will calculate an evaluation value. After each decision, you will sort the evaluation value and wait-in-law, and then pick the most likely part of the minimum route from the various schemes to be processed. To the next step, it is always looping to the object to move to the destination, or all the scenarios have not found a path to the destination. (Usually set the timeout control code in the game, when the memory consumption is too large Or exit the search for too long
After? No. How to write this algorithm is very important, how to ensure that the shortest path can you find? Afrigent condition is that the distance between your valuation function calculates must be less than or equal to the actual distance. This can be Mathematical strict proves, interested you can consult your own information. If your valuation function does not satisfy this, you can only call a A algorithm, and it is not possible to ensure that the final result is optimal, but it may be very fast. And in the game, we don't necessarily have to get the best solution. But undoubtedly, in the A * algorithm of that condition, the closer the value of the estimated value, the better the value of the real value, the procedure given below, I only Using a fairly simple valuation function: seeking two points, if you have a shortest path in the absence of an obstacle. If you want to write a fast search algorithm, please find a good valuation function, have time , I will narrate on this ;-)
I have taken time to get annotated, and debug passes. If you think after thinking, you can come to E-mail to CloudWu@263.net ;-)
The program runs in addition to the data file map.dat that describes the map.
80,24
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 舰
O Oo O
O S Ooooooooooooo O
O O O
OOOOOOOOOOO o O O
O O Oo OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO o
O Ooooo O Ooo O O O O O O O O O O O
o O Ooo OOO O
o oooo oooo o
Oo OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO /
O O O O O O
O O O O O O
O O O O O O
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO /
o O Oooooooooooooo
o O Oooooo OOOOOOOOOOO
O O O O O
O Oo OOOOOOOOOOOOOOOOO O O O O O O O O
o OE OO O O O
O Ooooo O O O O O O O O O O O O O O O O O O O O O O O O O
O O O O
o o o o oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
