You can create a random map using the map editor rather than in the play-sandbox mode; the method is similar (once you are in the scenario editor).
Go into map editor (accessed through "extras"), enter some details then create the map. Create the map again if you don't like it. Add/remove buildings, trees, roads wherever you want; you have to add the palace first, then roads... similar to the way you place building sites in-game. You might want to add a stockade too.
When ready, save the map (it is saved as a .{} file). Warning don't save the map before you place the palace - the program freezes. Play as a scenario (title is the same as what you entered when you saved the map), and the game will automatically play your map as a sandbox (unless there is a .txt file with the same title as the .{} file).
You can reload this map later in the map editor, make alterations to the map, then save the new version. I don't know that you can alter the King's traits etc at this stage.
