StarCraft Shortest Path Hack

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 from the inside at the process of developing games that later became cult. In the last post, Patrick told a wonderful story about how in a hurry he had to fix bugs in StarCraft before the release of the game and what came of it.

Developers had to work in a tight deadline. They constantly faced the fact that the release would take place “in two months”, so that they had time to fix critical bugs, but did not have time to make fundamental changes and rewrite part of the code to eliminate the cause of these bugs.

The final release of the game was postponed again and again, but the “two months” deadline remained unchanged. Hence the feet of those “dirty hacks” that Patrick Wyatt talks about.

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



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



Whatever game you buy, if you have a choice, Patrick Wyatt asks a rhetorical question. Blizzard developers stepped back from the shock and decided to rewrite the StarCraft graphics engine for isometric tiles.

The graphics engine was completely redone, and in the conditions of the deadline, Patrick Wyatt and his colleagues rushed to close the bugs. He says there were “thousands” of them. Some could be identified and eliminated by one developer in a couple of hours. Others - like a synchronization bug in multi-user mode - required the concentrated work of several developers over several days. There was a third category of bugs that are associated with gaps in the development process. For example, the Protoss Carrier code (Protoss Carrier) at one time was allocated in a separate branch, and could not pour it back. Thus, this protoss existed separately from the main code, and any changes that were made to all units, then had to be separately made to it. Also, any identified bugs in the game had to be separately fixed in the aircraft carrier. In the end, 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 leave the aircraft carrier.

Patrick Wyatt says that a particularly large number of bugs arose with the work of the engine for finding routes for units (path-finding). If the graphics engine was rewritten for isometric tiles, then the algorithm for finding routes in the deadline decided to take the old one from Warcraft (unlike Diablo, where they built a full-fledged isometric engine for moving units). It was optimized for tiles 32x32 pixels, composed of 16 cells of 8x8 pixels. This scheme was chosen in due time in order to optimize the graphics for the Super Nintendo prefix, since there was hardware acceleration for rendering 8x8 tiles.

Since the camera in Warcraft I and II looks down, the edges of graphic objects (forest, buildings, terrain objects) have either horizontal or vertical position, and finding the route for the units was carried out without problems. Each 32x32 tile was either complete or impassable. The screenshot shows the tile boundaries considered by the algorithm in green and impassable in red.



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

An additional problem was created because of the diagonal isometric graphics there were a lot of border situations when it was not clear whether to mark the tile passable or not. The screenshot shows how isometric graphics divides tiles into irregular shapes.



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

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

Patrick Wyatt studied the problem and realized that he did not have the mind to solve it in a fundamental way by changing the algorithm. Units constantly change their coordinates and, therefore, must 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 this could not do without a dirty hack - and he completely deleted the part of the code that was responsible for preventing collisions between working units and other units .

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

PS StarCraft was released in May 1998. By the way, the Dominion Storm game was released only a month after StarCraft, and generally did not live up to expectations. As it turned out, in Ion Storm in those years, an acute conflict erupted between management and developers. Patrick Wyatt refers to this articleand as an example he cites “his favorite” quote to understand how they communicated in the company: “Thanks again for the fact that we wrote off your car and your house, you fucking rat-haired c # 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 is even grateful to them for “giving us a good kick in the ass” and forcing us to make the game of a qualitatively different level.

Related:
Patrick Wyatt, "Creation of Warcraft» (translation): the first part , the second part , the third part .