 |
Attention | Topic was automatically imported from the old Question2Answer platform. |
 |
Asked By | PURULama |
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).
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)
or very near (that already did a small “hiccup”
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