words
You're right, I didn't really give any details on the nature of the game. I haven't said too much about it outside of IRC yet, but I might as well spill the beans.
The basic premise is that you are an exterminator, and you must destroy a newly-created race of giant, telepathic hivemind insects before their numbers proliferate beyond control, dooming the human race. While the actual combat will be mostly roguelike-style (with lots of ranged combat ala doomrl), the various factions of the game will manage their resource gathering/usage and unit deployment in a more RTS-like fashion. Meaning if you fight your way through to various egg chambers and torch the eggs you'll be saving yourself some future pain and wasting hive resources.
A key mechanic of the game is that the hive insects are all mentally linked, behaving like 'fingers' of a singular consciousness. Therefore I need the hive to be able to coordinate pincer attacks and flanks, as well as hanging back and attemping to flush the player out of small corridors instead of piling up to be dealt with one at a time as is typical of roguelike AI. The hive will also learn from your actions; the first time you throw a grenade, they won't know what it is. The second time they will know to either run away, try to kick it back at you, or sacrifice a unit by throwing it on top of it to protect the rest.
It might seem that the game is overly stacked against the player, especially considering that when one of them sees you, they all know where you are, but there will be various ways the player can disrupt the hivemind. In order for the bugs' psychic link to penetrate thick layers of rock (floor to floor), there will need to be special 'transmitter' bugs in the area, acting as vertebrae in the spine of the hive. If all transmitter bugs are killed on a floor, the remaining insects will be disconnected from the hivemind and easier to pick off. This obviously makes them a prime target for players and an important asset for the hive to protect. Disconnected hive insects won't learn either, so killing off the transmitters and then throwing the grenades won't let the hive learn about them. There will also be shorter-term solutions, like EMP pulses that disrupt the psychic link for a temporary period of time.
It's not just the bugs that will be using this group behavior either. There will be waves of police/military coming down, who will be giving information and taking commands from commanders on the surface. The AI entity that oversees the laboratory area will also be an important character, and will control a sizable host of robots for offense/support/repairs as well as numerous cameras for information gathering and monitoring.
I think what I'm looking for requires more than FSM's to pull off, but if you can think of a way that I could make it work I would love to hear it. In general I prefer simpler solutions but it seems to me that what I want to do is somewhat beyond the realm of FSM's.
I like that concept of dynamic terrain, although it would complicate things if you added player allies to the mix.
edit - I guess I should mention a bit more about what I want combat to be like. As I mentioned it will probably seem somewhat like DoomRL, with an emphasis on ranged combat. Fighting humans will probably involve a fair amount of running and finding cover, while fighting the bugs will often come down to mowing them down as they attempt to overwhelm you with their numbers, though some will have ranged attacks too like acid sprays / poison barbs or whatever. Even the bugs simply swarm-rushing you will require some modicum of coordination though, since I would want them to form a group(s) together near the player before attacking all at once.