Going on a idea streak, so bear not bare with me.
The map needs a weather system. Weather effects can still be turned off to reduce the device lag, if your device is older. Since people are having trouble being able to figh the blob at swamp, this would be a great solution.
Rain, and The Baddy King
Randomly rain at: Graal City, Balamb, and Belle.
When the rain starts, it means that a boss of some sort is about to spawn at belle, after Graal City sign, or the place (which needs a name) before swamp.
Flashes of lightning will indicate that the boss has spawned in these locations.
Would be cool if the knights start to leave graal city to fight the boss (don't actually go fight it. They just take formation at the city sign.)
Fog and the Giant Blob at Swamp & Maybe a Giant Rat/Dullahan for Deadwood
Fog, mist starts at: Swamptown, and Deadwood (if they are going to keep it).
When the fog starts = boss is about to spawn.
The fog starts small, and when it suddenly gets very dense a Giant Blob/whatever they pick for deadwood will spawn.
Sandstorm at Destiny and the Scorpion/Giant Lizardon
Small sandstorm randomly starts picking up at Destiny, maybe Big City as well.
Sandstorm gets heavier, boss spawns.
Blizzard at Snowtown and The Giant Yeti/Snowman
Snow starts falling.
Snow + wind for snowstorm, and boss spawns.
Questions, comments, concerns?