X-COM: UFO Defense / UFO: Enemy Unknown (1994)

X-Com was originally going to be a sequel to Laser Squad. The popularity of Civilization led MicroProse to suggest some changes, which eventually lead to X-Com being set on Earth with a strategic element. The original release actually had the geoscape and the battlescape as completely separate executables, but the actions in one half influenced the situation on the other side in significant ways. For example, shooting down a UFO made it crash-land, destroying its powerplant and weakening the aliens, but leaving fewer resources for your team to recover from the site.

This extended to the procedurally generated maps. Where Laser Squad had used a set of fixed missions, X-Com uses randomly generated maps to convey the feels of a global defense force. Each terrain type on the world map lead to a different kind of map in the tactical battles (plus the city terror missions). The maps are assembled from large pre-assembled blocks, most visible in the farm missions. Additionally, the cities have some simple rules to get streets and larger structures looking right. Because the UFO and X-Com landing craft can be placed anywhere on the tactical map, scouting is required to assess the tactical situation.

The other major factor for making the maps memorable is their destructibility and interactivity. While the only action your troops can really take to alter the map is shooting things, the various tiles on the map respond in expressive ways. Walls get knocked down, alien craft withstand grenades, and gas stations explode into flames. As your firepower and mobility increases with research, your experience of the tactical maps changes.