|
@@ -24,71 +24,71 @@
|
|
|
* Also remember that when you stop an algorithm before it is finished, your
|
|
|
* should call clear() yourself!
|
|
|
*/
|
|
|
|
|
|
#include "../../stdafx.h"
|
|
|
#include "../../core/alloc_func.hpp"
|
|
|
#include "aystar.h"
|
|
|
|
|
|
/* This looks in the Hash if a node exists in ClosedList
|
|
|
* If so, it returns the PathNode, else NULL */
|
|
|
PathNode *AyStar::ClosedListIsInList(const AyStarNode *node)
|
|
|
{
|
|
|
return (PathNode*)this->ClosedListHash.Get(node->tile, node->direction);
|
|
|
return (PathNode*)this->closedlist_hash.Get(node->tile, node->direction);
|
|
|
}
|
|
|
|
|
|
/* This adds a node to the ClosedList
|
|
|
* It makes a copy of the data */
|
|
|
void AyStar::ClosedListAdd(const PathNode *node)
|
|
|
{
|
|
|
/* Add a node to the ClosedList */
|
|
|
PathNode *new_node = MallocT<PathNode>(1);
|
|
|
*new_node = *node;
|
|
|
this->ClosedListHash.Set(node->node.tile, node->node.direction, new_node);
|
|
|
this->closedlist_hash.Set(node->node.tile, node->node.direction, new_node);
|
|
|
}
|
|
|
|
|
|
/* Checks if a node is in the OpenList
|
|
|
* If so, it returns the OpenListNode, else NULL */
|
|
|
OpenListNode *AyStar::OpenListIsInList(const AyStarNode *node)
|
|
|
{
|
|
|
return (OpenListNode*)this->OpenListHash.Get(node->tile, node->direction);
|
|
|
return (OpenListNode*)this->openlist_hash.Get(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 */
|
|
|
OpenListNode *AyStar::OpenListPop()
|
|
|
{
|
|
|
/* Return the item the Queue returns.. the best next OpenList item. */
|
|
|
OpenListNode *res = (OpenListNode*)this->OpenListQueue.Pop();
|
|
|
OpenListNode *res = (OpenListNode*)this->openlist_queue.Pop();
|
|
|
if (res != NULL) {
|
|
|
this->OpenListHash.DeleteValue(res->path.node.tile, res->path.node.direction);
|
|
|
this->openlist_hash.DeleteValue(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 */
|
|
|
void AyStar::OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g)
|
|
|
{
|
|
|
/* 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;
|
|
|
this->OpenListHash.Set(node->tile, node->direction, new_node);
|
|
|
this->openlist_hash.Set(node->tile, node->direction, new_node);
|
|
|
|
|
|
/* Add it to the queue */
|
|
|
this->OpenListQueue.Push(new_node, f);
|
|
|
this->openlist_queue.Push(new_node, f);
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
* Checks one tile and calculate his f-value
|
|
|
*/
|
|
|
void AyStar::CheckTile(AyStarNode *current, OpenListNode *parent)
|
|
|
{
|
|
|
int new_f, new_g, new_h;
|
|
|
PathNode *closedlist_parent;
|
|
|
OpenListNode *check;
|
|
|
|
|
|
/* Check the new node against the ClosedList */
|
|
@@ -113,34 +113,34 @@ void AyStar::CheckTile(AyStarNode *curre
|
|
|
/* 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) */
|
|
|
closedlist_parent = this->ClosedListIsInList(&parent->path.node);
|
|
|
|
|
|
/* Check if this item is already in the OpenList */
|
|
|
check = this->OpenListIsInList(current);
|
|
|
if (check != NULL) {
|
|
|
uint i;
|
|
|
/* Yes, check if this g value is lower.. */
|
|
|
if (new_g > check->g) return;
|
|
|
this->OpenListQueue.Delete(check, 0);
|
|
|
this->openlist_queue.Delete(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 */
|
|
|
this->OpenListQueue.Push(check, new_f);
|
|
|
/* Re-add it in the openlist_queue. */
|
|
|
this->openlist_queue.Push(check, new_f);
|
|
|
} else {
|
|
|
/* A new node, add him to the OpenList */
|
|
|
this->OpenListAdd(closedlist_parent, current, new_f, new_g);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
* 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.
|
|
@@ -173,60 +173,60 @@ int AyStar::Loop()
|
|
|
/* Load the neighbours */
|
|
|
this->GetNeighbours(this, current);
|
|
|
|
|
|
/* Go through all neighbours */
|
|
|
for (i = 0; i < this->num_neighbours; i++) {
|
|
|
/* Check and add them to the OpenList if needed */
|
|
|
this->CheckTile(&this->neighbours[i], current);
|
|
|
}
|
|
|
|
|
|
/* Free the node */
|
|
|
free(current);
|
|
|
|
|
|
if (this->max_search_nodes != 0 && this->ClosedListHash.GetSize() >= this->max_search_nodes) {
|
|
|
if (this->max_search_nodes != 0 && this->closedlist_hash.GetSize() >= this->max_search_nodes) {
|
|
|
/* We've expanded enough nodes */
|
|
|
return AYSTAR_LIMIT_REACHED;
|
|
|
} else {
|
|
|
/* Return that we are still busy */
|
|
|
return AYSTAR_STILL_BUSY;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
* This function frees the memory it allocated
|
|
|
*/
|
|
|
void AyStar::Free()
|
|
|
{
|
|
|
this->OpenListQueue.Free(false);
|
|
|
this->openlist_queue.Free(false);
|
|
|
/* 2nd argument above is false, below is true, to free the values only
|
|
|
* once */
|
|
|
this->OpenListHash.Delete(true);
|
|
|
this->ClosedListHash.Delete(true);
|
|
|
this->openlist_hash.Delete(true);
|
|
|
this->closedlist_hash.Delete(true);
|
|
|
#ifdef AYSTAR_DEBUG
|
|
|
printf("[AyStar] Memory free'd\n");
|
|
|
#endif
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
* This function make the memory go back to zero
|
|
|
* This function should be called when you are using the same instance again.
|
|
|
*/
|
|
|
void AyStar::Clear()
|
|
|
{
|
|
|
/* Clean the Queue, but not the elements within. That will be done by
|
|
|
* the hash. */
|
|
|
this->OpenListQueue.Clear(false);
|
|
|
this->openlist_queue.Clear(false);
|
|
|
/* Clean the hashes */
|
|
|
this->OpenListHash.Clear(true);
|
|
|
this->ClosedListHash.Clear(true);
|
|
|
this->openlist_hash.Clear(true);
|
|
|
this->closedlist_hash.Clear(true);
|
|
|
|
|
|
#ifdef AYSTAR_DEBUG
|
|
|
printf("[AyStar] Cleared AyStar\n");
|
|
|
#endif
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
* This is the function you call to run AyStar.
|
|
|
* return values:
|
|
|
* AYSTAR_FOUND_END_NODE : indicates we found an end node.
|
|
|
* AYSTAR_NO_PATH : indicates that there was no path found.
|
|
|
* AYSTAR_STILL_BUSY : indicates we have done some checked, that we did not found the path yet, and that we still have items left to try.
|
|
@@ -276,21 +276,21 @@ void AyStar::AddStartNode(AyStarNode *st
|
|
|
#endif
|
|
|
this->OpenListAdd(NULL, start_node, 0, g);
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Initialize an #AyStar. You should fill all appropriate fields before
|
|
|
* calling #Init (see the declaration of #AyStar for which fields are
|
|
|
* internal.
|
|
|
*/
|
|
|
void AyStar::Init(Hash_HashProc hash, uint num_buckets)
|
|
|
{
|
|
|
/* Allocated the Hash for the OpenList and ClosedList */
|
|
|
this->OpenListHash.Init(hash, num_buckets);
|
|
|
this->ClosedListHash.Init(hash, num_buckets);
|
|
|
this->openlist_hash.Init(hash, num_buckets);
|
|
|
this->closedlist_hash.Init(hash, num_buckets);
|
|
|
|
|
|
/* Set up our sorting queue
|
|
|
* BinaryHeap allocates a block of 1024 nodes
|
|
|
* When that one gets full it reserves another one, till this number
|
|
|
* That is why it can stay this high */
|
|
|
this->OpenListQueue.Init(102400);
|
|
|
this->openlist_queue.Init(102400);
|
|
|
}
|