OK, so here's how the EX Dungeon "random maps" works...
There are a total of 64 pre-defined maps. Woda's Envoi has 32 of them, Ziemja's Canticle has the other 32 of them. When the game is booted up, it randomly selects 20 maps: 12 for Woda's Envoi, and 8 for Ziemja's Canticle. You only go through six maps in Woda's Envoi, but these six are different depending on if you go through the A exit or the B exit.
Each of these maps is actually a collection of 36 "rooms". There are a total of 40 different "room" types, and they are arranged in a 6x6 pattern. Each "room" is 16x14 tiles in size, or 256x224 pixels in size, so each map is up to 96x84 tiles in size, or 1536x1344 pixels in size. This was the only way so many maps could be crammed into such limited space; if I had gone with a "true" random map generator, each rebuild would have taken a long time to finish, and including 32 single large maps would have been fast but would have consumed massive amounts of memory. This method was a good tradeoff between rebuild speed and storage size.
Here's the two templates. The "rooms" start at 0 and go from left to right, up to down. So, the upper left one is 0, the one to the right of it is 1, etc. The one below "room" 0 is 5, the one below that one is 10, etc etc. You get the idea.
http://www.frozenutopia.com/msr-wodatemplate.pnghttp://www.frozenutopia.com/msr-ziemjatemplate.png"Parasite Eve" uses this same exact method in its superdungeon, and was the inspiration not only for Mysterious Song's EX Dungeon design, but for the whole EX Game concept.
Some trivia here... originally, Ogien's Peroration was also supposed to have randomized central maps, but the idea was scrapped in favor of the singular Crystal Maze. Much like the previous portions, it had a template, and maps were constructed ahead of time using the template.
http://www.frozenutopia.com/msr-ogientemplate.pngThese maps were not in the final build of the game and I don't remember if there are any surviving prototypes that actually use them.