Yup. The in-game map helps you get back to places you've already visited, but in order to find locations you haven't been to you'll often need to slog through the forest.
Mel:
Spoiler:The directions your men head off in are hints. Try following them.
