(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)

1 files changed, 271 insertions, 271 deletions

diff --git a/aystar.c b/aystar.c
index cd7c40214..a38dfc7a8 100644
--- a/aystar.c
+++ b/aystar.c
@@ -1,271 +1,271 @@
-/*

- * This file has the core function for AyStar

- *  AyStar is a fast pathfinding routine and is used for things like

- *  AI_pathfinding and Train_pathfinding.

- *  For more information about AyStar (A* Algorithm), you can look at

- *    http://en.wikipedia.org/wiki/A-star_search_algorithm

- */

- 

-/*

- * Friendly reminder:

- *  Call (AyStar).free() when you are done with Aystar. It reserves a lot of memory

- *  And when not free'd, it can cause system-crashes.

- * Also remember that when you stop an algorithm before it is finished, your

- * should call clear() yourself!

- */

-

-#include "stdafx.h"

-#include "ttd.h"

-#include "aystar.h"

-// This looks in the Hash if a node exists in ClosedList

-//  If so, it returns the PathNode, else NULL

-PathNode *AyStarMain_ClosedList_IsInList(AyStar *aystar, 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

-void AyStarMain_ClosedList_Add(AyStar *aystar, PathNode *node) {

-	// Add a node to the ClosedList

-	PathNode *new_node = malloc(sizeof(PathNode));

-	*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

-OpenListNode *AyStarMain_OpenList_IsInList(AyStar *aystar, 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

-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

-void AyStarMain_OpenList_Add(AyStar *aystar, PathNode *parent, AyStarNode *node, int f, int g, int userdata) {

-	// 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);

-}

-

-/*

- * Checks one tile and calculate his f-value

- *  return values:

- *	AYSTAR_DONE : indicates we are done

- */

-int AyStarMain_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent) {

-	int new_f, new_g, new_h;

-	PathNode *closedlist_parent;

-	OpenListNode *check;

-

-	// Check the new node against the ClosedList

-	if (AyStarMain_ClosedList_IsInList(aystar, current) != NULL) return AYSTAR_DONE;

-	

-	// 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 (new_g == AYSTAR_INVALID_NODE) return AYSTAR_DONE;

-	

-	// There should not be given any other error-code..

-	assert(new_g >= 0);

-	// 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

-	new_h = aystar->CalculateH(aystar, current, parent);

-	// There should not be given any error-code..

-	assert(new_h >= 0);

-	

-	// 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 = AyStarMain_ClosedList_IsInList(aystar, &parent->path.node);

-	

-	// Check if this item is already in the OpenList

-	if ((check = AyStarMain_OpenList_IsInList(aystar, current)) != NULL) {

-		int i;

-		// 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

-		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);

-	}

-	

-	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

- *	reached.

- *	AYSTAR_FOUND_END_NODE : indicates we found the end. Path_found now is true, and in path is the path found.

- *	AYSTAR_STILL_BUSY : indicates we have done this tile, did not found the path yet, and have items left to try.

- */

-int AyStarMain_Loop(AyStar *aystar) {

-	int i, r;

-	

-	// Get the best node from OpenList

-	OpenListNode *current = AyStarMain_OpenList_Pop(aystar);

-	// If empty, drop an error

-	if (current == NULL) return AYSTAR_EMPTY_OPENLIST;

-	

-	// 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);

-		free(current);

-		return AYSTAR_FOUND_END_NODE;

-	}

-	

-	// Add the node to the ClosedList

-	AyStarMain_ClosedList_Add(aystar, &current->path);

-

-	// Load the neighbours

-	aystar->GetNeighbours(aystar, current);

-	

-	// Go through all neighbours

-	for (i=0;i<aystar->num_neighbours;i++) {

-		// Check and add them to the OpenList if needed

-		r = aystar->checktile(aystar, &aystar->neighbours[i], current);

-	}

-	

-	// 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 AYSTAR_STILL_BUSY;

-}

-

-/*

- * This function frees the memory it allocated

- */

-void AyStarMain_Free(AyStar *aystar) {

-	aystar->OpenListQueue.free(&aystar->OpenListQueue, false);

-	/* 2nd argument above is false, below is true, to free the values only

-	 * once */

-	delete_Hash(&aystar->OpenListHash, true);

-	delete_Hash(&aystar->ClosedListHash, 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 AyStarMain_Clear(AyStar *aystar) {

-	// Clean the Queue, but not the elements within. That will be done by

-	// the hash.

-	aystar->OpenListQueue.clear(&aystar->OpenListQueue, false);

-	// Clean the hashes

-	clear_Hash(&aystar->OpenListHash, true);

-	clear_Hash(&aystar->ClosedListHash, 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.

- * When the algorithm is done (when the return value is not AYSTAR_STILL_BUSY)

- * aystar->clear() is called. Note that when you stop the algorithm halfway,

- * you should still call clear() yourself!

- */

-int AyStarMain_Main(AyStar *aystar) {

-	int r, i = 0;

-	// Loop through the OpenList

-	//  Quit if result is no AYSTAR_STILL_BUSY or is more then loops_per_tick

-	while ((r = aystar->loop(aystar)) == AYSTAR_STILL_BUSY && (aystar->loops_per_tick == 0 || ++i < aystar->loops_per_tick)) { }

-#ifdef AYSTAR_DEBUG

-	if (r == AYSTAR_FOUND_END_NODE)

-		printf("[AyStar] Found path!\n");

-	else if (r == AYSTAR_EMPTY_OPENLIST)

-		printf("[AyStar] OpenList run dry, no path found\n");

-	else if (r == AYSTAR_LIMIT_REACHED)

-		printf("[AyStar] Exceeded search_nodes, no path found\n");

-#endif

-	if (r != AYSTAR_STILL_BUSY)

-		/* We're done, clean up */

-		aystar->clear(aystar);

-		

-	// Check result-value

-	if (r == AYSTAR_FOUND_END_NODE) return AYSTAR_FOUND_END_NODE;

-	// 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 

- */

-void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node) {

-#ifdef AYSTAR_DEBUG

-	printf("[AyStar] Starting A* Algorithm from node (%d, %d, %d)\n", GET_TILE_X(start_node->tile), GET_TILE_Y(start_node->tile), start_node->direction);

-#endif

-	AyStarMain_OpenList_Add(aystar, NULL, start_node, 0, 0, 0);

-}

-

-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);

-

-	aystar->addstart	= AyStarMain_AddStartNode;

-	aystar->main		= AyStarMain_Main;

-	aystar->loop		= AyStarMain_Loop;

-	aystar->free		= AyStarMain_Free;

-	aystar->clear		= AyStarMain_Clear;

-	aystar->checktile	= AyStarMain_CheckTile;

-}

+/*
+ * This file has the core function for AyStar
+ *  AyStar is a fast pathfinding routine and is used for things like
+ *  AI_pathfinding and Train_pathfinding.
+ *  For more information about AyStar (A* Algorithm), you can look at
+ *    http://en.wikipedia.org/wiki/A-star_search_algorithm
+ */
+ 
+/*
+ * Friendly reminder:
+ *  Call (AyStar).free() when you are done with Aystar. It reserves a lot of memory
+ *  And when not free'd, it can cause system-crashes.
+ * Also remember that when you stop an algorithm before it is finished, your
+ * should call clear() yourself!
+ */
+
+#include "stdafx.h"
+#include "ttd.h"
+#include "aystar.h"
+// This looks in the Hash if a node exists in ClosedList
+//  If so, it returns the PathNode, else NULL
+PathNode *AyStarMain_ClosedList_IsInList(AyStar *aystar, 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
+void AyStarMain_ClosedList_Add(AyStar *aystar, PathNode *node) {
+	// Add a node to the ClosedList
+	PathNode *new_node = malloc(sizeof(PathNode));
+	*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
+OpenListNode *AyStarMain_OpenList_IsInList(AyStar *aystar, 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
+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
+void AyStarMain_OpenList_Add(AyStar *aystar, PathNode *parent, AyStarNode *node, int f, int g, int userdata) {
+	// 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);
+}
+
+/*
+ * Checks one tile and calculate his f-value
+ *  return values:
+ *	AYSTAR_DONE : indicates we are done
+ */
+int AyStarMain_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent) {
+	int new_f, new_g, new_h;
+	PathNode *closedlist_parent;
+	OpenListNode *check;
+
+	// Check the new node against the ClosedList
+	if (AyStarMain_ClosedList_IsInList(aystar, current) != NULL) return AYSTAR_DONE;
+	
+	// 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 (new_g == AYSTAR_INVALID_NODE) return AYSTAR_DONE;
+	
+	// There should not be given any other error-code..
+	assert(new_g >= 0);
+	// 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
+	new_h = aystar->CalculateH(aystar, current, parent);
+	// There should not be given any error-code..
+	assert(new_h >= 0);
+	
+	// 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 = AyStarMain_ClosedList_IsInList(aystar, &parent->path.node);
+	
+	// Check if this item is already in the OpenList
+	if ((check = AyStarMain_OpenList_IsInList(aystar, current)) != NULL) {
+		int i;
+		// 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
+		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);
+	}
+	
+	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
+ *	reached.
+ *	AYSTAR_FOUND_END_NODE : indicates we found the end. Path_found now is true, and in path is the path found.
+ *	AYSTAR_STILL_BUSY : indicates we have done this tile, did not found the path yet, and have items left to try.
+ */
+int AyStarMain_Loop(AyStar *aystar) {
+	int i, r;
+	
+	// Get the best node from OpenList
+	OpenListNode *current = AyStarMain_OpenList_Pop(aystar);
+	// If empty, drop an error
+	if (current == NULL) return AYSTAR_EMPTY_OPENLIST;
+	
+	// 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);
+		free(current);
+		return AYSTAR_FOUND_END_NODE;
+	}
+	
+	// Add the node to the ClosedList
+	AyStarMain_ClosedList_Add(aystar, &current->path);
+
+	// Load the neighbours
+	aystar->GetNeighbours(aystar, current);
+	
+	// Go through all neighbours
+	for (i=0;i<aystar->num_neighbours;i++) {
+		// Check and add them to the OpenList if needed
+		r = aystar->checktile(aystar, &aystar->neighbours[i], current);
+	}
+	
+	// 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 AYSTAR_STILL_BUSY;
+}
+
+/*
+ * This function frees the memory it allocated
+ */
+void AyStarMain_Free(AyStar *aystar) {
+	aystar->OpenListQueue.free(&aystar->OpenListQueue, false);
+	/* 2nd argument above is false, below is true, to free the values only
+	 * once */
+	delete_Hash(&aystar->OpenListHash, true);
+	delete_Hash(&aystar->ClosedListHash, 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 AyStarMain_Clear(AyStar *aystar) {
+	// Clean the Queue, but not the elements within. That will be done by
+	// the hash.
+	aystar->OpenListQueue.clear(&aystar->OpenListQueue, false);
+	// Clean the hashes
+	clear_Hash(&aystar->OpenListHash, true);
+	clear_Hash(&aystar->ClosedListHash, 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.
+ * When the algorithm is done (when the return value is not AYSTAR_STILL_BUSY)
+ * aystar->clear() is called. Note that when you stop the algorithm halfway,
+ * you should still call clear() yourself!
+ */
+int AyStarMain_Main(AyStar *aystar) {
+	int r, i = 0;
+	// Loop through the OpenList
+	//  Quit if result is no AYSTAR_STILL_BUSY or is more then loops_per_tick
+	while ((r = aystar->loop(aystar)) == AYSTAR_STILL_BUSY && (aystar->loops_per_tick == 0 || ++i < aystar->loops_per_tick)) { }
+#ifdef AYSTAR_DEBUG
+	if (r == AYSTAR_FOUND_END_NODE)
+		printf("[AyStar] Found path!\n");
+	else if (r == AYSTAR_EMPTY_OPENLIST)
+		printf("[AyStar] OpenList run dry, no path found\n");
+	else if (r == AYSTAR_LIMIT_REACHED)
+		printf("[AyStar] Exceeded search_nodes, no path found\n");
+#endif
+	if (r != AYSTAR_STILL_BUSY)
+		/* We're done, clean up */
+		aystar->clear(aystar);
+		
+	// Check result-value
+	if (r == AYSTAR_FOUND_END_NODE) return AYSTAR_FOUND_END_NODE;
+	// 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 
+ */
+void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node) {
+#ifdef AYSTAR_DEBUG
+	printf("[AyStar] Starting A* Algorithm from node (%d, %d, %d)\n", GET_TILE_X(start_node->tile), GET_TILE_Y(start_node->tile), start_node->direction);
+#endif
+	AyStarMain_OpenList_Add(aystar, NULL, start_node, 0, 0, 0);
+}
+
+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);
+
+	aystar->addstart	= AyStarMain_AddStartNode;
+	aystar->main		= AyStarMain_Main;
+	aystar->loop		= AyStarMain_Loop;
+	aystar->free		= AyStarMain_Free;
+	aystar->clear		= AyStarMain_Clear;
+	aystar->checktile	= AyStarMain_CheckTile;
+}