New path finder

New path finder

We've been using Phil Lapsley's A* library to find land paths since
Chainsaw 3.  It's reasonably general, and uses relatively complex data
structures to conserve memory.  Unfortunately, it occasionally leaks a
bit of memory (see commit 86a187c0), and is unsafe for long paths (see
commit e30dc417).

To speed it up, v4.2.2 added two caches: the neighbor cache and the
path cache.

The neighbor cache attempts to speed up lookup of adjacent sectors.
It allocates 6 pointers per sector for that.  In my tests, this is
more, sometimes much more memory than the A* library uses.  See commit
7edcd3ea on branch old-astar for its (modest) performance impact.

The path cache attempts to speed up the update's computation of
distribution path costs.  There, A* runs many times.  Each run finds
many shortest paths, of which only the one asked for is returned.  The
path cache saves all of them, so that when one of them is needed
later, we can get it from the path cache instead of running A* again.
The cache is quite effective, but a bit of a memory hog (see commit
a02d3e9f on branch old-astar).

I'm pretty sure I could speed up the path cache even more by reducing
its excessive memory consumption --- why store paths when we're only
interested in cost?  But that's a bad idea, because the path cache
itself is a bad idea.

Finding many shortest paths from the same source has a well-known
efficient and simple solution: Dijkstra's algorithm[*].

A* is an extension of Dijkstra's algorithm.  It computes a *single*
path faster than Dijkstra's.  But it can't compute *many* shortest
paths from the same source as efficiently as Dijkstra's.

I could try to modify Phil's code to make it compute many shortest
paths from the same source efficiently: turn A* into its special case
Dijkstra's algorithm (at least for distribution path assembly), then
generalize it to the many paths problem.  Of course, I'd also have to
track down its memory allocation bugs, and make it safe for long
paths.

Instead, I'm replacing it.  This commit is the first step: a rather
unsophisticated implementation of Dijkstra's algorithm specialized to
hex maps.  It works with simple data structures: an array for the hex
map (16 bytes per sector), and a binary heap for the priority queue
(16 bytes per sector, most of it never touched).  This is more memory
than Phil's A* uses, but much less than Phil's A* with v4.2.2's
caches.

[*] To fully exploit Dijkstra's "many paths" capability, we need to
compute distribution paths in distribution center order.