Godot A* pathfinding

pathfinding.gd

func grid_to_world(position):
    # (0,8) is the offset to the middle of the tile
    return map_to_world(position) + Vector2(0, 8)

func world_to_grid(position):
    return world_to_map(position)

func get_tile_cost(pos):
    # placeholder
    return 1.0

func get_tile_weighing_category(pos):
    # placeholder
    return 'normal'

func _heap_pop(heap, f_scores):
    # naive O(n) implementation. Only invariant of this function is
    # that it returns the smallest element in the data structure.
    # Can be optimized to an actual heap with O(log n) if it becomes necessary
    var minimum_i = 0
    var current_minimum = 1000000000
    if f_scores.has(heap[0]):
        current_minimum = f_scores[heap[0]]

    for i in range(1, heap.size()):
        var this_score = 1000000000
        if f_scores.has(heap[i]):
            this_score = f_scores[heap[i]]
        if this_score < current_minimum:
            minimum_i = i
            current_minimum = this_score

    var ret = heap[minimum_i]
    heap.remove(minimum_i)
    return ret

func _heap_push(heap, val, f_scores):
    heap.append(val)

func get_neighbors(field):
    var neighbors = []
    for move in [Vector2(-1, 0), Vector2(1, 0), Vector2(0, 1), Vector2(0, -1)]:
        var potential_neighbor = Vector2(int(field.x + move.x), int(field.y + move.y))
        var world_point = grid_to_world(potential_neighbor)
        if (world_point - get_node("WalkMap").get_closest_point(world_point)).length_squared() < 0.1:
            neighbors.append(potential_neighbor)
    return Vector2Array(neighbors)

func _heuristic_score(prev, from, to):
    # a bit of a convoluted heuristic score that punishes taking many turns
    return (to - from).length_squared() * (from - prev).angle_to(to - from)

func calculate_path(from, to, weights={}):
    # Perform an A* to calculate a good way to the target
    # Use WalkMap to check whether a tile is accessible
    # Weights can be used to prefer certain categories of field costs.
    # (I'll document this better later, triple promise!)
    #
    # closely following https://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode
    
    # naively arrays, could be replaced with heaps and search trees in case of performance issues
    var closed = []
    var open = [from]
    var predecessors = {}
    var g_scores = {from: 0}
    var turns = {from: 0}
    var f_scores = {to: (to - from).length_squared()}
    # shackle maximum checking size
    while open.size() > 0 and open.size() < 9999:
        var current = _heap_pop(open, f_scores)
        # if reached the goal, retrace steps
        if (current - to).length_squared() < 0.1:
            var path = []
            var f = to
            while (f - from).length_squared() > 0.1:
                path.insert(0, f)
                f = predecessors[f]
            return Vector2Array([from] + path)
        
        open.erase(current)
        closed.append(current)

        for neighbor in get_neighbors(current):
            # skip checked nodes
            if closed.find(neighbor) > -1:
                continue

            var cost_modifier = 1.0
            var weight_category = get_tile_weighing_category(neighbor)
            if weights.has(weight_category):
                cost_modifier = weights[weight_category]

            var this_turns = turns[current]
            var turn_cost = 0
            if predecessors.has(current):
                turn_cost = abs(sin((current - predecessors[current]).angle_to(neighbor - current)))

            if turn_cost > 0.5:
                this_turns += 1

            var move_cost = get_tile_cost(neighbor)
            var tentative_g_score = g_scores[current] + move_cost * cost_modifier
            tentative_g_score += this_turns * 1.5

            if open.find(neighbor) == -1:
                _heap_push(open, neighbor, f_scores)
            elif tentative_g_score >= g_scores[neighbor]:
                continue # found a worse path
            
            # found a better path
            predecessors[neighbor] = current
            turns[neighbor] = this_turns
            g_scores[neighbor] = tentative_g_score
            f_scores[neighbor] = tentative_g_score + (to - neighbor).length_squared() + turn_cost
        
    return null

Hi Athalean
I have been trying to implement mouse click movement with A* pathfinding in Godot for an isometric game for weeks. But due to lack of much resources/tutorials I am about to give up on this engine when suddenly I came across your post.
How do you use this in your game and what is the "WalkMap" node you refer to? Do you have an example project you can share? thanks

Hi there, to answer your last questions really short, this was for a prototype that is getting superseded so I sadly didn't keep the project around. I posted this snippet on a reddit post once and the gist itself is missing a bit of context, so I'll try to explain a bit what's going on. So this isn't a "traditional" pathfinding algorithm because I had the very specific use case of making a game which is completely built around an isometric grid (think Civ games or the old Fallout games). You can see there's a `get_neighbours` method whose sole purpose is to find out which fields are next to one on the grid, and the pathfinding only really made sense that way in the game. I designed the map with a TileMap (that's the node that this script is attached to) with a `Navigation2D` on top (which is what `WalkMap` is). The `Navigation2D` has a couple `NavigationPolygon` on it. Here's a good tutorial on the topic which works if you don't work with a `TileMap` or want the navigation to be separate on top of the TileMap (like I did): https://www.youtube.com/watch?v=b7rhFPcj230 - essentially I need this to call `get_closest_point` and figure out what is on and off the walk map. I also highly recommend GDQuest's tutorial (all of their tutorials actually) on this topic which is on more modern versions of the engine: https://www.youtube.com/watch?v=0fPOt0Jw52s They even made one on the new AStar implementation that shipped with Godot 3.0 and after (which wasn't available when I wrote this): https://www.youtube.com/watch?v=Ad6Us73smNs Hope this helps!

Thanks Athalean. As i am a hobbyist game developer, I am finding it difficult to apply the GDquest Astar video (which I have already seen) to an isometric grid. Do we need to alter mathematics there or just apply as is?
I also stumbled across the following, very easy to understand tutoral for a 2d path follow.. I implemented it to an isometric grid. It works to some extent when I click the mouse but I cannot seem to get the co-ordinates right. Any help would be great if you are free. Thanks

https://medium.com/kitschdigital/2d-path-finding-with-astar-in-godot-3-0-7810a355905a

The mathematics stay pretty much the same. A* is a graph algorithm for a weighted graph, and a weighted graph is nothing more than a set of points of which some can be connected and where every connection has a distance value, whether that's coordinates on a screen or cities on a map or something more abstract.

The AStar implementation in Godot does it for 3D coordinates (you can use 2D coordinates there if you always set the last number to 0) and you can treat it like a box that you tell what the world looks like and ask it questions which it then answers really fast. You can see it even models that concept of "set of points" and "connections" as you can see by the AStar class having add_point and connect_points in the documentation (https://docs.godotengine.org/en/3.1/classes/class_astar.html). That means it's flexible since you can put in basically anything but you also gotta tell it which points you're interested in. The article you linked basically describes what I'd do, with the exception that I'd use world_to_pos and pos_to_world to convert between on-screen coordinates to map coordinates and back.
You probably want this to sit in its own object that deals with game logic in general, but no matter how you structure it, you're most probably gonna do two things:

1. Tell the object the "logical" coordinates that any actor can even go to (depending on what your map looks like, but you can probably find some helpful methods on TileMap → https://docs.godotengine.org/en/3.1/classes/class_tilemap.html)
2. Whenever an actor moves, run get_point_path and use the result in your game logic somehow (for example by saving it on an actor so they move there)

I hope this helps - I think the specifics will depend on your game, but this is as far as Godot goes for off-the-shelf solutions. My best advise for next things to do is look into more tutorials on TileMap or try to work out from the snippet how you can build a graph of possible movements on a TileMap. Or maybe your game allows you to get away by just using a Navigation2D instead like in the first tutorial.

Again Thanks for the explanation. Over the next few days I will do as you have advised and see what results I get.