One of the ideas we had was to paint a map in a regular painting program (like Microsoft Paint) and then convert it into an internal map format. I tried that here: Warning: SLOW
Conclusion: it works, but anti aliasing gets in the way. It’d be better to use a paint program that doesn’t have anti-aliasing.
Also see Azgaar’s much cooler version. I eventually used this idea (over a year later) in mapgen4, but there, I made my own painting code. Underneath, mapgen4’s painting code writes to a hidden heightmap image, and then reads that image to produce the map.