while the 2D sprites were cleaned up in Adobe Photoshop and imported and animated using Extractor. To create the texture maps for the terrain, the artists used Photoshop to draw the equivalent of an aerial photo, and then applied it to the 3D landscape using Loathing. Initially, the developers had planned on using fractal-generated landscapes, but they felt the randomness of such landscapes would make it difficult to design interesting levels, and so all maps were instead constructed by hand. Implementing pathfinding was a particularly difficult challenge. The terrain in the game is a 3D polygonal mesh constructed of square cells, each of which is tessellated into two triangles. Certain cells have an associated terrain type which indicates their impassability, and may contain any solid object. The team originally planned to use the A* algorithm, but soon realized this would create problems in terms of the realism they desired. As impassable obstacles can lie anywhere on the map, and as the square cells are quite large, the obstacles are not guaranteed to be aligned at their center. Furthermore, even if an obstacle did occupy exactly one cell, the A* algorithm would make a unit walk up to the obstacle, turn, and continue around it. The developers instead wanted their units to move to avoid obstacles ahead of time, as they approached them, such as smoothly weaving through a forest instead of continually heading straight for a tree, only to stop and suddenly walk around it. As such, they wrote their own pathfinding algorithm. As the terrain in the game never changes, paths could be calculated once and remembered. Then, the team factored in arbitrarily placed obstacles and periodically refined their pathfinding using a vector-based scheme. If the planned path caused the unit to hit an obstacle, the path was altered, with the AI choosing whether deviating to the left or the right was the shorter option. Their system worked for 90% of cases, but in testing, the developers discovered several scenarios where their pathfinding algorithm didn't work especially well. However, by the time they made this discovery, it was too late to implement the changes that would have been necessary to fully correct it. As such, their assessment of the pathfinding in the final version of the game was that "it works pretty well and provides the effect we sought, but there's definitely room for improvement." Speaking of the game's