script, find route, tile, dest, ignore walls=false, begin
  # Stores return value in the "route" fake array
  clear astar parents
  clear array(route)
  clear array(astar open)
  clear array(astar closed)
  do find route(tile, dest, ignore walls)
end

script, clear astar parents, begin
  for each tile(@do clear astar parents)
end

script, do clear astar parents, tile, begin
  set tile astar parent(tile, 0)
end

script, confirm route, tile, begin
  prepend(route, tile)
  variable(parent)
  parent := get tile astar parent(tile)
  if(parent) then(
    confirm route(parent)
  )
end

script, do find route, tile, dest, ignore walls=false, begin
  if(tile == dest) then(
    # Found destination! copy it into the route
    confirm route(dest)
    exit script
  )
  append(astar closed, tile)
  variable(x, y)
  x := x for tile(tile)
  y := y for tile(tile)
  variable(i, ax, ay, other tile)
  for(i, 0, 5) do(
    ax := x + hex around x(i)
    ay := y + hex around y(i)
    if(ax < 0 || ay < 0 || ax >= gridsize || ay >= gridsize) then(
      continue
    )
    other tile := get tile at(ax, ay)
    if(in array(astar open, other tile)) then(
      check if new route is better(other tile, tile)
      continue
    )
    if(in array(astar closed, other tile)) then(
      continue
    )
    if(ignore walls || tile is passable for route(other tile, dest)) then(
      set tile astar parent(other tile, tile)
      append(astar open, other tile)
    )
  )
  if(array length(astar open) == 0) then(
    # no more tiles on the open list
    #script error(string sprintf(0, $1="Open list is empty, no route found yet"))
    exit script
  )
  for each in array set sort order(astar open, @update astar sort order, dest)
  sort children(astar open, true)
  variable(best)
  best := get slice extra(first child(astar open), 0)
  drop(astar open, best)
  do find route(best, dest, ignore walls)
end

script, update astar sort order, tile, dest, begin
  variable(known cost, guessed cost)
  known cost := calc known cost(tile)
  guessed cost := hexmanhattan distance(tile, dest) * tilecost
  exit returning(known cost + guessed cost)
end

script, check if new route is better, old open tile, new parent, begin
  variable(old cost)
  old cost := calc known cost(old open tile)
  variable(new cost)
  new cost := calc known cost(new parent) + tilecost
  if(new cost < old cost) then(
    set tile astar parent(old open tile, new parent)
  )
end

script, calc known cost, tile, begin
  if(not(tile)) then(
    script error(string sprintf(0, $1="null tile in calc known cost"))
  )
  variable(from)
  from := get tile astar parent(tile)

  # No parent, return a cost of 1
  if(not(from)) then(exit returning(tilecost))

  exit returning(tilecost + calc known cost(from))
end

script, hexmanhattan distance, t1, t2, begin
  variable(x1, y1, x2, y2)
  x1 := x for tile(t1)
  y1 := y for tile(t1)
  x2 := x for tile(t2)
  y2 := y for tile(t2)
  variable(xd, yd)
  xd := x1 -- x2
  yd := y1 -- y2
  if(cmp(xd, 0) == cmp(yd, 0)) then(
    exit returning(abs(xd + yd))
  )else(
    exit returning(large(abs(xd), abs(yd)))
  )
end

script, hexmanhattan unit distance, u1, u2, begin
  exit returning(hexmanhattan distance(unit tile(u1), unit tile(u2)))
end

script, set tile astar parent, tile, parent, begin
  set slice extra(tile, 2, parent)
end

script, get tile astar parent, tile, begin
  exit returning(get slice extra(tile, 2))
end

#-----------------------------------------------------------------------

script, find move range, tile, dist, begin
  # Stores return value in the "move range" fake array
  clear array(move range)
  do find move range(tile, dist, 0)
end

script, do find move range, tile, dist, step, begin
  if(step > dist) then(
    exit script
  )
  if(not(in array(move range, tile))) then(
    append(move range, tile)
  )

  if(step > 0 && tile unit(tile)) then(
    # A unit is standing here, don't continue range searching from this tile
    exit script
  )

  variable(x, y)
  x := x for tile(tile)
  y := y for tile(tile)

  variable(i, ax, ay, other tile)
  for(i, 0, 5) do(
    ax := x + hex around x(i)
    ay := y + hex around y(i)
    if(ax < 0 || ay < 0 || ax > gridsize || ay > gridsize) then(
      continue
    )
    other tile := get tile at(ax, ay)
    if(tile is passable for range(other tile, dist, step)) then(
      do find move range(other tile, dist, step + 1)
    )
  )
end

#-----------------------------------------------------------------------

script, find dash range, from tile, dist, begin
  clear array(move range)
  variable(tile, x, y, ax, ay, i, j)
  x := x for tile(from tile)
  y := y for tile(from tile)
  for(i, 0, 5) do(
    for(j, 1, dist) do(
      ax := x + hex around x(i) * j
      ay := y + hex around y(i) * j
      tile := get tile at(ax, ay)
      if(tile is passable for route(tile, 0)) then(
        append(move range, tile)
      )else(
        break
      )
    )
  )
end

script, find best dash, from tile, to tile, dist, begin
  # Uses astar closed for a list of valid dash end-points
  clear array(astar closed)
  variable(tile, x, y, ax, ay, i, j)
  x := x for tile(from tile)
  y := y for tile(from tile)
  for(i, 0, 5) do(
    # Uses astar open for a list of tiles in the currently tested dash
    clear array(astar open)
    for(j, 1, dist) do(
      ax := x + hex around x(i) * j
      ay := y + hex around y(i) * j
      tile := get tile at(ax, ay)
      if(tile == to tile) then(exit returning(to tile))
      if(tile is passable for route(tile, to tile)) then(
        append(astar open, tile)
      )else(
        break
      )
    )
    if(array length(astar open)) then(
      append(astar closed, fetch last(astar open))
    )
  )
  if(array length(astar closed) == 0) then(exit returning(0))
  for each in array set sort order(astar closed, @sort dash, to tile)
  sort children(astar closed, true)
  exit returning(fetch(astar closed, 0))
end

script, sort dash, tile, to tile, begin
  variable(n)
  # Main sort key is hexmanhattan distance
  n := hexmanhattan distance(tile, to tile) * 100000
  # Second sort key is pixel dist squared
  n += dist squared(tile, to tile)
  exit returning(n)
end

#-----------------------------------------------------------------------

script, tile is passable, tile, begin
  if(not(tile)) then(exit returning(false))
  variable(unit)
  unit := tile unit(tile)
  if(unit) then(
    if(get unit inert(tile)) then(exit returning(false))
  )
  variable(k)
  k := get tilekind(tile)
  switch(k) do(
    case(tile:void) exit returning(true)
    case(tile:snow) exit returning(true)
  )
  exit returning(false)
end

script, tile is passable for route, tile, dest, begin
  if(not(tile)) then(exit returning(false))
  if(tile == dest) then(exit returning(true))
  if(tile unit(tile)) then(exit returning(false))
  exit returning(tile is passable(tile))
end

script, tile is passable for range, tile, dist, step, begin
  if(not(tile)) then(exit returning(false))
  exit returning(tile is passable(tile))
end