Dynamic Heightmap Loading

I'm currently working on an isometric strategy game. The "level" consists of basically two parts - a two-dimensional heightmap, and a two-dimensional character grid. These two parts correspond directly, each being a two-dimensional array of dimensions AxB. The heightmap is the basic geometry of the level, while the character grid dictates what type of thing each grid unit is (grass, sand, water, etc).

Now, here's where I'm having trouble: both the heightmap and grid change quite frequently, and tend to be rather large dimensionally (128 x 128 needs to run smoothly). In my original implementation, I had a different mesh for each grid type, and would create an entity for each node in the grid, like so:


for(x=0; x<gameMap.width; x++)
{
   for(y=0; y<gameMap.height; y++)
   {
      char buffer[12];
      sprintf(buffer, "res%.3i%.3i", x, y);

      celentity=pl->CreateEntity(buffer, bl, "level_behave", "pcobject.mesh", CEL_PROPCLASS_END);
      pcmesh=CEL_QUERY_PROPCLASS_ENT(celentity, iPcMesh);
      pcmesh->SetPath("cellib/lev");
      pcmesh->SetMesh("genFloor", "floor");
      if(!pcmesh->GetMesh())
      {
         return ReportError("Error loading mesh...");
      }
      zonemgr->PointMesh(buffer, "main", "Origin");
      pcmesh->MoveMesh((iSector*)(0), csVector3(x, gameMap.heightmap

[y], y));

}
}

This achieves the desired result in that I have a game grid that I can modify on the fly, but framerate leaves quite a bit to be desired. My suspicion is that there's a much more efficient way to do this with static geometry that gets recompiled whenever a change occurs, but I'm a little stuck as to how to begin that, or if that's even a good idea.

Ideas? Suggestions? Links? Anything helps.