Hack searching the shortest path in starcraft

One of the leading developers of Warcraft and Starcraft, Patrick Wyatt periodically publishes memories of his work at Blizzard in the 90s. It is very interesting to look at the development of games from the inside, which later became iconic. In the last post, Patrick told a wonderful story about how, in a hurry, I had to hurry to fix the bugs in StarCraft before the release of the game and what came of it.



Developers had to work on tight deadlines. They constantly faced the fact that the release would take place “in two months”, so they had time to fix critical bugs, but there was no time to make fundamental changes and rewrite some of the code to eliminate the cause of these bugs.



The final release of the game was postponed again and again, but the deadline "two months" remained unchanged. This is where the legs grow from those “dirty hacks” that Patrick Wyat tells about.

')

Why did the company set such a deadline? The fact is that at the E3 gaming conference in 1996, the company Ion Storm unexpectedly showed an amazing demo Dominion Storm.







At this time, almost ready for release StarCraft looked like this.







Whatever game you bought, whether you had a choice, Patrick Wyatt asks a rhetorical question. The Blizzard developers were shocked and decided to rewrite the StarCraft graphics engine under the isometric tiles.



The graphics engine was completely redone, and in the deadline, Patrick Wyatt and his colleagues rushed to close bugs. He says they were "thousands." Some could be identified and eliminated by one developer in a couple of hours. Others - like a synchronization bug in multiuser mode - required several developers concentrated work for several days. There was a third category of bugs that are associated with gaps in the development process. For example, the code of the protoss aircraft carrier (Protoss Carrier) at one time was allocated to a separate branch, and could not infuse it back. Thus, this protoss existed separately from the main code, and any changes that were made to all units had to be made separately into it later. Also, any identified bugs in the game had to be corrected separately in the aircraft carrier. As a result, it turned out that he did everything in a special way, standing out among all the units. It would be possible to "kill" this unit, but he was very fond of everyone, so they decided to abandon the aircraft carrier.



Patrick Wyatt says that a particularly large number of bugs arose with the engine's job of finding routes for units (path-finding). If the graphics engine was rewritten for isometric tiles, then the algorithm for finding routes in deadline conditions was decided to take the old one from Warcraft (unlike Diablo, where a full-fledged isometric unit movement engine was built in). It has been optimized for tiles of 32x32 pixels, made up of 16 cells of 8x8 pixels. This scheme was chosen at the time to optimize the graphics for the Super Nintendo console, since there was hardware acceleration for rendering 8x8 tiles.



Since the camera in Warcraft I and II looks from top to bottom, the edges of the graphic objects (forest, buildings, terrain objects) are either horizontal or vertical, and the route search for the units was carried out without problems. Each 32x32 tile was either complete or impassable. In the screenshot, green shows the tile boundaries considered by the algorithm, and red - impassable.







But for StarCraft, the graphics were made isometric, so the game became more visually appealing. For the old route search engine to work on isometric graphics, we had to increase the map resolution: now every 8x8 tile must be passable or impassable. Although the best resolution allowed to put more units on the map, the load for calculating the route increased 16 times!



An additional problem was created by the fact that, due to the diagonal isometric graphics, a lot of borderline situations appeared, when it was not clear whether to mark a tile as passable or not. The screenshot shows how isometric graphics divide tiles into irregularly shaped shapes.







Because of this, a whole bunch of glitches came out. Some were quickly fixed, but others were very annoying. For example, the most unpleasant was a glitch with the appearance of traffic jams during the extraction of resources from working units (SCV terrans, zerg drone, protoss probe). At some point, one of the units stood on the path of the other, he stopped, blocking the path of the third, etc. There was a deaf traffic jam, because of which all the mining stopped. Since the player is usually busy with other tasks (building construction, participation in battles, etc.), he did not notice the problem in time until the entire economy collapsed due to lack of money.



The source of the problem is that the players tried to maximize the number of working units, sending them to the same source of resources. Therefore, units moved along similar routes and could interfere with each other.



Patrick Wyat studied the problem and realized that he was not smart enough to solve it in a fundamental way by changing the algorithm. Units constantly change their coordinates and must, therefore, constantly recalculate the route, depending on the routes of other units (by the way, this task is close to NP-complete tasks). Therefore, he decided that he could not do without a dirty hack - and he completely removed part of the code that was responsible for preventing collisions of working units with other units .



In this way. working units could literally pass through each other, they solved the problem with traffic jams. Development continued, and soon the game was released in production. Although the flaws in the search engine engine made themselves felt. For example, a protoss dragoon has earned a bad reputation in this regard because he, as the largest land unit, more often than others refused to follow the best route.



PS StarCraft was released in May 1998. By the way, the game Dominion Storm came out only a month after StarCraft, and did not meet expectations at all. As it turned out, in those years Ion Storm had a sharp conflict between management and developers. Patrick Wyatt refers to this article and cites "his favorite" quotation as an example, in order to understand how the company communicated: "Also, thank you for writing off your car and house, fucking rat-face with # ka." Obviously, in such a working atmosphere it was difficult to make an outstanding game. And the aforementioned demo at the E3 gaming conference in 1996, as it turned out, was fake. However, Patrick is not offended by the competitors, and even grateful for the fact that they "gave us a good kick in the ass" and forced us to make a game of a qualitatively different level.



On this topic:

Patrick Wyatt, "Creating Warcraft" (translation): the first part , the second part , the third part .