C
C SUBROUTINES FOR SEARCHING OF A PATH BETWEEN POINTS
C
C THIS VERSION OF THE FILE ZOEK BELONGS TO PCONE
C
C  ***** LAST UPDATE 19-09-84 *****
C  THE SEARCHING PROCESS IS CHANGED
C  NEW PRINCIPLE: SEARCH IN LONGEST DIRECTION
C  ADDED SEARCHING THE SHORTEST CONNECTION
C
      SUBROUTINE PRIOR(IPRIR,NSTEP,MLEN)
C
C Function for the determination of the direction for movement.
C The searchprinciple is to move in the current direction, except if a
C movement is possible that leads to a decrease of distance between
C the current and target point. Prior indicates the direction of possible
C movements
C if IPRIR = 0 there is no further path
C if IPRIR =-1 the target has been reached.
C for IPRIR= 1,2,3,4 the direction is indicated
C LX,LY   : current grid coordinates
C LX2,LY2 : target gridcoordinates
C IAPX,IAPY : coordinates nearest point to target point
C IDIST : initialized in main program (to a large value)
C NSTEP : Number of steps from the start
C MLEN  : Maximum length of the trace
C ZOEKX,ZOEKY: BOOLEANS TO INDICATE PRIORITY SEARCH DIRECTION
C NSTEPM: MAXIMUM NUMBER OF DEVIATING STEPS
C
      LOGICAL MOV,D1,D2,D3,D4,IPRIR,C1,C2,C3,ZOEKX,ZOEKY
      INTEGER NSTEPM
      COMMON /PCOORD/LX,LY,LX2,LY2,IAPX,IAPY,IDIST
      COMMON /LASTMO/ MOV
      COMMON /DIVPAR/ZOEKX,ZOEKY,NSTEPM
      DATA D1,D2,D3,D4/1,2,3,4/
C
C COMPUTE THE POINT NEAREST TO THE TARGET POINT, WHERE A FREE POINT
C EXISTS ON THE OTHER PLANE
C
      IDX=IABS(LX-LX2)
      IDY=IABS(LY-LY2)
      IAFST=IDX+IDY
      IPRIR=-1
C
C THE TEST FOR THE MAXIMUM APPROACH IS INVALID FOR DISTANCE ZERO
C
      IF(IAFST.EQ.0) RETURN
C
C the test below has as effect that only a path with a prescribed
C (via MLEN) length can be found
C
      IPRIR=0
      IF(IAFST+NSTEP.GT.MLEN+1) RETURN
      IF(IDIST.LT.IAFST) GOTO 100
      CALL PUNTB(LX,LY,C2)
      IF(C2.EQ.0) GOTO 100
C
C SAVE THE COORDINATES OF THE CLOSEST POINT TILL TARGET UNTIL NOW
C
      IDIST=IAFST
      IAPX=LX
      IAPY=LY
C
C TRY LOWERING THE X OR Y DISTANCE, DEPENDING ON ZOEKX AND ZOEKY
C
      IF(.NOT.ZOEKX) GOTO 101
      IF(LX.GE.LX2) GOTO 50
      CALL CHECK(D1,C1,C2)
      IPRIR=D1
      IF(C1) RETURN
      GOTO 101
   50 IF(LX.LE.LX2) GOTO 101
      CALL CHECK(D3,C1,C2)
      IPRIR=D3
      IF(C1) RETURN
      goto 100
C
C TRY LOWERING THE Y distance, OR SKIP IF ZOEKX IS TRUE
C
  101 IF(.NOT.ZOEKY) GOTO 100
      IF(LY.GE.LY2) GOTO 51
      CALL CHECK(D2,C1,C2)
      IPRIR=D2
      IF(C1) RETURN
      GOTO 100
   51 IF(LY.LE.LY2) GOTO 100
      CALL CHECK(D4,C1,C2)
      IPRIR=D4
      IF(C1) RETURN
C
C THE THIRD OPTION IS TO CONTINUE WITH THE PRESENT DIRECTION
C EXCEPT WHEN ANOTHER DIRECTION IS BETTER
C
  100 GOTO(10,20,30,40),MOV
   10 CALL PRIOR1(D4,D2,IPRIR)
      RETURN
   20 CALL PRIOR1(D1,D3,IPRIR)
      RETURN
   30 CALL PRIOR1(D2,D4,IPRIR)
      RETURN
   40 CALL PRIOR1(D3,D1,IPRIR)
      RETURN
      END
      SUBROUTINE PRIOR1(NA2,NA3,IPRIR1)
C
C LX,LY: current coordinates
C CA1 IS THE CONDITION INDICATING THE APPROXIMATION WITH THE CURRENT
C CONDITION.
C CA2 IS THE CONDITION INDICATING THE APPROXIMATION OF 90 DEGREES ANTI
C CLOCKWISE ROTATED MOVEMENT RESPECTIVE TO THE CURRENT DIRECTION.
C NA2 and NA3 are perpendicular directions to the current direction
C NA2 IS 90 DEGREES ROTATED ANTICLOCKWISE
C
      LOGICAL C1,C2,C3,CA1,CA2,NA1,NA2,NA3,IPRIR1
      COMMON /LASTMO/ NA1
C
C the default is to continue, this will generally be possible
C
      IPRIR1=NA1
C
C check the possibility of continuation
C
      CALL CHECK(NA1,C1,CA1)
C
C check if continuation gives an approach
C
      IF(C1 .AND. CA1) RETURN
C
C If continuation gives no approach check for other directions
C
      IPRIR1=NA2
C
C is a perpendicular movement possible?
C
      CALL CHECK(NA2,C2,CA2)
C
C Does it give an improvement?
C
      IF(C2 .AND. CA2) RETURN
C
C the perpendicular movement was no improvement, check the other one
C
      IPRIR1=NA3
      CALL CHECK(NA3,C3,CA2)
C
C ready if this movement gives an improvement
C
      IF(C3 .AND.CA2) RETURN
C
C we arrive here if no possible movement gives an approach
C
C check if any continuation is possible
C
      IPRIR1=NA1
      IF(C1) RETURN
      IPRIR1=NA2
      IF(C2) RETURN
      IPRIR1=NA3
      IF(C3) RETURN
C
C if we arrive here no movement is possible and prior1 is 0
C
  100 IPRIR1=0
      RETURN
      END
      SUBROUTINE SEARCH(LX1,LY1,IX1,IY1,LX2A,LY2A,IX2,IY2,NR,succes,LE)
C
C search routine for a connection between two points on a grid that does
C not cross any other connection.
C the shortest connection is searched between the two points
C
C Parameters:
C
C LX1,LY1: STARTPOINT OF THE CONNECTION
C LX2,LY2: ENDPOINT OF THE CONNECTION
C IX1,IY1,IX2,IY2 : (IX?,IY?) IS THE DIRECTION VECTOR OF THE ROW
C                   OF THE STARTING VIZ. THE ENDPOINT
C NR: The number of the connection
C LE: The length of the connection as found
C succes is .true. if the connection is found
C NSTEPM: MAXIMUM NUMBER OF STEPS ALLOWED
C
      LOGICAL DIR(600),MOV,LEFT,RIGHT,succes,ZOEKX,ZOEKY
      INTEGER NSTEPM
      COMMON /PCOORD/LX,LY,LX2,LY2,IAPX,IAPY,IDIST
      COMMON /LASTMO/ MOV
      COMMON /DIVPAR/ZOEKX,ZOEKY,NSTEPM
      LX2=LX2A
      LY2=LY2A
      idetou=NSTEPM
      imaxde=NSTEPM*2
      iminde=0
      MLEN=IABS(LX1-LX2)+IABS(LY1-LY2)
C
C IF THE CONNECTION HAS LENGTH ZERO, RETURN
C
      succes=.true.
      if(MLEN.EQ.0) RETURN
C
C SAVE THE GRID, at the start of the search process
C
  600 CALL SAVE
      MAXL=MLEN+idetou
C
C CLEAR THE TARGET POINT, AND THE POINTS PREVIOUSLY SET TO THE LEFT
C OR THE RIGHT OR ABOVE AND BELOW
C
      CALL UNSET(LX2-IY2,LY2-IX2)
      CALL UNSET(LX2,LY2)
      CALL UNSET(LX2+IY2,LY2+IX2)
      CALL UNSET(LX1-IY1,LY1-IX1)
      CALL UNSET(LX1+IY1,LY1+IX1)
C
C SET THE FOUR POINTS 45 DEGREES RELATIVE TO THE DEPARTURE AND TARGET
C POINT
C
      CALL SET(LX1+1,LY1+1)
      CALL SET(LX1+1,LY1-1)
      CALL SET(LX1-1,LY1+1)
      CALL SET(LX1-1,LY1-1)
      CALL SET(LX2+1,LY2+1)
      CALL SET(LX2+1,LY2-1)
      CALL SET(LX2-1,LY2+1)
      CALL SET(LX2-1,LY2-1)
      I=1
C
C LX and LY are the current coordinates
C
      LX=LX1
      LY=LY1
      NPUNT=0
   10 CONTINUE
      NPUNT=NPUNT+1
C
C NO PATH LONGER THAN 600 STEPS
C
      IF(I.GE.601) GOTO 100
C
C INVESTIGATE NOT MORE THAN 750 POINTS

      IF(NPUNT.GT.750) GOTO 300
C
C search for a possible movement
C
      CALL PRIOR(DIR(I),I,MAXL)
C
C if DIR(I) is negative a connection has been found
C
      IF(DIR(I).LT.0) GOTO 200
C
C if dir equal 0 there is no further movement possible. we have to
C go back.
C
      IF(DIR(I).EQ.0) GOTO 100
C
C FROM THE THIRD MOVE ONWARDS WE MAY GO BACK IN THE OPPOSITE DIRECTION
C COMPARED WITH TWO MOVES AGO, THIS IS ALWAYS UNNECESSARY
C
   11 IF(I.LE.2) GOTO 900
C
C IF THE OPPOSITE DIRECTION OF TWO MOVES AGO IS FOUND: NO PATH
C USING THE LOGICALS AS DIRECT ARGUMENTS TO IABS DOES NOT WORK ALWAYS
C
      IH1=DIR(I)
      IH2=DIR(I-2)
      IF(IABS(IH1-IH2).NE.2) GOTO 900
C
C UNDO THE LAST TWO MOVES
C
      CALL BACK(DIR(I-1))
      CALL BACK(DIR(I-2))
      DIR(I-2)=DIR(I-1)
      MOV=DIR(I-1)
      I=I-2
C
C CONTINUE WITH CHECKING FOR A NEW PIT
C
      GOTO 11
  900 CONTINUE
C
C set the possible movement in the try-out array
C and change the current coordinates
C
      CALL SETM(DIR(I))
      CALL SET(LX,LY)
      MOV=DIR(I)
      I=I+1
      GOTO 10
C
C move back to a previously reached point: move I is not found
C move i-1 has to be reconsidered, for mov(0) we keep the value
C as it is only priority determining
C
  100 I=I-1
      IF(I.LE.0) GOTO 300
      CALL BACK(DIR(I))
      IF(I.NE.1) MOV=DIR(I-1)
      GOTO 10
C
C if the connection is complete the trace is followed from the start and
C drawn, both on the plotter as well as in the board memorygrid.
C
  200 CALL RESTOR
C
C I-1 POINTS TO THE LAST STEP
C
      I=I-1
C
C THE MAXIMUM DETOUR NECESSARY IS EQUAL TO THE DETOUR FOUND
C THIS SPEEDS UP THE SEARCHING FOR THE SHORTEST CONNECTION
C
      imaxde=I-MLEN
      SUCCES=.TRUE.
    3 FORMAT(' Connection:',I4,' No. of points:',I4,' detour=',I4,
     *' length=',I4,' maxdet:',I4)
      WRITE(5,3) Nr,NPUNT,imaxde,I,idetou
C
C no extra search is started for a detour as small as 2
C
      if(imaxde.gt.2) goto 400
C
C LE CONTAINS THE LENGTH OF THE TRACE
C
  500 LE=I
      DIR(I+1)=0
      DIR(I+2)=0
      CALL CONV(LX1,LY1,DIR,NR,LX2,LY2)
      RETURN
  300 WRITE(5,2) NR,NPUNT,idetou
    2 FORMAT(' Connection:',I4,' No. of points:',I4,' maxdet:',I4)
      CALL RESTOR
      succes=.false.
C
C After a detour of 16 a path should have been found, if not, searching
C is stopped
C
      if(idetou.GE.16) RETURN
      iminde=idetou
C
C if we arrive here, a path has been found with detour=iminde. No path has
C been found with idetou=imaxde
C
  400 inieuw=(imaxde+iminde)/2
C
C set inieuw to even
C The number of detours is always even (from is compensated by to)
C which means that if e.g. 6 is not succesful, then 7 will not be too.
C
      inieuw=((inieuw+1)/2)*2
      IF(inieuw.eq.idetou) goto 700
C
C if there is a new number of detours, try again
C
      idetou=inieuw
C
C STOP SEARCHING FOR A NEAREST POINT AFTER THE FIRST TRY
C
      IDIST=-1
      goto 600
C
C if the new number of detours is the same then the search is over
C
  700 if(succes) goto 500
C
C if the search is not succesful, then return
C
      RETURN
      END
      SUBROUTINE SETPAR
C
C SUBROUTINE TO SET SEARCHING PARAMETERS
C
      LOGICAL ZOEKX,ZOEKY,CHAR
      COMMON /DIVPAR/ZOEKX,ZOEKY,NSTEPM
    1 FORMAT(' ENTER MAXIMUM DETOUR: ')
    2 FORMAT(' PRIORITY SEARCH IN X(X), Y(Y) OR NO (N) DIRECTION: ')
    3 FORMAT(I3)
    4 FORMAT(A1)
      WRITE(5,1)
      READ(5,3) NSTEPM
      WRITE(5,2)
      READ(5,4) CHAR
      ZOEKX=CHAR.EQ.88
      ZOEKY=CHAR.EQ.89
      RETURN
      END






UN=CALGO. 
0 
    PF-NAME   CONTENTS
    -------   --------
  
      