I have heard of one multiplayer game with terrain that changes. I cant remember the name, but i think i is a fps. I never actually played it to see how good it was. I was wondering if anyone else has ever done this in a multiplayer game. I am currently debating whether I will use it since it would add so much realism, but bandwidth is the main cause for questioning it. Also, if anyone has any suggestions on how to do it efficiently, I would like to hear.

It depends in what way the terrain is being modified I guess. For example for an explosion, you could just tell all the clients "Explosion of magnitude 23.45 at (53.23, 74.2, 100.84)" and they all know what to do with it... no bandwidth problem there. However if its something like one player driving a bulldozer or something you will need a more constant stream of information. Even then this could be just the movements of the bulldozer, which you will probably be sending anyway.
Either way I can''t see too much potential for bandwidth problems... unless maybe it''s a multiplayer bulldozer racing game

Red Faction is the game you are thinking of, using the GeoMod engine. I''ve played it, is quite fun multiplayer, when you blow a hole in front of someone as they''re running and they fall down
As said above, it''s really not that big a bandwidth problem, as long as it is a session based game. (All players are connected at the start of the game). The problems start to come into play for people who join a map halfway through a game for example, and they have to download the data for every explosion that''s happened so far, simulate them all on the terrain, and THEN they can start playing. This could extend your load times by a reasonable amount. I think red faction allowed you to join in the middle of a game, i can''t remember what the laod times were like though, i only connected once then played for hours . Deformable terrain is, at the moment, pretty much a non-issue for persistent state games (such as MMORPG''s) because, not only do people have to download everything that''s happened since they were there last....for each zone (as they enter it, or as they connect), but the servers also have to REMEMBER every single terrain deforming thing that has happened, and this could take up valuable memory/disk etc. Load times for clients could extend into hours on slower connections....for each zone they enter!
But for a session, or near session based game it''s not so bad. Just remember if people can join halfway through a game, the server has to remember every explosion etc. and feed it to the player as the connect.
For the record, not all the weapons in Red Faction deformed terrain, only explosive weapons (rocket launcher type weapons, explosives) caused damage, things such as rifles, chainguns etc. didn''t cause real damage to the environment. Because basically all the explosive type weapons were slow load, it limited the number of explosions that could happen, and therefore resulted in very little extra bandwidth used. What i believe is actually a bigger problem, is the modifying of the video/rendering data that has to be done when an explosions happens. This can severely hamper the framerate (as is my current not-so-good knowledge of things ), but once again, the slow loading times of weapons that could actually damage the environement kept this to a minimum.
Oh, and lastly, from what i could tell in redfaction, they way it handled vehicles (or vehicle, i can only remember 1 that damaged terrain) The mining vehicle (big metal thing with those big spinning horn things on the front) would chew up a big chunk of terrain, then move forward, then chew another big chunk, about once every couple seconds or so, it was a constant stream of destruction.
Hope theres some useful info there

well, thats the problem. I wanted to use this for a persistent world game. What I was thinking of doing is, streaming heightmap info of nearby land as the player approaches it. Obviously recording every deformation wouldnt work for me. I guess I''ll just have to experiment.

Depending on the game you could transmit the crater information cloest to the player start position and over the next few seconds transmit crater info that is furthur away.
Thus you are not using up too much bandwidth or CPU time to begin with.