In that case, I'll continue by talking about the overworld.
Knowing that there would be day and night, I didn't expect the two worlds to be considerably different. So my focus was on the day version, knowing that the night version would only take one evening's worth of work to do (which it did). You know, palette swap, adjusting certain things, etc. Almost all of the actual landscape would be taken care of once the world of the day was done.
You may have noticed in that animated .GIF that I started with a hand-drawn plan, here it is again:
I chose to do a 16 x 16 screen grid for the map, or 2560 x 2048 pixels, which is the same size as Koholint, or Holodrum (without the westernmost lonely screen). Then I just freely drew what came to mind once I had decided the size of the "canvas".
I figured I would have to go with the usual mountains-in-the-north and ocean-to-the-south that all three Game Boy games' main worlds used. Though many of the dungeon entrances would shift at later phases of the world's development, the rough idea of where they were influenced what I would put in the various regions of Falsia. At this point, however, the sixth dungeon (Magma Mines) and the seventh dungeon (Vampire's Crypt) were still up in the air, and so the grey area in the northeast was originally going to be the graveyard, for what was then going to be the area around the sixth dungeon, the Vampire's Crypt. You can also see other oddities, most obvious being that the river is way too wide.
When it came time to make the grid, I had a grid of black lines showing the right columns and the bottom rows of pixels for every tile. The blue lines indicate the screens. (I'd never gotten around to using an image editor with a grid.) The above image is the initial hand-drawn plan with the grid in place.
But then I realized that it was not enough to know where the screen edges were. Though already marked, the corners would be particularly important. Had this been a real playable game, like the other Zelda games, you would know that the corners must be "blocked off". It can't be a standable/walkable space for Link, as I suppose the game would have to load up more data and quicker if Link co go diagonally across screens, not to mention being more disorienting, since the Game Boy game screens don't scroll. You can see this even in the Super NES game (A Link To The Past) with areas that only scroll to a certain point; the Great Swamp has the same area size as other "zones" but is actually four segments, with a rock formation in the middle to prevent that diagonal-walking.
So I made another grid, this time with trees in the corners. The image above shows four screens of that grid. As in filled in the screens with tiles, many of these trees would be replaced with larger clumps of trees, or walls, or rocks, etc. And they would serve as screen-edge markers when tiles filled in over the blue lines. Always being aware of the screen edges was important, as I didn't want to place something at the edge of a screen that would block off Link walking in from the adjacent screen.
Details about managing the screen edges and corners was important. Even if no one would notice if I made a "mistake" in a couple places, knowing the screen boundaries allowed me to make things with a certain scale in mind.
But the actual tile-filling would take place more than a couple months later, as I went to work on the right main dungeons. More about them later, of course. When I came upon the overworld again, it was the end of February, so I only had about a month to do it all! Sure, the planning phase was done, but here comes the hard part.
Most evident in A Link To The Past, but also noticeable in Link's Awakening, is that Zelda worlds are made up of square "zones". Somewhat distinct geographical locations fit nicely into squares of equal size. Knowing this, I decided to use that same idea, which not only kept the plan simple, but to break down this large task. The initial plan was to do a region/zone a day...which proved difficult to keep up with, especially with other things I have to do outside of VGMaps.com. And yes, Super Smash Bros. Brawl coming out on March 9 did little to help... >_<