0 votes

Hello Everyone,

so this is my first question here, but i already learned a lot just reading your answers.
Iam quite new to Godot-Engine and iam quite insecure about my choices.

So now i did a well working AStar Script for my Top-Down Prototype, but i realized that the distance squared heuristik is not optimal for me ( not optimal paths, not really considering paths that are parallel and thus not even considered).

not really optimal path

I tried changing my H to different other approaches like 0 for a Dijkstra Algorithm and after that to a lot of other heuristiks but Godot just freezes if i try that.

however - it works if it is something very straight (fast) (here is a X+Y Distance as heuristik)

straight path

or very near (that already did a small "hiccup"

minimal y offset

But every offset in y direction makes it considerably "hiccup".and if too much (meaning like 10 tiles) the application just freezes

so iam looking for a Problem in my Algorithm like a ressource-hog or a memory limitation i did not count in.

I tried debugging it with labels and the good old print, but if it "hangs" its not printing anything at all (probably because its updating the "print" after it finished that run).
I then tried debugging it with returns and breakpoints - but that works well as far as i can click "next".

My assumption is that by changing the heuristic, its considering way more points thus crashing - this leady me to my "findInArray" function - is there a problem?
... but it can do long routes (horizontally) and its also breaking on short ones. I cant spot the problem.

Can you help me identifiy that problem?

Here is my Source code of the AStar:

openList.append({"parentPos" : null, "position" : sourceLocationInArray,"gValue" : 0,"hValue" : 0,"fValue" : 0})

var movementCost:float = 0
var childGValue:float = 0
var childHValue:float = 0
var childFValue:float = 0


while !openList.empty():

    #find item in openList with smallest F
    var currentNode = openList[0]
    #print_debug(str(currentNode))

    var ii = 0;
    var iToDel = 0;
    for item in openList:
        if item['fValue'] < currentNode['fValue']:
            #print(str(item['fValue']) + " " + str(currentNode['fValue']) )
            currentNode = item;
            iToDel = ii;
        ii += 1;

    #remove currentNode from open List, Add to closedList
    openList.remove(iToDel)
    closedList.append(currentNode)
    #environmentMap.set_cellv(currentNode['position'], 1)
    #print("closed List now:")
    #print(str(closedList))

    if currentNode["position"] == destinationLocationInArray:
        #follow path reverse
        while currentNode != null:
            #print_debug(str(openList));
            movementRoute.append(environmentMap.map_to_world(currentNode["position"]));
            currentNode = findInArray(closedList, "position", currentNode["parentPos"])
        break

    #generate Children
    var children = []
    for newPosition in [    Vector2(0, -1), Vector2(0, 1), Vector2(-1, 0), Vector2(1, 0)
                        ]:
        var childPosition = currentNode['position'] + newPosition

        if environmentMap.get_cellv(childPosition) <= 0:
            continue;

        #in der closedList nachschauen ob schon vorhanden
        if findInArray(closedList, "position", childPosition) != null:
            continue


        # Create the f, g, and h values
        #movementCost
        movementCost = environmentMap.get_cellv(childPosition)/float(pathingGridIndexOffset)

        #print(newPosition.length() * movementCost)
        childGValue = currentNode["gValue"] + newPosition.length() * movementCost;
        childHValue = childPosition.distance_to(destinationLocationInArray)
        #childPosition.distance_to(destinationLocationInArray);
        childFValue = childGValue + childHValue
        envDebug(childPosition, int(childGValue*10)/10.0, "0_0")
        #envDebug(childPosition, int(childHValue*10)/10.0, "0_1")
        #in der open List schauen ob diese Position schon mit einem schlechteren G Wert vorhanden ist
        var existingItemInOpenList = findInArray(openList, "position", childPosition)           
        if existingItemInOpenList != null:
            if childGValue < existingItemInOpenList['gValue']:
                existingItemInOpenList['gValue'] = childGValue;
                existingItemInOpenList['parentPos'] = currentNode['position'];
                continue
        #in der closed List schauen ob die Position schon mit einem schlechteren G Wert vorhanden ist
        var existingItemInClosedList = findInArray(closedList, "position", childPosition)
        if existingItemInClosedList != null:
            if childGValue < existingItemInClosedList['gValue']:
                existingItemInClosedList['gValue'] = childGValue;
                existingItemInClosedList['parentPos'] = currentNode['position'];
                continue        

        openList.append({"parentPos" : currentNode['position'], "position" : childPosition,"gValue" : childGValue,"hValue" : childHValue,"fValue" : childFValue})

here is the helper class to search in the dictionary:

func findInArray(listToUse, Parameter, Value):
if Value == null:
        return null;

for item in listToUse:
    if item[Parameter] == Value:
        return item;

return null

UPDATE: Mystery solved!
so after posting my question i got through my code to clean it up a bit.
i found the issue with the openList -> i actually never skipped adding a point to the open List, so this List got reallllllly long!
the fix are the well placed continues :) :

#in der open List schauen ob diese Position schon mit einem schlechteren G Wert vorhanden ist
        var existingItemInOpenList = findInArray(openList, "position", childPosition)           
        if existingItemInOpenList != null:
            if childGValue < existingItemInOpenList['gValue']:
                existingItemInOpenList['gValue'] = childGValue;
                existingItemInOpenList['parentPos'] = currentNode['position'];
                continue
            continue

        #in der closed List schauen ob die Position schon mit einem schlechteren G Wert vorhanden ist
        var existingItemInClosedList = findInArray(closedList, "position", childPosition)
        if existingItemInClosedList != null:
            if childGValue < existingItemInClosedList['gValue']:
                existingItemInClosedList['gValue'] = childGValue;
                existingItemInClosedList['parentPos'] = currentNode['position'];
                continue
            continue    
Godot version v3.5.stable.official [991bb6ac7]
in Engine by (12 points)

Please log in or register to answer this question.

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 Frequently asked questions and 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 [email protected] with your username.