Knowing that giant slaves had done most of the work would worry me if I were involved with this passage. As to the map, the colors suit the theme well, and you include some interesting features. A scale would be nice. As to the key: 5,6 - "Barrack" takes a "c"; while "Barracks" would be more usual, "Barrack" is acceptable; 16, 20 - the backstory suggests sufficiently recent construction that it is unlikely the apostrophes would have been dropped from "Aluduin's" and "King's" (or "Kings'"); 18 - "Lower" should be capitalized to maintain consistency with the rest of the key.