|
@@ -47,25 +47,25 @@ static OpenListNode *AyStarMain_OpenList
|
|
|
static OpenListNode *AyStarMain_OpenList_Pop(AyStar *aystar)
|
|
|
{
|
|
|
// Return the item the Queue returns.. the best next OpenList item.
|
|
|
OpenListNode* res = (OpenListNode*)aystar->OpenListQueue.pop(&aystar->OpenListQueue);
|
|
|
if (res != NULL)
|
|
|
Hash_Delete(&aystar->OpenListHash, res->path.node.tile, res->path.node.direction);
|
|
|
|
|
|
return res;
|
|
|
}
|
|
|
|
|
|
// Adds a node to the OpenList
|
|
|
// It makes a copy of node, and puts the pointer of parent in the struct
|
|
|
static void AyStarMain_OpenList_Add(AyStar *aystar, PathNode *parent, AyStarNode *node, int f, int g, int userdata)
|
|
|
static void AyStarMain_OpenList_Add(AyStar *aystar, PathNode *parent, AyStarNode *node, int f, int g)
|
|
|
{
|
|
|
// Add a new Node to the OpenList
|
|
|
OpenListNode* new_node = malloc(sizeof(OpenListNode));
|
|
|
new_node->g = g;
|
|
|
new_node->path.parent = parent;
|
|
|
new_node->path.node = *node;
|
|
|
Hash_Set(&aystar->OpenListHash, node->tile, node->direction, new_node);
|
|
|
|
|
|
// Add it to the queue
|
|
|
aystar->OpenListQueue.push(&aystar->OpenListQueue, new_node, f);
|
|
|
}
|
|
|
|
|
@@ -111,25 +111,25 @@ int AyStarMain_CheckTile(AyStar *aystar,
|
|
|
if (new_g > check->g) return AYSTAR_DONE;
|
|
|
aystar->OpenListQueue.del(&aystar->OpenListQueue, check, 0);
|
|
|
// It is lower, so change it to this item
|
|
|
check->g = new_g;
|
|
|
check->path.parent = closedlist_parent;
|
|
|
/* Copy user data, will probably have changed */
|
|
|
for (i=0;i<lengthof(current->user_data);i++)
|
|
|
check->path.node.user_data[i] = current->user_data[i];
|
|
|
// Readd him in the OpenListQueue
|
|
|
aystar->OpenListQueue.push(&aystar->OpenListQueue, check, new_f);
|
|
|
} else {
|
|
|
// A new node, add him to the OpenList
|
|
|
AyStarMain_OpenList_Add(aystar, closedlist_parent, current, new_f, new_g, 0);
|
|
|
AyStarMain_OpenList_Add(aystar, closedlist_parent, current, new_f, new_g);
|
|
|
}
|
|
|
|
|
|
return AYSTAR_DONE;
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
* This function is the core of AyStar. It handles one item and checks
|
|
|
* his neighbour items. If they are valid, they are added to be checked too.
|
|
|
* return values:
|
|
|
* AYSTAR_EMPTY_OPENLIST : indicates all items are tested, and no path
|
|
|
* has been found.
|
|
|
* AYSTAR_LIMIT_REACHED : Indicates that the max_nodes limit has been
|
|
@@ -239,31 +239,32 @@ int AyStarMain_Main(AyStar *aystar) {
|
|
|
// Check if we have some left in the OpenList
|
|
|
if (r == AYSTAR_EMPTY_OPENLIST || r == AYSTAR_LIMIT_REACHED) return AYSTAR_NO_PATH;
|
|
|
|
|
|
// Return we are still busy
|
|
|
return AYSTAR_STILL_BUSY;
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
* Adds a node from where to start an algorithm. Multiple nodes can be added
|
|
|
* if wanted. You should make sure that clear() is called before adding nodes
|
|
|
* if the AyStar has been used before (though the normal main loop calls
|
|
|
* clear() automatically when the algorithm finishes
|
|
|
* g is the cost for starting with this node.
|
|
|
*/
|
|
|
void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node) {
|
|
|
void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node, uint g) {
|
|
|
#ifdef AYSTAR_DEBUG
|
|
|
printf("[AyStar] Starting A* Algorithm from node (%d, %d, %d)\n",
|
|
|
TileX(start_node->tile), TileY(start_node->tile), start_node->direction);
|
|
|
#endif
|
|
|
AyStarMain_OpenList_Add(aystar, NULL, start_node, 0, 0, 0);
|
|
|
AyStarMain_OpenList_Add(aystar, NULL, start_node, 0, g);
|
|
|
}
|
|
|
|
|
|
void init_AyStar(AyStar* aystar, Hash_HashProc hash, uint num_buckets) {
|
|
|
// Allocated the Hash for the OpenList and ClosedList
|
|
|
init_Hash(&aystar->OpenListHash, hash, num_buckets);
|
|
|
init_Hash(&aystar->ClosedListHash, hash, num_buckets);
|
|
|
|
|
|
// Set up our sorting queue
|
|
|
// BinaryHeap allocates a block of 1024 nodes
|
|
|
// When thatone gets full it reserves an otherone, till this number
|
|
|
// That is why it can stay this high
|
|
|
init_BinaryHeap(&aystar->OpenListQueue, 102400);
|