find_closest_coordinate

find_closest:
;Input:
;   HL points to an array of coordinates
;   DE = (x0,y0), the point to compare
;   B is the number of elements to search
;Output:
;   A is the closest element
;   C = B-C, with 'B' being the input 'B'
;   IX is (distance^2)>>1
;0 elements : 40cc
;if last element is closest, +12cc
;64+n*(252+2*{0,3}+2*C_Times_C+{20,{0,11+{0,22}{p0,1-p0}}{p1,1-p1}}{p2,1-p2})
;p0 is the probability that our new candidate is definitely closer
;p1 is the probability that our new candidates adjusted distance is equal to the current candidate
;p2 is the probability that, if the adjusted distances are equal, our candidate had odd distance (before adjustment)
;min: 64+n*640
;max: 64+n*783
;avg: 64+n*720.4    ;Determined with probabilistic methods, no clue on precision, but probably +-.05

; Initialize C to 0
    ld c,0

; Initialize "closest" distance
    ld ix,-1

; First we'll play it safe and verify that B!=0
    inc b
    dec b
    ret z

; Save B for the end adjustment
    push bc

; Begin the loop
find_closest_loop:
    push bc   ;save the counter
    ; Load the next coordinates, but find the absolute value
    ; of their differences from the input coords
    ld a,e
    sub (hl)
    jr nc,+_
    neg
_:
    ld c,a
    inc hl

    ld a,d
    sub (hl)
    jr nc,+_
    neg
_:
    ld b,a
    inc hl

; BC is the adjusted coordinates,
; HL is the pointer to the next coordinate
    push hl

; Now we need to compute B^2 + C^2
  ld a,b
  call C_Times_C
  ex de,hl         ;C^2
  ld c,a
  call C_Times_C

  ; This might overflow, so we are going to shift right,
  ;losing information in the bottom bit :/
  xor a
  add hl,de
  rr h
  rr l
  rra   ;save the carry, but reset carry flag for next sbc

  ; If no carry, and HL<=IX, then this is a guaranteed
  ;candidate for closest.
  ; If the carry flag is set and HL==IX, do not select
  ;this coordinate

  ld b,ixh
  ld c,ixl
  sbc hl,bc

  ;if carry, then definitely select this candidate
  jr c,select_new_candidate

  ;If they are not equal, keep searching
  jr nz,find_next_candidate

  ;Otherwise, they are equal. If top bit of A is reset,
  ;select as the candidate
  rla
  jr c,find_next_candidate

select_new_candidate:
  ld b,h
  ld c,l
  add ix,bc
  pop hl
  pop bc
  ld c,b
  djnz find_closest_loop
  jr +_

find_next_candidate:
  pop hl
  pop bc
  djnz find_closest_loop

_:
; Gotta finalize!
; We actually want A = B-C
  pop af
  sub c
  ret


C_Times_C:
;min: 194cc
;max: 246cc
;avg: 220cc
  ld h,c
H_Times_C:
;min: 190cc
;max: 242cc
;avg: 216cc
  ld b,0
  ld l,b
  sla h \ jr nc,$+3 \ ld l,c
  add hl,hl \ jr nc,$+3 \ add hl,bc
  add hl,hl \ jr nc,$+3 \ add hl,bc
  add hl,hl \ jr nc,$+3 \ add hl,bc
  add hl,hl \ jr nc,$+3 \ add hl,bc
  add hl,hl \ jr nc,$+3 \ add hl,bc
  add hl,hl \ jr nc,$+3 \ add hl,bc
  add hl,hl \ ret nc \ add hl,bc \ ret