I think it should be possible to leave messages where you are. This including scribling in the ground or sand with a stick, writing with calc on a rock or wall, dropping a letter on the floor, carving letters on a trunk or maby even leaving magical writing in the air.
All these forms of messeging should of cause wither away and disappear over time.