Also ich würde mal stark annehmen, dass diese Tiles nicht zufallsgeneriert sind, sondern im vorhinein definiert. D.h. der Grafiker hat alle möglichen Arten von Kurven und Verbindungen des Materials erstellt, um diese Formen möglich zu machen.

Du könntest es aber zumindest mit Surfaces probieren. Zeichne deinen normalen Background, darüber einen anderen, den du nur teilweise möchtest und erstelle ein schwarzes Surface in der größe des BG's. Per Maus könntest du nun weiße Kreise etc auf das Surface Malen und schlussendlich einen neuen BG aus dem Surface machen und diesen als Alphamaske für den anderen verwenden.

diese maps sind garantiert nicht zufallsgeneriert.
hab früher in der "pokemon hacking szene" teilgehabt, und würde mal so behupten das es mit tilesets/chipsets
gemacht wurde.

mfg

Die Tilesets sind nicht zufallsgeneriert, sondern mit hand aufgetragen.
Wie bereits gesagt sind diverse übergänge gemacht worden die vrschieden kombiniert wurden. So wird das schon ein paar Jahre gemacht, egal in welcher sprache
Es gibt viele "gerippte" (was zu verlinkt hast war auch eins davon) Tilesets, die man sich ansehen kann. Dort wirst du feststellen, das sich die ganze map in kleine quadrate aufschlüsseln lässt. Teilweise werden die Tiles einfach nur nicht gleichmäßig übereinander verteilt, um einen organischen eindruck zu erziehlen.

Glaube nicht, dass GIMP geeignet ist.
Ihr werdet wohl selber einene Map-Editor schreiben müssen.
Den könntet ihr etwa in C++ schreiben, und Teile eurer Game-Engine verwenden, etwa die Rendering-Engine, und einen Editor drum rum schreiben zB mit QT oder GTK+.
Möglich wärs auch mit C# und WPF, welches optimal für solche Applikationen ist. Allerdings müsstet ihr euch hierbei auch um interopability zwischen dem nativen C++ Code und dem gemanagten .Net C# Code kümmern.

So oder so braucht ihr dann natürlich auch ein Map-Format und müsst dieses auslesen... google hilft weiter