I would actually be totally possible with a series of png images. Each image is the same size XXXX by XXXX and the entire image is transparent except for one region. Each region has five such images - one for each potential region type. These are layers. To create the full map just pick one image of each region and merge them together. Now you have a single image of a full map. If a region changes type, throw the picture of that region of that type on top and merge again and you have a new world map. Then just change that region's stats in the database.
Of course, this is not saying it would be easy or even worthwhile. Just an idea I had...
