0 votes

I'm only just learning pathfinding. I have followed the instructions at GeeksForGeeks and gotten the following code working for printing the fastest path to a given point. The issue is that it works and is instant for any close-by tiles, but for for anything starting at around 12 tiles away and further, it starts to slow down significantly and anything much further just makes Godot stop responding...

Can someone a little smarter than me help me figure out what the slow down is and how I can optimize this code?

Basically, I have a tilemap with coordinates starting at (0, 0) at the top left. On the map, when I click anywhere with my mouse, I have a function called get_tile that returns the tile coordinates for the tile clicked on. As you can see, find_path is supposed to then return the quickest path from (0, 0) to the tile clicked on. As per the Geeks for Geeks article, g is the movement cost from (0, 0) to the node, h is the movement cost from the node to the destination, and f is the sum of the two.

I'm using a dictionary to represent each tile node because I had problems with building a class.

How can I speed things up for greater distances?

extends Node2D


func _input(event):
    if event.is_action_pressed("click"):
        print(find_path(Vector2(0, 0), get_tile(event.position)))


func find_path(starting_pos, ending_pos):
    var open = []
    var closed = []

    var root = {}
    construct_tile_node(root, null, starting_pos, ending_pos)
    open.append(root)

    while open.size() > 0:
        var lowest_f = open[0]
        for tile_node in open:
            if tile_node.f < lowest_f.f:
                lowest_f = tile_node

        var q = open.pop_at(open.find(lowest_f, 0))

        var successors = get_tile_node_successors(q, ending_pos)
        for successor in successors:
            if successor.location == ending_pos:
                return pull_path_coordinates(successor)
            else:
                var add_to_open = true
                for tile_node in open:
                    if tile_node.location == successor.location and tile_node.f < successor.f:
                        add_to_open = false
                if add_to_open:
                    for tile_node in closed:
                        if tile_node.location == successor.location and tile_node.f < successor.f:
                            add_to_open = false
                if add_to_open:
                    open.append(successor)
        closed.append(q)
    return null


func construct_tile_node(dict, parent, location, ending_pos):
    dict.parent = parent
    dict.location = location
    if parent != null:
        dict.g = Game.Utils.sharp_distance(parent.location, location) + parent.g
        dict.h = Game.Utils.sharp_distance(location, ending_pos)
        dict.f = dict.g + dict.h
    else:
        dict.g = 0
        dict.h = 0
        dict.f = 0


func get_tile_node_successors(tile_node, ending_pos):
    var temp_nodes = []
    var successors = []
    temp_nodes.append(tile_node.location - Vector2(1, 0))
    temp_nodes.append(tile_node.location + Vector2(1, 0))
    temp_nodes.append(tile_node.location - Vector2(0, 1))
    temp_nodes.append(tile_node.location + Vector2(0, 1))

    for tile_position in temp_nodes:
        if Game.is_in_bounds(tile_position):
            var new_tile_node = {}
            construct_tile_node(new_tile_node, tile_node, tile_position, ending_pos)
            successors.append(new_tile_node)

    return successors


func pull_path_coordinates(leaf_node):
    var path = []
    while true:
        path.append(leaf_node.location)
        if leaf_node.parent == null:
            break
        leaf_node = leaf_node.parent
    path.invert()
    return path
Godot version 3.4.2
in Engine by (75 points)

1 Answer

0 votes
Best answer

Well using a dictionary will not be fast enough for this but to be honest I would suggest you look into the A* class in godot.

Documentation here

https://docs.godotengine.org/ko/latest/classes/class_astar.html

basically you are trying to recreate a function which already exists in godot. The A* class in godot can do the pathfinding for you.

by (1,635 points)
selected by

Yes fully agree with you.

You've heard it said a million times before and will say it once more. Do not reinvent the wheel. Build upon it.

The A* class can be extended to accommodate all you have above.

It's also obvious why it gets slower as you extend outward as aStar calculates all possible nodes

Wonderful, thank you so much for providing this info! Not only will this work much better, but I'm sure it'll help me clean up my code, haha!

Honestly, I would like to understand the algorithm better, personally, and would like to look into how I can optimize what I've got, but for now this class is definitely a better alternative. Thank you!

Understand the need for speed and you're walking down a road others have already walked before.
Depending on your end goal there are a couple of tricks you can use for optimization.

  • Break the path up into smaller from-to positions
  • Use obstacles and precalculate boundaries
  • Use a chunk system or divide using sets

It's good to look under the hood but the time it takes to tear things apart you could have finished more projects

Welcome to Godot Engine Q&A, where you can ask questions and receive answers from other members of the community.

Please make sure to read How to use this Q&A? before posting your first questions.
Social login is currently unavailable. If you've previously logged in with a Facebook or GitHub account, use the I forgot my password link in the login box to set a password for your account. If you still can't access your account, send an email to webmaster@godotengine.org with your username.