I know that UFO-AI-1 will not support destructible environment. I do not know if a destructible environment is a good thing or not, but I like to talk about a possible future. Here are my thoughts.
[Models]
What is the best way to model a house? It may be easier to model a house as one thing. Disadvantage: You can place this house only as a whole on a random map. Whenever you use this type of house it looks exactly the same. Another approach: Model cubes: e.g. a wall (only one square meter), a window, a corner, a roof, .... This cubes can be randomly merged together on a map. Disadvantage: Even to create a simple house you have to create 20+ cubes. Each of this cubes may need its own texture.
[Grid]
Can cubes be placed only on a grid or can the have any rotation? In a world editor it maybe easy to build up a house with single cubes, if all cubes are aligend. On the other hand all houses are then aligned too (like Sim City), but it may be a tedious (impossible?) task to build a house without creating any gap/lap.
[Textures]
If we shoot at a wall there may happen two things. The wall is destroyed completly. In this case I may see inside the neighbor wall. If I model this wall with this in mind, I will draw a texture for this missing face. Disadvantage: 99% of the time the engine has to draw/remove faces which may be never seen.
In the other case the wall may not be destroyed completly. The question that arises here. How does the model/texture looks yet? To modify a model one may use a CSG algorithm (although I dont know if there is piece of software that can do this on arbitrary models without any error). In a perfect world a 3D texture would solve this (because we can look inside an object). But a 3D texture with a size of 256 and 4 channels (RGBA) may consume up to 64 MB RAM (512 = 512 MB). Within the next 2 years I think it would be impossible to use them for game content.
[Objects]
It may be possible to create a house with cubes. But what happens with trees? cars? If the designer splits them at creation time he also has to model the interior. When I shoot at the car the engine may brake the model at this defined planes.
[Batches]
Today graphic cards are able to draw an enormous amount of polygons. But they are not able to draw an enormous amount of batches. A game which allows to move around every object is inherently slower than a game that has large objects that stay at the same location every time.
[Shadows]
It is more or less easily to calculate a perfect shadowmap (or lightmap as you like) at creation time. You may invest a day to calculate a perfect map based on some radiosity equations. No one cares, because this work is not repeated at runtime. But if you shoot at a window, everything changes. In UFO like game, you may see 10 or more lights on one screen (maybe 1000+ lights on one map). 10 lights means to render the scene at least 10 times and map this textures on the current scene.
If there is a sun, the sun may cast long shadows, a problem that is not solved, as far as I know, without introducing ugly artifacts (there are millions of shadow mapping examples with small objects).
[Physics]
Every generic physic simulation I have seen till today has problems in some situations. It happens from time to time that objects are rotating/moving not as intended, objects collide too early/late. It may not be a good idea to use this ideas to blow up a whole building.
In a FPS game you may blow up 10 objects at the same time, but in a UFO like game you may be able to blow up 100 of objects at the same time, something that current physics engine may not handle efficiently (every object may collide which every other).
There are tons of questions in my head. May be that is one reason that 99% of all games only have static environments/models. If there is more then one people interested talking about this topic I will post an overview of every game, I am aware, that has a destructible environment (and probably how they solved it).
I am happy to get response from anyone but especially from the ones who create models and paint textures. (BTW I know that my english is terrible, if there is something indecipherable I'll try to rewrite it).