Paper maps before that. If you were in AAA you could get a "trip map" that was a complete route with turn by turn directions and a spiral bound, printed map that you paged through as you traveled, but paper maps worked well. Not as convenient as a phone but not terrible either.