Yeah, I made a thread a while back saying that regenerating the obstacle map for just one character cost 10fps for 3 seconds or so. With multiple characters, it pretty much brought the game to a halt.
It was for that reason that I got rid of the destructible environment feature. It is not big deal, but I was going to have it in until I realized the cost of regenerating the obstacle map if even just one block was destroyed.
If it would add/remove "just" the object that was created or destroyed from the obstacle map, I figure it would not have been a problem, in other words not affected the framerate.
Even if a character ran into the object and paused for a second before realizing it needed to regenerate the obstacle map, that's still better than dragging the fps down to nothing in order to make sure it can move uninterrupted.
So yeah, if regenerating the obstacle map can be done per object created/destroyed or within a limited radius of the character, it would be much better.