pathfind old code, should work still though

"""
Grid Based Pathfinder similar to Dijkstra
Steps:
    -searches outwards from the start to find a match to conditions
    -follows back from the target to produce coordinates
    -trims the results backwards removing coordinates in line with each other
    
by Richard Ellicott
I provide this code CC0 (completely free):
https://creativecommons.org/share-your-work/public-domain/cc0/
(no attribution required)


however if you tidy it up for me and re-post it, please drop me a mention and lemme know what u did with it ;)


"""


tool
extends Node
class_name ee10_TileMapPathfinder


export var tool_update = false setget set_tool_update
func set_tool_update(new_value):
    tool_update = new_value
    if tool_update:
        tool_update()
        tool_update = false


func tool_update():
    _ready() # ensure vars are available
    print(self, "run tool_update functions here...")

export var debug = true

export var auto_update = false

export(NodePath) var _tile_map
onready var tile_map = get_node(_tile_map)

export(NodePath) var _debug_tile_map
onready var debug_tile_map = get_node(_debug_tile_map)


export(NodePath) var _path2D
onready var path2D = get_node(_path2D)


enum Mode {
    find_nearest_int,
    find_coordinates,
    island_scan,
    }

export(Mode) var mode = Mode.find_nearest_int

#export var x_start = 0
#export var y_start = 0

export var start_coor = Vector2()
export var target_coor = Vector2(16,16)

export var target_int = 1

#export var target_x = 16
#export var target_y = 16

export var search_ttl = 512


func match_conditions (x,y,tile_val):
    var target_x = int(target_coor.x)
    var target_y = int(target_coor.y)

    match mode:
        Mode.find_nearest_int:
            return tile_val == target_int
        Mode.find_coordinates:
            return x == target_x and y == target_y

enum Translations {
    cardinal4,
    diagonal8,
   }

export(Translations) var translations = Translations.cardinal4


export var grid_trim_interpolated_path_positions = false
export var grid_cardinal_trim_path_positions = false






var block_cells = [-1] # set for island check on rails (also rail pathfinds)
#var block_cells = range(10)

var cardinal4_translations = [
        [0,-1], #N
        [1,0], #E
        [0,1], #S
        [-1,0], #W
#        [1,-1], #NE
#        [1,1], #SE
#        [-1,1], #SW
#        [-1,-1], #NW
        ]

var diagonal8_translations = [
        [0,-1], #N
        [1,0], #E
        [0,1], #S
        [-1,0], #W
        [1,-1], #NE
        [1,1], #SE
        [-1,1], #SW
        [-1,-1], #NW
        ]

func get_translations():
    match translations:
        Translations.cardinal4:
            return cardinal4_translations
        Translations.diagonal8:
            return diagonal8_translations


func pathfind():



    var x_start = int(start_coor.x)
    var y_start = int(start_coor.y)

    # all the valid "moves" the pathfinder can make
    var current_translations = get_translations()

    var search_cell_tile_map = TileMap.new() # map for search data

    if debug and is_instance_valid(debug_tile_map):
        debug_tile_map.clear()
        debug_tile_map.cell_size = tile_map.cell_size

    var to_search_cells = [] # cells to be checked

    to_search_cells.append([x_start,y_start,0]) # seed with start

    var ttl = search_ttl # make cells to check

    var result = false # sucess in finding target

    var path_positions = [] # waypoints to target

    while to_search_cells.size() > 0 and ttl > 0:
        ttl -= 1

        var current_cell = to_search_cells.pop_front()

        var x = current_cell[0]
        var y = current_cell[1]

        var n = current_cell[2] + 1

        var cell_val = tile_map.get_cell(x,y)
        var search_cell_val = search_cell_tile_map.get_cell(x,y)

        if match_conditions(x,y,cell_val):
            result = true
            path_positions.append([x,y,n])
            break


        var cell_unblocked = true

        if cell_val in block_cells:
            cell_unblocked = false



        if cell_unblocked and search_cell_val  == -1:

            search_cell_tile_map.set_cell(x,y,n)
            if debug:
                debug_tile_map.set_cell(x,y,0)

            for trans in current_translations:
                to_search_cells.append([x+trans[0],y+trans[1],n]) # N


    if result:

        ttl = 1000
        while ttl > 0:
            ttl -= 1

            var current_pos = path_positions.back()
            var x = current_pos[0]
            var y = current_pos[1]
            var n = current_pos[2]

            if n == 1: # found last cell
                break

            for trans in current_translations:
                if search_cell_tile_map.get_cell(x+trans[0],y+trans[1]) == n - 1:
                    path_positions.push_back([x+trans[0],y+trans[1],n - 1])
                    break



    if debug and is_instance_valid(debug_tile_map):
        for pos in path_positions:
            debug_tile_map.set_cell(pos[0],pos[1],1)

    debug_tile_map.set_cell(start_coor.x,start_coor.y,5)


    if grid_trim_interpolated_path_positions:
        path_positions =_grid_trim_interpolated_path_positions(path_positions)

    if grid_cardinal_trim_path_positions:
        _grid_cardinal_trim_path_positions(path_positions)



    if debug and is_instance_valid(debug_tile_map):
        for pos in path_positions:
            debug_tile_map.set_cell(pos[0],pos[1],2)

    return path_positions



func pathfind_state_based_test():
    """
    copy of old one, working to dictionary state based on for train
    DEVELOP THIS ONE TO USE DICTIONARY ONLY, for performance comparison
    """


    var x_start = int(start_coor.x)
    var y_start = int(start_coor.y)

    # all the valid "moves" the pathfinder can make
    var current_translations = get_translations()

    var search_cell_tile_map = TileMap.new() # map for search data
    var search_cell_dictionary = {}

    if debug and is_instance_valid(debug_tile_map):
        debug_tile_map.clear()
        debug_tile_map.cell_size = tile_map.cell_size

    var to_search_cells = [] # cells to be checked

    to_search_cells.append([x_start,y_start,0]) # seed with start

    var ttl = search_ttl # make cells to check

    var result = false # sucess in finding target

    var path_positions = [] # waypoints to target

    while to_search_cells.size() > 0 and ttl > 0:
        ttl -= 1

        var current_cell = to_search_cells.pop_front()

        var x = current_cell[0]
        var y = current_cell[1]

        var n = current_cell[2] + 1

        var cell_val = tile_map.get_cell(x,y)
        var search_cell_val = search_cell_tile_map.get_cell(x,y)

        if match_conditions(x,y,cell_val):
            result = true
            path_positions.append([x,y,n])
            break


        var cell_unblocked = true

        if cell_val in block_cells:
            cell_unblocked = false



        if cell_unblocked and search_cell_val  == -1:

            search_cell_tile_map.set_cell(x,y,n)
            if debug:
                debug_tile_map.set_cell(x,y,0)

            for trans in current_translations:
                to_search_cells.append([x+trans[0],y+trans[1],n]) # N


    if result:

        ttl = 1000
        while ttl > 0:
            ttl -= 1

            var current_pos = path_positions.back()
            var x = current_pos[0]
            var y = current_pos[1]
            var n = current_pos[2]

            if n == 1: # found last cell
                break

            for trans in current_translations:
                if search_cell_tile_map.get_cell(x+trans[0],y+trans[1]) == n - 1:
                    path_positions.push_back([x+trans[0],y+trans[1],n - 1])
                    break



    if debug and is_instance_valid(debug_tile_map):
        for pos in path_positions:
            debug_tile_map.set_cell(pos[0],pos[1],1)

    debug_tile_map.set_cell(start_coor.x,start_coor.y,5)


    if grid_trim_interpolated_path_positions:
        path_positions =_grid_trim_interpolated_path_positions(path_positions)

    if grid_cardinal_trim_path_positions:
        _grid_cardinal_trim_path_positions(path_positions)



    if debug and is_instance_valid(debug_tile_map):
        for pos in path_positions:
            debug_tile_map.set_cell(pos[0],pos[1],2)

    return path_positions



func _grid_cardinal_trim_path_positions(path_positions):
    # trims unnecessary coordinates for grid movement
    # WARNING, does not duplicate the list!

    # for example:
    # 6 tiles line up in the y axis
    # 4 tiles in between them will be deleted

    var continuous_x_run = 0
    var continuous_y_run = 0

    #HACKY!, add dummy position
    path_positions.push_front([null,null])

    var last_x # last x we checked
    var last_y

    var n = path_positions.size()

#    print('path_positions size:', n)

    #WARNING CHANGED X1 "n > 0" to "n >= 0"
    while n > 0: # we iterate backwards to allow deleting while we go
        n -= 1
        var pos = path_positions[n]
#        print("path_positions ", n, " ", pos)
        if last_x == pos[0]: # last pos on same x
            continuous_x_run += 1
        else:
            if continuous_x_run > 0: # means we have a run
#                    print('continuous_x_run: ', continuous_x_run)
                for n2 in continuous_x_run - 1:
                    path_positions.remove(n+2) # note we delete two positions back from this point
                continuous_x_run = 0

        if last_y == pos[1]: # last pos on same y
            continuous_y_run += 1
        else:
            if continuous_y_run > 0: # means we have a run
#                    print('continuous_y_run: ', continuous_y_run)
                for n2 in continuous_y_run - 1:
                    path_positions.remove(n+2) # note we delete two positions back from this point
                continuous_y_run = 0

        last_x = pos[0]
        last_y = pos[1]

    path_positions.pop_front() # remove dummy position


func my_interpolated_line(start, end = null):

    # MODDED SINCE SNIPPETS, stops checking is start == end
    # which may have thrown a divide error

    if start is Rect2: # overload Rect2
        end = start.size
        start = start.position

    if start is Array: # overload, convert lists like [0,4]
        start = Vector2(start[0],start[1])
    if end is Array:
        end = Vector2(end[0],end[1])

    var points = PoolVector2Array()

    if start == end:
        points.append(start)
        return points
    else:
        var dx = end.x - start.x
        var dy = end.y - start.y
        var N = max(abs(dx), abs(dy))
        for i in N + 1:
            var t = float(i) / float(N)
            points.append(Vector2(round(lerp(start.x, end.x, t)),
                round(lerp(start.y, end.y, t))
            ))
        return points


func check_los(start_pos, end_pos):
    # TESTED WORKING

    var line = my_interpolated_line(start_pos, end_pos)

    var clear = true
    for pos in line:
        if tile_map.get_cell(pos.x,pos.y) != -1:
            clear = false
            break
    return clear






func remove_nulls(input_array):

    print("in remove nulls...A")


    # returns a new list with all the nulls removed
    # i.e [1,2,null,3,null,4] => [1,2,3,4]
    # for usage of lua nulls style pattern
    # the return array is only resized a few times for speed

    var ret = [] # fresh array
    ret.resize(input_array.size()) # set to max possible size
    var n = 0 # current reference
    for i in range(input_array.size()):
        var val = input_array[i]
        if val != null:
            ret[n] = val
            n += 1
    ret.resize(n) # chop array to final size

    print("in remove nulls...B")

    return ret


func cancel_inter_from_pos(path_positions, start_pos_index, ttl = 128):

    """
    currently functioning to detect points
    something not working
    keeping function seperate
    """



    var target_pos_index = start_pos_index + 2

    var exit = false

    var sucess_count = 0

    var start_pos = path_positions[start_pos_index]

    while not exit:

        if target_pos_index >= path_positions.size():
            exit = true
            break

        var target_pos = path_positions[target_pos_index]


        var sucess = false

        if start_pos == null or target_pos == null:
            break # break

        if check_los (start_pos, target_pos):
            sucess = true
            sucess_count += 1
        else:
            exit = true

#        print("check positions", start_pos," ", target_pos, " ", sucess)

        target_pos_index += 1
#        exit = true

#    print("sucess count: ", sucess_count)

    if sucess_count > 0:
        for i in sucess_count - 1:
            print('try null')
            path_positions[start_pos_index + 1 + i] = null
            pass
        pass

    path_positions = remove_nulls(path_positions)

#    print("new possi" , path_positions)

    return path_positions # HACKY!



func _grid_trim_interpolated_path_positions(path_positions):

    # introducing a new pattern, making nulls instead of resizing array
    # hopefully to improve speed (later maybe)

    var ret = path_positions.duplicate()

#    cancel_inter_from_pos(ret, 0)


    for i in range(path_positions.size()):

        if i >= path_positions.size():
            break

#        print('try removing lines..')

        var pos = path_positions[i]

#        print('pos:', pos)

        if pos != null:
#            print("sss", ret)
            cancel_inter_from_pos(ret,i)

        pass


    print('POINT2')


    ret = remove_nulls(ret)
    return ret





func path_positions_to_curve(search_path, curve):

    #currently backwards

    print("GEN CURVE")
    print(search_path)

    var cell_size = tile_map.cell_size

    var n = search_path.size()
    while n > 0:
        n -= 1
        var pos = search_path[n]
        curve.add_point(
            Vector2(pos[0]*cell_size.x+cell_size.x/2.0,pos[1]*cell_size.y+cell_size.y/2.0)
            )
    return curve


var _island_scan_cache_tilemap





func island_scan():
    """
    scan for seperate islands, isolated parts of the map
    """

    print("island_scan()...")

    if not _island_scan_cache_tilemap:
        _island_scan_cache_tilemap = TileMap.new()
    var search_cell_tile_map = _island_scan_cache_tilemap # map for search data
    search_cell_tile_map.clear()

    var used_cells = tile_map.get_used_cells() # we try floodfill on all used cells

    var island_count = 0

    # all the valid "moves" the pathfinder can make
    var current_translations = get_translations()

    if debug and is_instance_valid(debug_tile_map):
        debug_tile_map.clear()
        debug_tile_map.cell_size = tile_map.cell_size

    var ttl = search_ttl * 128 # make cells to check

    for start_cell in used_cells:

        var island_size_count = 0

        var to_search_cells = [] # cells to be checked

        to_search_cells.append([int(start_cell.x),int(start_cell.y),0]) # seed with start

        while to_search_cells.size() > 0 and ttl > 0:
            ttl -= 1

            var current_cell = to_search_cells.pop_front()

            var x = current_cell[0]
            var y = current_cell[1]

            var n = current_cell[2] + 1

            var cell_val = tile_map.get_cell(x,y)
            var search_cell_val = search_cell_tile_map.get_cell(x,y)

            if search_cell_val == -1:
                island_size_count += 1

            var cell_unblocked = true
            if cell_val in block_cells:
                cell_unblocked = false

            if cell_unblocked and search_cell_val  == -1:

                search_cell_tile_map.set_cell(x,y,island_count)
                if debug:
                    debug_tile_map.set_cell(x,y,island_count)

                for trans in current_translations:
                    to_search_cells.append([x+trans[0],y+trans[1],n]) # N

        if island_size_count > 0:
            island_count += 1
            print("found island %s size: %s" % [island_count,island_size_count])

    return search_cell_tile_map # maybe use this


func _ready():
#    print(self, "_ready...")


    match mode:
        Mode.island_scan:

#            print("HSHS")
            island_scan()



    if mode >= 0 and mode <= 1: # modes 0 or 1 pathfind

#        var search_path = pathfind()
        var search_path = pathfind_state_based_test()



        if is_instance_valid(path2D):

            if not is_instance_valid(path2D.curve):
                path2D.curve = Curve2D.new()

            path2D.curve.clear_points()
            path2D.curve = path_positions_to_curve(search_path,path2D.curve)

        print('found coors: ', search_path)





var timer = 0.0
var delay = 2.0

func _process(delta):
    timer += delta
    if timer > delay:
        timer -= delay
        if auto_update:
            _ready()

    pass