🚀 go-pugleaf

I hope this isn't a FAQ, but I'm looking for a least-cost path algorithm
for a hexmap wargame.  To be useful, it needs to meet the following
requirements:

  -- Take into account varying terrain costs.  The direct path will 
     almost never be the least-cost path (so shortest path solutions are
     out).

  -- Be efficient.  Exhaustive searches of the entire game board will
     not work since there are several hundred units and several thousand
     hexes (100 x 100).

By way of background, this is a fairly typical land/air wargame.  The
ground portion consists of a 100 x 100 hex map (each hex 25km across).
Each hex can contain mountains, clear, desert, etc. type terrain.  Some
hexsides are crossed by rivers and fortifications.  Roads and railroads
traverse across hexsides through the center of various hexes.

If you have an algorithm I'd sure appreciate any help you could provide.

-------------------------------------------------------------------------
Capt Karl Mathias                                  kmathias@afit.af.mil
Graduate Student, Air Force Institute of Technology
"Opinions expressed are my own and not those of the U.S. Air Force"