Assuming the map is either large scale (I think Middle Earth is about Europe sized so it's probably a bit too big an area, but borderline) or in the Normal Mercator projection (Which preserves direction at all scales), the straight lines are rhumb lines (lines along which the bearing is constant) used for Dead Reckoning navigation as Ascension said. The curved lines on the other hand are completely meaningless decoration that show that the artist is certainly not a cartographer.

Check this thread for links to my Rhumb line generator script, and some pre-generated lines: http://www.cartographersguild.com/sh...l=1#post154451