# Main functions of the HotPath heuristic (version 0).
# Last edited on 2021-02-18 22:35:22 by jstolfi

import hotpath_IMP
  
def best_path(o, BS, CS, Delta, maxcalls, parms):
  # This procedure tries to concatenate a given set of partial paths
  # into a single tool-path that minimizes the total execution time,
  # respecting a maximum cooling time constraint for adjacent traces.
  #
  # The parameter {o} is the initial position of the nozzle -- a pair
  # (2-tuple) of float coordinates, in millimeters.
  #
  # The parameter {BS} is a list of {block.Block} objects, the /building
  # blocks/. Each building block represents a part of the extruded slice
  # that is to be inserted in the final tool-path as a single sub-path.
  # 
  # At the simplest, each buildng block can be a single trace. For solid
  # fill, in particular, {BS} could be set of /raster lines/, single
  # parallel traces that spaced with no gaps. For non-solid fills, each
  # building block may be a zigzag path. More generally, it can be a
  # part of the contour, a bunch of filling scanlines, or an entire
  # sub-slice like an island with its contour and filling. The only
  # criterion is that it is OK for the heuristic to execute one choice
  # of each block in one go, witout interruptions to do other blocks or
  # parts thereof.
  #
  # The parameter {CS} is a set of /relevant contacts/ (see {contact.py})
  # between traces that occur in the paths of {BS}; specifically, a list
  # of {contact.Contact} objects. Each contact must refer to two traces in
  # different blocks.
  #
  # The parameter {Delta} is the maximum allowed cooling time between 
  # the deposition of the two sides of any of those contacts.
  #
  # The {maxcalls} parameter is a limit on the number of recursive calls
  # that the procedure can make. It is used only after the procedure found
  # the first complete tool-path that is valid (satsfies the cooling
  # constraints). Thus, if it is zero, the procedure will return as soon
  # as if finds such a path. If it is a sufficiently large number, and the
  # number of possible paths built from the given blocks is small enough,
  # the procedure will return the optimum valid path (the one with
  # smallest build time).
  #
  # The {parms} parameter is a Python dict that specifies printer-specific
  # parameters, such as the maximum nozzle traveling speed and acceleration. 
  # It is used to compute the execution times of those connectors and 
  # the conctact covering times.
  #
  # BLOCK ALTERNATIVES
  #
  # Each building block is actually one or more /alternatives/ or
  # /choices/, which are paths that are considered equivalent for the
  # purpose of creating the same part of the slice. E. g. a certain part
  # of a solid fill can be covered by two different paths of alternating
  # rasters, depending on the drection of the bottom-most raster; and
  # each can be executed in two distinct directions. Or a closed contour
  # may be excuted starting at several specific points.
  #
  # In general, the reversal of an alternative should be added as a
  # separate alternative. Even if it begins and ends at the same point,
  # the direction of its execution may matter if it has ontacts with
  # other blocks
  #
  # For good economy, the alertnatives of a building block must reuse the
  # same {move.Move} objects whenever possible. Otherwise separate contact
  # objects may have to be specified for each alternative.
  #
  # The procedure uses a backtracking depth-first search heuristic with 
  # ordered choices at each step.
  return hotpath_IMP.best_path(o, BS, CS, Delta, maxcalls, parms)