To my knowledge... we haven't seen any games provide actual structures which truly travel. As seen within the movie Krull an evil fortress would teleport and appear at different locations across the realm... this piece of the story was very interesting. Traveling structures should naturally be very rare, but definitely available within the editor. Such a feature would add a fun type of fantasy we've never seen for games.
Here are a few examples:
An Evil Fortress which teleports to a random new location once every 10_turns.
A Wizards Tower which floats on clouds. (Its shadow can be the source for moving to this location IF the travelers have the ability to fly.)
A Portal(teleporter) which travels on a floating island.
A Powerful Blacksmith on the back of a gigantic turtle. The turtle could travel on land and water plus while traveling in water it may submerge thus not being available for several turns. The blacksmith himself could be amphibian or have a magic item which allows him to breath underwater. History myths have spoken of turtles this large in size.