Game Trails

Speaking of wilderness navigation again, one handy feature definitely worth considering in otherwise-trackless wilderness is game trails.

It's not much, but it's better than nothing

Game trails are paths produced by wildlife between sites that they commonly frequent, typically including lair, water source, and feeding grounds.  This, combined with their relative ease of traversal, make them a wonderful feature for adventurers.  If you're lost and dying of thirst, you can follow the trail and hope you get the water end instead of the lair end.  If you're in good shape and looking for treasure, you can instead look for the lair end.  Additionally, the trail's usual denizens tend to leave spoor - shed fur in the spring, droppings, chewed up trees, footprints, and suchlike.  This is a great opportunity to drop clues about what's living in the area.

Mechanically, following a game trail has the same effect on wilderness movement speed as a road (though they are much too narrow for wheeled vehicles, typically single-file, and may wind instead of running straight), but doubles (at least) the chance of a random encounter per unit time, with the odds heavily weighted towards the trail's creators.

A minimal game trail generation algorithm would probably take each lair on a hex map and link it to its nearest water source.  If we're willing to complicate things a little more, flying monsters do not leave trails, and arboreal / brachiating monsters may or may not.  Burrowing monsters that can rely on groundwater, like giant ants, probably don't either, nor do sealed or undead monsters that do not hunt (ghouls probably do, though), nor do aquatic monsters.  Social or sentient monsters with multiple lairs in the area may produce linked trail networks between their lairs.  Predatory monsters may also link their trail networks to the trail networks of their prey species.  Depending on the scale you're using for wilderness movement and the monster density of your hexes, the details of trail network structure may be irrelevant - I could see having a "game trailed" modifier for hexes, which when traversed give the party the choice between fast, risky movement and slow, safer movement.  On the other hand, game trails are likely to be relatively safe from non-monster natural hazards, at least compared to bushwhacking - nothing's going to build a game trail over a quicksand pit.