Title About the Imperial 2 Powder and Margin Algorithm Zhengr (Original) Keyword Empire Times Pathway Path Marcea A *
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, our programmer will not let this situation, usually there are several ways to avoid the way to block the way: 1. Limit the number of selected mobile units in the Empire 2, 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, and may also have other considerations, I can think of controlling Multi-unit attacks the same target may be very low. I don't know if other RTS games have similar restrictions, but if the second, third programs described below are used, this limit is not so important. 2. Putting the roadwork in time. It can be estimated that each "round" (one frame of the game) will be estimated to limit the time for each "round" (just one frame of the game). A turn will then say. This game will not stop, but It is a disadvantage that everyone can see that everyone is not simultaneous, but starts moving. Online article says that in order to avoid selecting the unit "Worn", let players think what problems will be, I can make the way to find the way. Little time decided to "intuition" (usually the straight direction of the target) first, then, then change again, then change it back later. This is also a way, because "intuition" direction is mostly in most In the case of the right direction. But according to I observed that I didn't use this little trick in the empire 2, I will say. 3. This is the most affordable, most effective, the distance similar to the unit. The so-called "similar" In general, people who play the empire 2 within the field of view are limited to all kinds of beautiful formations, and even the leadership of the march, the whole, the premise is to run on the air. ). Even if you deliberately disperse them (can not be too far), while choosing them and takes a destination, they will slowly and close them in the future, and they will be alive. Moreover, no matter where you let them go to the map, they will respond now, and there will be no such pauses that have been said or have started. What is going on? Smart, you can think of it, just let A person is looking for a way, others follow it. Yes! That's going on. Let a unit look for the way, and the rest of the unit, this is much more fast than letting every unit. This is a team. The mobile unit is called "looking forward"
