Geners
Member
So I have a grid of hexes, each containing a coordinate, an array of its neighbors, and its g_value, h_value, and f_value.
I have set up this A* pathfinding function to find a path between two points, and as you can see below it works perfectly if there's a valid path.
But if there's not a valid path, instead of returning noone like I want it to it to, the loop runs forever and it keeps rechecking things that have already been evaluated, but that makes no sense because it shouldn't check anything that's contained in the closedSet
Here's my code for the pathfinding function. I'm sorry if this is very sloppy, it's my first attempt at this algorithm. As far as I can see, it's not an issue with any of my utility functions like "array_push" or with the hex objects themselves.
So I guess my question is, what am I doing wrong?
I have set up this A* pathfinding function to find a path between two points, and as you can see below it works perfectly if there's a valid path.
But if there's not a valid path, instead of returning noone like I want it to it to, the loop runs forever and it keeps rechecking things that have already been evaluated, but that makes no sense because it shouldn't check anything that's contained in the closedSet
Here's my code for the pathfinding function. I'm sorry if this is very sloppy, it's my first attempt at this algorithm. As far as I can see, it's not an issue with any of my utility functions like "array_push" or with the hex objects themselves.
GML:
function hex_pathfinding(beginX, beginY, endX, endY){
var openSet = ds_list_create();
var closedSet = ds_list_create();
var current = global.hexGrid[beginX, beginY];
var beginning_hex = current;
var end_hex = global.hexGrid[endX, endY];
openSet = ds_list_add(openSet, current);
while (!ds_list_empty(openSet)) {
//shorthand
var setLength = ds_list_size(openSet);
var lowestValue = 0;
for(var i = 0; i < setLength; i++) {
if(openSet[| lowestValue].f_value > openSet[| i].f_value) {
lowestValue = i;
}
}
current = openSet[| lowestValue];
show_debug_message(string(current.coordinate[0]) + ", " + string(current.coordinate[1]));
if(current == end_hex) {
var path = [];
var tempH = current;
while(tempH != beginning_hex) {
path = array_push(path,tempH);
tempH = tempH.previousHex;
}
path = array_push(path,beginning_hex);
return path;
}
openSet = remove_from_ds(openSet, current);
closedSet = ds_list_add(closedSet, current);
//creating a shorthand
var neighbors = current.neighbors;
for(var i = 0; i < array_length(neighbors); i++) {
if(!contains_ds(closedSet,neighbors[i])) {
var tempG = current.g_value + 1;
if(contains_ds(openSet,neighbors[i])) {
if(tempG <= neighbors[i].g_value) {
neighbors[i].g_value = tempG;
neighbors[i].h_value = distance_hex(neighbors[i].coordinate[0],neighbors[i].coordinate[1],endX,endY);
neighbors[i].f_value = neighbors[i].g_value + neighbors[i].h_value;
neighbors[i].previousHex = current;
}
}
else {
neighbors[i].g_value = tempG;
neighbors[i].h_value = distance_hex(neighbors[i].coordinate[0],neighbors[i].coordinate[1],endX,endY);
neighbors[i].f_value = neighbors[i].g_value + neighbors[i].h_value;
neighbors[i].previousHex = current;
openSet = ds_list_add(openSet,neighbors[i]);
}
}
}
}
//this only happens when there is no valid path.
return noone;
}
Last edited: