[furgufxu] shortest path on a grid

consider a square grid graph.  assign random weights to edges, uniformly and independently sampling between 0 and 1.

what do shortest paths between nodes typically look like?  this should be easy.  path between opposite corners?  longest shortest path (graph diameter)?

instead of assigning weights to edges, consider assigning weights to nodes because that seems simpler.  path cost is the sum of nodes.

consider sampling weights from non-uniform distributions.  need to avoid negative weights.

shortest paths will prefer valleys: connected or nearly connected strings of low cost nodes or edges.  valleys define a maze.  previously.

do terrain generation (e.g., fractal terrain generation) on the grid to generate heights on nodes.  nodes are no longer statistically independent.

node weights could be heights.  narrative: oxygen decreases with height, and you need to pack oxygen with you, so you want a path that prefers lower elevations.  or stays near an ideal elevation: oxygen also becomes poisonous at the high pressues of low elevations.

edge weights could be euclidean distance between nodes in 3D.  or abs(h1-h2)^r.  or anything monotonically increasing in abs(h1-h2).

node weights could be magnitude(gradient) or laplacian.  mag(grad) might encourage traveling on ridges as done by mountain climbers in real life.

finding the shortest path between opposite corners of a 2-by-N grid (whether weights on edges or nodes) is not trivial, even though the optimal path never goes "backward".

consider a 2^D grid in D dimensions.

let weights on nodes be a checkerboard pattern of zero and random positive weights.

consider a checkerboard 3^D grid.  perhaps forbid center node.