It will be said to a *. In fact, I am not very familiar with A *, I have seen in a game production reference book. The author puts forward some attention to using A *: Do not use C-type maps.
I used to observe the people in "Star" to find a diameter, I feel very unreasonable. Whether it is a C-type or a noodle type, it can make the correct response immediately.
If the map can be seen as a data structure, the point / line is composed, then the following concept (I call it "path analysis":
1, hanging: the path of the tree structure, its root is connected to a "region";
2, the area: After the drafting is eliminated, the sub-map independent by "Bridge" is defined as a region;
3, bridge: The bridge in the figure in the data structure, but excludes the hanging;
4, Generalized Area (Connecting Component): Collection of paths that can be reached, including regional, hanging. The bridge is just an abstract concept, a road sign;
5, whole picture: consisting of a single / multiple generalized zone. Two generalized areas are unreachable;
// Region / hose is the location where the characters may exist, that is, the area / hose constitutes a whole map, bridge, etc., just an abstract coordinate range.
Once the above information can be sorted, the map findings will become very simple. Usually, a very complex graphic, "path analysis" will become very simple. Look at the following ordinary map, path analysis after the path analysis:
(White in the figure means a feasible area, XX color means not feasible, red line indicates path distribution)
This is a simplified map of the actual "Star" map. After analysis, the entire picture includes 1 broad area; the general district includes 1 area, 0 bridges; the area includes 1 branch; the branch is a tree having a depth of 1!
The characters are usually in a certain area / branch (in this picture, it can only be branch), and the diameters between any two locations are in the same branch, and they can be used directly with the tree.
In addition: See here: If the information after the path analysis is much enough, such as the node number of the branch (tree), the hierarchy, the same branch (tree), the direct comparison level and the node number can be immediately take the first step! ! The CPU reaction cycle should be within 50! ! !
In fact, after the "path analysis", in addition to the findings in the area, the other is a tree find path, which is very simple. For half of the map, you can build a fixed route in the region, so that all findings will be very fast! ! !
If the two locations are not arrived, there is information that they are located within a different "general sense area / communication branch";
Disadvantages:
1. Due to the analysis of the drawing, the simplification of the figure is too fire, resulting in sometimes distortion. If you add distortion processing, programming will be more complicated, but efficiency will not affect too much;
2, the algorithm is mainly the reduction of "branch", using tree findings to accelerate map findings. Therefore, there is too much efficiency of too much loop; I analyzed that the map is 255 * 255 star map, and there may be a loop of about 30 * 30 = 900. If the fixed route is established, 900 * 900 = 810 000 approximately 1m unit; (but we can do not use fixed routing, such as A *, don't forget it?) About the algorithm "Path Analysis": This algorithm spent some time, after calculation, it needs to be adjusted It is not difficult, but I don't know if it should be public. . . .
----------- 2003.6.20 New Algorithm Introduction ----------
First, rectangular analysis (recommended to use paper / pen practice)
1. Any map model must be converted to a matrix, such as Int Map [256] [256]. And Map [I] [J] represents the possible map type of the coordinate, such as: flat, edge, highlands, pool, etc. And, (i, j) to (i, j 1) is feasible to determine whether or not MAP [i] [j] is equal to MAP [I] [J 1];
2. For each feasible unit (2 for loops), if the change unit is not calculated, then:
2.1, with this unit of the upper left corner, long / width = 1, establish a rectangle;
2.2, expand the rectangle to the right / down, so that the four vertices are at least one "obstacle" phase (key);
2.3, try to expand 2, select the width or high priority; (secondary)
3. Repeat 2 until all the map units are calculated, all viable units should belong to 1 rectangle; all rectangles are saved, including location information (can establish a rectangle for non-feasible units, but no necessary)
Second, path / door
Brief description: All rectangles are filled with the entire map and these rectangles are not superimposed. "Rectangular Algorithm" enables neighbors of rectangles only possible on a single side. And, any 2 rectangles may only have a 1 segment adjacent side, which is called "door", which is the way to rectangular to the rectangular routing!
Most importantly, due to the four top points of the rectangle must be adjacent to obstacles, it is impossible to appear three rectangles adjacent to 1 unit!
1. Analyze all the doors: For each rectangle, scan it four sides, if there is a trace of other rectangles (check the rectangular number to which the unit belongs), the door is identified (the algorithm is not difficult);
2. All rectangular center points to each door and draw a line. Since the door is copied by 2 rectangles, the line will also connect all rectangles, all paths. In fact, it looks like the graphic given above!
3, there is also a number of new concepts, such as a plurality of rectangles to connect to 1 strip, they can merge into a "road". For any two points, if it belongs to 1 rectangle, the straight line can wait. . .
------------ The end. ----------
There is actually a number of adjustments, such as "deviation" "deviation", which is preferred according to the width, requires cutting / merge to reduce the error. . .
There are too many loops, and the circumference is small, and the loop can be analyzed with the far near the "door", and it is ignored under certain error rates. . . If you have time, use the program to implement it, you will find it very fun :)
