Roads I: Original Pathfinder

No, not that pathfinder. To be honest, I've never played it.

I'm talking about a real pathfinder.

Where do the roads go? How can I get from Point A to Point B most effectively?

I won't try to give an indepth explanation of how the algorithm I've chosen (A*) works, since others can do that much better. I'll just explain how I implemented it.

def a_star(start, end):
  def g(current):
        z = zip(closed_list, closed_list[1:] + [current])
        return sum(travel(i, j) for i, j in z)
    def h(current):
        return(distance(hexes[current].c, hexes[end].c) / 86.6)
    def f(current):
        return g(current) + h(current)
    open_list = list(hexes[start].neighbors)
    closed_list = [start]
    came_from = {sorted(open_list, key = lambda h: f(h))[0]: start}
    while open_list:
        s = sorted(open_list, key = lambda h: f(h))[0]
        open_list.remove(s)
        closed_list.append(s)
        if s == end:
            break
        for t in hexes[s].neighbors:
            if t not in closed_list:
                if t not in open_list or g(t) < h(t):
                    open_list.append(t)
                came_from.update({t: s})
    path = [end]
    while path[-1:][0] != start:
        path.append(came_from[path[-1:][0]])
    return path[::-1]

Basically, we find the path that minimizes the cost of travel. I've made some custom adjustments to the travel heuristic here. The only modifications so far are for height - I need to work on more specific terrain later. For now, moving up or down 400 feet costs an extra day of travel. If you're moving into or through an area that's above 8000 feet, it costs an extra day for each 1000 more feet you ascend (due to oxygen requirements - 8000 feet is the general baseline I've found, but I'm not a climber, and I'd like some better data to use here).

Here, it is quite obvious that even those constraints are enough to create an interesting pathway. Rather than take the "shortest" path (a straight line), our caravan is compelled to ascend into the foothills, and follow the crests of the mountain chain, until at last a suitable pass is found.

This took about two hours to implement - much better than I was expecting. I think the next steps are to figure out the effects of terrain, and to save the cumulative road score (how many paths are found through this hex), which can affect the desirability index. High traffic roads are good places to start up a village and leech off the resulting trade.

One thing I don't know how to do yet is sea travel. This is an important one, but there are a few problems.

1. I don't save sea hexes as terrain; I leave them blank to save file size
2. Sea travel is highly dependent on winds and currents, which I have, but not in a format that is good for cellular automata

There are ways around these problems, but I have to pick them out of my brain first. Right now they're floating around nebulously and I can't see them very clearly.