First, how do you randomly generate terrain and not have deserts next to swamps? If you think of terrain as fitting into hot-cold and wet-dry continuums, with a chart like this:
You can generate terrain that will always be one step away from the temperature and moisture of the terrain you were in. Imagine a position on the graph which represents the features of the area you are in. Like this:
|The black square is pretty temperate, roll a 1 and things get colder and dryer|
Roll to check the next chunk:
- colder / wetter
- colder / dryer
- hotter / wetter
- hotter / dryer
|This graph has the axes opposite of mine|
The second possible way to handle this is to generate features on the fly with some component charts. For example:
Roll for each:
- Great lack
- Great Abundance
If we aren't keeping track of strict units like hexes, we could more loosely determine the size of the piece of land we are in, like this:
Size of this chunk of terrain:
Keeping Track of Points
But, none of this gets at how you would keep track of points in a pointcrawl without using something like hexpaper. I think the answer is in the connections. This topic made me think of my long time project of trying to randomly generate catacombs with hexes. You can see some examples if you scroll through my hexes label. Doing generating based on connections is easy with hexes because you can roll 1 d6 to tell you how many exits a hex has and 1d6 for each to find the position of that exit. That still requires hex paper for easy record keeping, though.
Some of these combinations of exits have shapes like a "T" or a "K." And that might be a possible approach to keeping track of things. For example: You come to a large forest with several roadways, they take the shape of a "K" and you have entered at the bottom straight leg of the "K." So, just using the letters of the alphabet or the shapes of numbers to evoke connections to new areas might be a way to generate and record connections.
Another idea that comes to mind, is to record the connections in relation to a clock face. Kind of the way fighter pilots talk about incoming bogies. So, for example, You come to a grassy plain with roadways continuing into the distance in the direction of 2 and 10. A d12 would tell you a direction and maybe a d4 or d6 could tell you how many connections.
Distance between Points
Without a regular grid of some sort another issue will be determining which points are farther away than others. Are simple sizes above could help here. If the terrain you're in is huge it could add a certain amount of travel to get to any point. And if you determine the size of the terrain you're moving into it would tell you how much longer until you reached the point of interest.
Encounters and locations I leave for someone else, but hopefully the ideas here will be interesting to folks.