diff options
Diffstat (limited to 'src/aystar.cpp')
-rw-r--r-- | src/aystar.cpp | 96 |
1 files changed, 48 insertions, 48 deletions
diff --git a/src/aystar.cpp b/src/aystar.cpp index d34e9911d..3e1260afd 100644 --- a/src/aystar.cpp +++ b/src/aystar.cpp @@ -25,36 +25,36 @@ int _aystar_stats_open_size; int _aystar_stats_closed_size; -// This looks in the Hash if a node exists in ClosedList -// If so, it returns the PathNode, else NULL +/* This looks in the Hash if a node exists in ClosedList + * If so, it returns the PathNode, else NULL */ static PathNode *AyStarMain_ClosedList_IsInList(AyStar *aystar, const AyStarNode *node) { return (PathNode*)Hash_Get(&aystar->ClosedListHash, node->tile, node->direction); } -// This adds a node to the ClosedList -// It makes a copy of the data +/* This adds a node to the ClosedList + * It makes a copy of the data */ static void AyStarMain_ClosedList_Add(AyStar *aystar, const PathNode *node) { - // Add a node to the ClosedList + /* Add a node to the ClosedList */ PathNode *new_node = MallocT<PathNode>(1); *new_node = *node; Hash_Set(&aystar->ClosedListHash, node->node.tile, node->node.direction, new_node); } -// Checks if a node is in the OpenList -// If so, it returns the OpenListNode, else NULL +/* Checks if a node is in the OpenList + * If so, it returns the OpenListNode, else NULL */ static OpenListNode *AyStarMain_OpenList_IsInList(AyStar *aystar, const AyStarNode *node) { return (OpenListNode*)Hash_Get(&aystar->OpenListHash, node->tile, node->direction); } -// Gets the best node from OpenList -// returns the best node, or NULL of none is found -// Also it deletes the node from the OpenList +/* Gets the best node from OpenList + * returns the best node, or NULL of none is found + * Also it deletes the node from the OpenList */ static OpenListNode *AyStarMain_OpenList_Pop(AyStar *aystar) { - // Return the item the Queue returns.. the best next OpenList item. + /* 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); @@ -63,18 +63,18 @@ static OpenListNode *AyStarMain_OpenList_Pop(AyStar *aystar) return res; } -// Adds a node to the OpenList -// It makes a copy of node, and puts the pointer of parent in the struct +/* 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, const AyStarNode *node, int f, int g) { - // Add a new Node to the OpenList + /* Add a new Node to the OpenList */ OpenListNode *new_node = MallocT<OpenListNode>(1); 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 + /* Add it to the queue */ aystar->OpenListQueue.push(&aystar->OpenListQueue, new_node, f); } @@ -89,49 +89,49 @@ int AyStarMain_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *pare PathNode *closedlist_parent; OpenListNode *check; - // Check the new node against the ClosedList + /* Check the new node against the ClosedList */ if (AyStarMain_ClosedList_IsInList(aystar, current) != NULL) return AYSTAR_DONE; - // Calculate the G-value for this node + /* Calculate the G-value for this node */ new_g = aystar->CalculateG(aystar, current, parent); - // If the value was INVALID_NODE, we don't do anything with this node + /* If the value was INVALID_NODE, we don't do anything with this node */ if (new_g == AYSTAR_INVALID_NODE) return AYSTAR_DONE; - // There should not be given any other error-code.. + /* There should not be given any other error-code.. */ assert(new_g >= 0); - // Add the parent g-value to the new g-value + /* Add the parent g-value to the new g-value */ new_g += parent->g; if (aystar->max_path_cost != 0 && (uint)new_g > aystar->max_path_cost) return AYSTAR_DONE; - // Calculate the h-value + /* Calculate the h-value */ new_h = aystar->CalculateH(aystar, current, parent); - // There should not be given any error-code.. + /* There should not be given any error-code.. */ assert(new_h >= 0); - // The f-value if g + h + /* The f-value if g + h */ new_f = new_g + new_h; - // Get the pointer to the parent in the ClosedList (the currentone is to a copy of the one in the OpenList) + /* Get the pointer to the parent in the ClosedList (the currentone is to a copy of the one in the OpenList) */ closedlist_parent = AyStarMain_ClosedList_IsInList(aystar, &parent->path.node); - // Check if this item is already in the OpenList + /* Check if this item is already in the OpenList */ check = AyStarMain_OpenList_IsInList(aystar, current); if (check != NULL) { uint i; - // Yes, check if this g value is lower.. + /* Yes, check if this g value is lower.. */ if (new_g > check->g) return AYSTAR_DONE; aystar->OpenListQueue.del(&aystar->OpenListQueue, check, 0); - // It is lower, so change it to this item + /* 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 + /* Readd him in the OpenListQueue */ aystar->OpenListQueue.push(&aystar->OpenListQueue, check, new_f); } else { - // A new node, add him to the OpenList + /* A new node, add him to the OpenList */ AyStarMain_OpenList_Add(aystar, closedlist_parent, current, new_f, new_g); } @@ -153,12 +153,12 @@ int AyStarMain_Loop(AyStar *aystar) { int i, r; - // Get the best node from OpenList + /* Get the best node from OpenList */ OpenListNode *current = AyStarMain_OpenList_Pop(aystar); - // If empty, drop an error + /* If empty, drop an error */ if (current == NULL) return AYSTAR_EMPTY_OPENLIST; - // Check for end node and if found, return that code + /* Check for end node and if found, return that code */ if (aystar->EndNodeCheck(aystar, current) == AYSTAR_FOUND_END_NODE) { if (aystar->FoundEndNode != NULL) aystar->FoundEndNode(aystar, current); @@ -166,26 +166,26 @@ int AyStarMain_Loop(AyStar *aystar) return AYSTAR_FOUND_END_NODE; } - // Add the node to the ClosedList + /* Add the node to the ClosedList */ AyStarMain_ClosedList_Add(aystar, ¤t->path); - // Load the neighbours + /* Load the neighbours */ aystar->GetNeighbours(aystar, current); - // Go through all neighbours + /* Go through all neighbours */ for (i = 0; i < aystar->num_neighbours; i++) { - // Check and add them to the OpenList if needed + /* Check and add them to the OpenList if needed */ r = aystar->checktile(aystar, &aystar->neighbours[i], current); } - // Free the node + /* Free the node */ free(current); if (aystar->max_search_nodes != 0 && Hash_Size(&aystar->ClosedListHash) >= aystar->max_search_nodes) { /* We've expanded enough nodes */ return AYSTAR_LIMIT_REACHED; } else { - // Return that we are still busy + /* Return that we are still busy */ return AYSTAR_STILL_BUSY; } } @@ -211,10 +211,10 @@ void AyStarMain_Free(AyStar *aystar) */ void AyStarMain_Clear(AyStar *aystar) { - // Clean the Queue, but not the elements within. That will be done by - // the hash. + /* Clean the Queue, but not the elements within. That will be done by + * the hash. */ aystar->OpenListQueue.clear(&aystar->OpenListQueue, false); - // Clean the hashes + /* Clean the hashes */ clear_Hash(&aystar->OpenListHash, true); clear_Hash(&aystar->ClosedListHash, true); @@ -235,8 +235,8 @@ void AyStarMain_Clear(AyStar *aystar) */ int AyStarMain_Main(AyStar *aystar) { int r, i = 0; - // Loop through the OpenList - // Quit if result is no AYSTAR_STILL_BUSY or is more than loops_per_tick + /* Loop through the OpenList + * Quit if result is no AYSTAR_STILL_BUSY or is more than loops_per_tick */ while ((r = aystar->loop(aystar)) == AYSTAR_STILL_BUSY && (aystar->loops_per_tick == 0 || ++i < aystar->loops_per_tick)) { } #ifdef AYSTAR_DEBUG switch (r) { @@ -279,14 +279,14 @@ void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node, uint g) void init_AyStar(AyStar *aystar, Hash_HashProc hash, uint num_buckets) { - // Allocated the Hash for the OpenList and ClosedList + /* 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 + /* 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); aystar->addstart = AyStarMain_AddStartNode; |