How intelligent is r.cost?

[Jim Westervelt]

Conn V Copas, Loughborough University of Technology, asks questions of
r.cost.  Involves finding least cost path to a lake.

# Can I simply use a map which contains 2 categories: lake and land?
   Yes, the lake would be given category 1 and the rest of the map 0.
# Or, do I need to create a map which defines the perimeter of the
# lake only?
   That would work too.   Perhaps the easiest however would be to give
   a travel time of zero to cells in the lake.  Then, give any starting
   point in the middle of the lake.
# I can vaguely see that this latter step requires one to perform a
# neighbourhood analysis in which one inspects the attributes of cells on
# each 'side' of a given cell, but exactly how would one do this in
# practice? Once I have my map of multiple coordinates in a suitable
# form, can I be sure that r.cost will select the 'cheapest' cell from
# that list when computing cumulative cost for a given cell? 
   The r.cost algorithm runs as follows:
   1) Sort all of the potential starting points in order of travel time
	  across the cell.
   2) If there are any cells on the list, pick that with the shortest
	  travel time. (else, quit)
   3) For that cell, compute potential travel time to all surrounding
	  cells.  If the potential time is less than that already assigned
	  to the cell (they start out at effectively infinite), update the
	  time to the cell.
   4) Add all neighboring cells to the sorted list.
   5) Go to 2.

By the way, there is a new and improved r.cost on moon.cecer.army.mil
which has two advantages over the r.cost of 4.0
   1) Faster sorting of the cells on the list (b-tree)
   2) Knight's move option.  This changes step (3) above by considering
	  not only the 8 surrounding cells, but the 8 cells that are in the
	  position where a chess knight could move to.
   3) Better management of swap space
   The first and third upgrades significantly improves execution speed.
   The second generates a more correct solution at a cost in speed.