When it comes to the way in the game, many people will think of a * algorithm. Indeed, A * is undoubtedly the most advanced algorithm, in a simple map, it is very fast, can quickly find the shortest The path (exactly said time cost minimum path), and use a * algorithm to easily control search size to prevent program blockage. About A * algorithm has a lot of articles, Google can find, but domestic netizen Original doesn't seem a lot, it is recommended to find relevant information on foreign websites, such as http://www-cs-students.stanford.edu/~Amitp/gameprog.html. A * Algorithm itself expressed Very simple, the program is not difficult, two or three hundred lines are easy to get. The key is to optimize the upper and lower efforts in the code, this is very testing the programmer's algorithm. Basic ideas generally use space (not memory) Occupy) Change time (search speed), there are also some map pretreatment (including artificial preprocessing and program pretreatment) such as multi-level map accuracy or map partition domain search, but I have to discuss today is not A * algorithm itself, is interested in this area can be exchanged with me. No matter how it is optimized, the way to find a very time-time work, and the amount of work and map is basically linear (not restricting the search scale) Premise). The current RTS often allows each of more than 200 mobile units per side, and there may be a large number of moving objects need to be learned. If you select 100 unit points and get a remote march command to them, assume each time 5ms needed to find a road (on the complex map, this value is not exaggerated, I said on my machine), then I need 0.5 seconds of time on the way, that is, the whole game will stop 0.5 seconds. You What is it? Oh, the programmer will not let this situation, usually there are several ways to avoid the way to block the way:
1. Limit the number of Empire 2, which is selected simultaneously, this limit is 40. Of course, the number of people in the same form cannot exceed 40. This aspect is to reduce the way to find a way. At the same time, there may be other considerations, I can think of whether too many units attack the same goal is very efficient. I don't know if other RTS games have similar restrictions, but if they use the second below. , This limit is not so important.
2. Putting the way out in time. It can be estimated that each "round" is limited to each "round" (one frame of the game), other waiting for the next one. Round again. This game will not stop, but the disadvantage may see that everyone is not the same simultaneously, but starts to move. Online article says that in order to avoid selecting the unit "Laun", let the player think something It can make the unit that will not be asked for a long time, and the time is "intuition" to determine a direction (usually the straight direction of the target) first, then let go, then change it, then change it. This is also a way Because the direction of "intuition" is the right direction in most cases. But according to I observed that I didn't use this little trick in the empire 2, it will be said.
3. This is the most affordable, which is a common path of the unit. The so-called "similar" generally playing all kinds of beautiful arrays, including each other, and limited to the imperial 2. When the leadership, the whole quadruple array (of course, the premise is to run on the air). Even if you deliberately dispersed them (can't be too far), choose them and take a destination They will also slowly and automatically close them in the future, and they will be arranged in a square. Moreover, no matter where you let them go, they will respond to the map, but will not appear. That kind of pause or start, what is going on? Smart, you can think of it, just let a person bring a team to find the way, others follow it. Yes! That's going to find the road and the rest The unit follows, this is much more fast than letting each unit look for a single way. This team's mobile unit called "Looking Forwarders" to say that it is necessary to mention a bug that the empire 2 does not know. For example, there is a very long stream, you have a bunch of people, part of the left side of the river, the other is in the right side, they are very close, although they are separated from the river. Now you have chosen, such as letting them Go to the left of the river. Because they can see each other, then the procedures choose a person with a way (how to choose, I don't query). There may be two situations at this time: one is the way to find the road on the river, so he With the destination of the brothers on the left side of the river, a man in the river really wants to follow (according to the program settings, they don't need to find the way, but no choice but to go, I have been in the river. ( Empire 2's algorithm According to I observe that in the case of the original route, I will try to bypass both sides. Of course, the range of the winding is limited. If I find that I can't re-seek roads, when I can't go back to the road, when the horse on the shore goes out of them When they thought of them, they could find their own way, so they went around the river. The other situation is more funny, that is, the system selected for the river in the river. The people on the left of the river are very far away Near, but they don't care, they have to follow the road to find the road over the river until the end of the river is in the event of the troops in the river, they will be rowed together to go to the destination. About the empire 2 The determination of the road to the road is to take the lead in a team of people, I haven't had a short-minded. In addition, when the road is dying (pressing the DEL key, huh), or specified another destination In the rest of the unit, it will reach a ride soldier, re-search. Weird, the movement of the farmers in the Empire 2 did not use the way to find a routine strategy, even if they were very close to each other, they also moved Will not be arranged in a square, and a moment of selecting the target will appear on the pauses described above, that is, some farmers start, and have started. On my CII533 machine, 40 farmers , Huge blank map From one head to another, the fastest start-up farmer and the slowest phase difference of 0.5 seconds, the delay is already very obvious. I don't quite understand why it is designed, it may be the particularity of farmers' behavior.
In addition, the empire 2 is to explain that it does not have the same party "let the road" algorithm in the red police, if you let a few people block a throat, then control another team tried to pass this gate, you can see When looking for the way, the algorithm does not consider blocking the gateway, because the people you control will come over, just like thinking it is the same (this is reasonable because they don't know when they don't know when the road is Will leave), when you look at it, you will look around it around the left. If you don't get around the past, you will look back to find another road. The people who have a road will have an indifferent. The current RTS is developing to network development, the more In the case where the mobile unit is increasing, on the one hand, the efficiency and cleverness of the path search algorithm itself, the efficiency and cleverness of the military algorithm (such as formation, road, etc.) is also a matter of great research. Oh, I have written so much. I have time to study the way of searching for other games. If there is a good person to communicate with me. If you want to reprint this article, please indicate it. Thank you! Cooker03_05_16
