From a3dd7506d377b1434f913bd65c019eed52b64b6e Mon Sep 17 00:00:00 2001 From: truebrain Date: Mon, 12 Jan 2009 17:11:45 +0000 Subject: (svn r15027) -Merge: tomatos and bananas left to be, here is NoAI for all to see. NoAI is an API (a framework) to build your own AIs in. See: http://wiki.openttd.org/wiki/index.php/AI:Main_Page With many thanks to: - glx and Rubidium for their syncing, feedback and hard work - Yexo for his feedback, patches, and AIs which tested the system very deep - Morloth for his feedback and patches - TJIP for hosting a challenge which kept NoAI on track - All AI authors for testing our AI API, and all other people who helped in one way or another -Remove: all old AIs and their cheats/hacks --- bin/ai/library/queue/binary_heap/library.nut | 12 ++ bin/ai/library/queue/binary_heap/main.nut | 131 +++++++++++++++ bin/ai/library/queue/fibonacci_heap/library.nut | 12 ++ bin/ai/library/queue/fibonacci_heap/main.nut | 204 ++++++++++++++++++++++++ bin/ai/library/queue/priority_queue/library.nut | 12 ++ bin/ai/library/queue/priority_queue/main.nut | 115 +++++++++++++ 6 files changed, 486 insertions(+) create mode 100644 bin/ai/library/queue/binary_heap/library.nut create mode 100644 bin/ai/library/queue/binary_heap/main.nut create mode 100644 bin/ai/library/queue/fibonacci_heap/library.nut create mode 100644 bin/ai/library/queue/fibonacci_heap/main.nut create mode 100644 bin/ai/library/queue/priority_queue/library.nut create mode 100644 bin/ai/library/queue/priority_queue/main.nut (limited to 'bin/ai/library/queue') diff --git a/bin/ai/library/queue/binary_heap/library.nut b/bin/ai/library/queue/binary_heap/library.nut new file mode 100644 index 000000000..3a96617a9 --- /dev/null +++ b/bin/ai/library/queue/binary_heap/library.nut @@ -0,0 +1,12 @@ +/* $Id$ */ + +class BinaryHeap extends AILibrary { + function GetAuthor() { return "OpenTTD NoAI Developers Team"; } + function GetName() { return "Binary Heap"; } + function GetDescription() { return "An implementation of a Binary Heap"; } + function GetVersion() { return 1; } + function GetDate() { return "2008-06-10"; } + function CreateInstance() { return "BinaryHeap"; } +} + +RegisterLibrary(BinaryHeap()); diff --git a/bin/ai/library/queue/binary_heap/main.nut b/bin/ai/library/queue/binary_heap/main.nut new file mode 100644 index 000000000..1bbb3914f --- /dev/null +++ b/bin/ai/library/queue/binary_heap/main.nut @@ -0,0 +1,131 @@ +/* $Id$ */ + +/** + * Binary Heap. + * Peek and Pop always return the current lowest value in the list. + * Sort is done on insertion and on deletion. + */ +class BinaryHeap +{ + _queue = null; + _count = 0; + + constructor() + { + _queue = []; + } + + /** + * Insert a new entry in the list. + * The complexity of this operation is O(ln n). + * @param item The item to add to the list. + * @param priority The priority this item has. + */ + function Insert(item, priority); + + /** + * Pop the first entry of the list. + * This is always the item with the lowest priority. + * The complexity of this operation is O(ln n). + * @return The item of the entry with the lowest priority. + */ + function Pop(); + + /** + * Peek the first entry of the list. + * This is always the item with the lowest priority. + * The complexity of this operation is O(1). + * @return The item of the entry with the lowest priority. + */ + function Peek(); + + /** + * Get the amount of current items in the list. + * The complexity of this operation is O(1). + * @return The amount of items currently in the list. + */ + function Count(); + + /** + * Check if an item exists in the list. + * The complexity of this operation is O(n). + * @param item The item to check for. + * @return True if the item is already in the list. + */ + function Exists(item); +}; + +function BinaryHeap::Insert(item, priority) +{ + /* Append dummy entry */ + _queue.append(0); + _count++; + + local hole; + /* Find the point of insertion */ + for (hole = _count - 1; hole > 0 && priority <= _queue[hole / 2][1]; hole /= 2) + _queue[hole] = _queue[hole / 2]; + /* Insert new pair */ + _queue[hole] = [item, priority]; + + return true; +} + +function BinaryHeap::Pop() +{ + if (_count == 0) return null; + + local node = _queue[0]; + /* Remove the item from the list by putting the last value on top */ + _queue[0] = _queue[_count - 1]; + _queue.pop(); + _count--; + /* Bubble down the last value to correct the tree again */ + _BubbleDown(); + + return node[0]; +} + +function BinaryHeap::Peek() +{ + if (_count == 0) return null; + + return _queue[0][0]; +} + +function BinaryHeap::Count() +{ + return _count; +} + +function BinaryHeap::Exists(item) +{ + /* Brute-force find the item (there is no faster way, as we don't have the priority number) */ + foreach (node in _queue) { + if (node[0] == item) return true; + } + + return false; +} + + + +function BinaryHeap::_BubbleDown() +{ + if (_count == 0) return; + + local hole = 1; + local tmp = _queue[0]; + + /* Start switching parent and child until the tree is restored */ + while (hole * 2 < _count + 1) { + local child = hole * 2; + if (child != _count && _queue[child][1] <= _queue[child - 1][1]) child++; + if (_queue[child - 1][1] > tmp[1]) break; + + _queue[hole - 1] = _queue[child - 1]; + hole = child; + } + /* The top value is now at his new place */ + _queue[hole - 1] = tmp; +} diff --git a/bin/ai/library/queue/fibonacci_heap/library.nut b/bin/ai/library/queue/fibonacci_heap/library.nut new file mode 100644 index 000000000..1ea7260e0 --- /dev/null +++ b/bin/ai/library/queue/fibonacci_heap/library.nut @@ -0,0 +1,12 @@ +/* $Id$ */ + +class FibonacciHeap extends AILibrary { + function GetAuthor() { return "OpenTTD NoAI Developers Team"; } + function GetName() { return "Fibonacci Heap"; } + function GetDescription() { return "An implementation of a Fibonacci Heap"; } + function GetVersion() { return 1; } + function GetDate() { return "2008-08-22"; } + function CreateInstance() { return "FibonacciHeap"; } +} + +RegisterLibrary(FibonacciHeap()); diff --git a/bin/ai/library/queue/fibonacci_heap/main.nut b/bin/ai/library/queue/fibonacci_heap/main.nut new file mode 100644 index 000000000..7c6b3ece2 --- /dev/null +++ b/bin/ai/library/queue/fibonacci_heap/main.nut @@ -0,0 +1,204 @@ +/* $Id$ */ + +/** + * Fibonacci heap. + * This heap is heavily optimized for the Insert and Pop functions. + * Peek and Pop always return the current lowest value in the list. + * Insert is implemented as a lazy insert, as it will simply add the new + * node to the root list. Sort is done on every Pop operation. + */ +class FibonacciHeap { + _min = null; + _min_index = 0; + _min_priority = 0; + _count = 0; + _root_list = null; + + /** + * Create a new fibonacci heap. + * http://en.wikipedia.org/wiki/Fibonacci_heap + */ + constructor() { + _count = 0; + _min = Node(); + _min.priority = 0x7FFFFFFF; + _min_index = 0; + _min_priority = 0x7FFFFFFF; + _root_list = []; + } + + /** + * Insert a new entry in the heap. + * The complexity of this operation is O(1). + * @param item The item to add to the list. + * @param priority The priority this item has. + */ + function Insert(item, priority); + + /** + * Pop the first entry of the list. + * This is always the item with the lowest priority. + * The complexity of this operation is O(ln n). + * @return The item of the entry with the lowest priority. + */ + function Pop(); + + /** + * Peek the first entry of the list. + * This is always the item with the lowest priority. + * The complexity of this operation is O(1). + * @return The item of the entry with the lowest priority. + */ + function Peek(); + + /** + * Get the amount of current items in the list. + * The complexity of this operation is O(1). + * @return The amount of items currently in the list. + */ + function Count(); + + /** + * Check if an item exists in the list. + * The complexity of this operation is O(n). + * @param item The item to check for. + * @return True if the item is already in the list. + */ + function Exists(item); +}; + +function FibonacciHeap::Insert(item, priority) { + /* Create a new node instance to add to the heap. */ + local node = Node(); + /* Changing params is faster than using constructor values */ + node.item = item; + node.priority = priority; + + /* Update the reference to the minimum node if this node has a + * smaller priority. */ + if (_min_priority > priority) { + _min = node; + _min_index = _root_list.len(); + _min_priority = priority; + } + + _root_list.append(node); + _count++; +} + +function FibonacciHeap::Pop() { + + if (_count == 0) return null; + + /* Bring variables from the class scope to this scope explicitly to + * optimize variable lookups by Squirrel. */ + local z = _min; + local tmp_root_list = _root_list; + + /* If there are any children, bring them all to the root level. */ + tmp_root_list.extend(z.child); + + /* Remove the minimum node from the rootList. */ + tmp_root_list.remove(_min_index); + local root_cache = {}; + + /* Now we decrease the number of nodes on the root level by + * merging nodes which have the same degree. The node with + * the lowest priority value will become the parent. */ + foreach(x in tmp_root_list) { + local y; + + /* See if we encountered a node with the same degree already. */ + while (y = root_cache.rawdelete(x.degree)) { + /* Check the priorities. */ + if (x.priority > y.priority) { + local tmp = x; + x = y; + y = tmp; + } + + /* Make y a child of x. */ + x.child.append(y); + x.degree++; + } + + root_cache[x.degree] <- x; + } + + /* The root_cache contains all the nodes which will form the + * new rootList. We reset the priority to the maximum number + * for a 32 signed integer to find a new minumum. */ + tmp_root_list.resize(root_cache.len()); + local i = 0; + local tmp_min_priority = 0x7FFFFFFF; + + /* Now we need to find the new minimum among the root nodes. */ + foreach (val in root_cache) { + if (val.priority < tmp_min_priority) { + _min = val; + _min_index = i; + tmp_min_priority = val.priority; + } + + tmp_root_list[i++] = val; + } + + /* Update global variables. */ + _min_priority = tmp_min_priority; + + _count--; + return z.item; +} + +function FibonacciHeap::Peek() { + if (_count == 0) return null; + return _min.item; +} + +function FibonacciHeap::Count() { + return _count; +} + +function FibonacciHeap::Exists(item) { + return ExistsIn(_root_list, item); +} + +/** + * Auxilary function to search through the whole heap. + * @param list The list of nodes to look through. + * @param item The item to search for. + * @return True if the item is found, false otherwise. + */ +function FibonacciHeap::ExistsIn(list, item) { + + foreach (val in list) { + if (val.item == item) { + return true; + } + + foreach (c in val.child) { + if (ExistsIn(c, item)) { + return true; + } + } + } + + /* No luck, item doesn't exists in the tree rooted under list. */ + return false; +} + +/** + * Basic class the fibonacci heap is composed of. + */ +class FibonacciHeap.Node { + degree = null; + child = null; + + item = null; + priority = null; + + constructor() { + child = []; + degree = 0; + } +}; diff --git a/bin/ai/library/queue/priority_queue/library.nut b/bin/ai/library/queue/priority_queue/library.nut new file mode 100644 index 000000000..a8c615ed1 --- /dev/null +++ b/bin/ai/library/queue/priority_queue/library.nut @@ -0,0 +1,12 @@ +/* $Id$ */ + +class PriorityQueue extends AILibrary { + function GetAuthor() { return "OpenTTD NoAI Developers Team"; } + function GetName() { return "Priority Queue"; } + function GetDescription() { return "An implementation of a Priority Queue"; } + function GetVersion() { return 2; } + function GetDate() { return "2008-06-10"; } + function CreateInstance() { return "PriorityQueue"; } +} + +RegisterLibrary(PriorityQueue()); diff --git a/bin/ai/library/queue/priority_queue/main.nut b/bin/ai/library/queue/priority_queue/main.nut new file mode 100644 index 000000000..bafc93ac5 --- /dev/null +++ b/bin/ai/library/queue/priority_queue/main.nut @@ -0,0 +1,115 @@ +/* $Id$ */ + +/** + * Priority Queue. + * Peek and Pop always return the current lowest value in the list. + * Sort is done on insertion only. + */ +class PriorityQueue +{ + _queue = null; + _count = 0; + + constructor() + { + _count = 0; + _queue = []; + } + + /** + * Insert a new entry in the list. + * The complexity of this operation is O(n). + * @param item The item to add to the list. + * @param priority The priority this item has. + */ + function Insert(item, priority); + + /** + * Pop the first entry of the list. + * This is always the item with the lowest priority. + * The complexity of this operation is O(1). + * @return The item of the entry with the lowest priority. + */ + function Pop(); + + /** + * Peek the first entry of the list. + * This is always the item with the lowest priority. + * The complexity of this operation is O(1). + * @return The item of the entry with the lowest priority. + */ + function Peek(); + + /** + * Get the amount of current items in the list. + * The complexity of this operation is O(1). + * @return The amount of items currently in the list. + */ + function Count(); + + /** + * Check if an item exists in the list. + * The complexity of this operation is O(n). + * @param item The item to check for. + * @return True if the item is already in the list. + */ + function Exists(item); +}; + +function PriorityQueue::Insert(item, priority) +{ + /* Append dummy entry */ + _queue.append(0); + _count++; + + local i; + /* Find the point of insertion */ + for (i = _count - 2; i >= 0; i--) { + if (priority > _queue[i][1]) { + /* All items bigger move one place to the right */ + _queue[i + 1] = _queue[i]; + } else if (item == _queue[i][0]) { + /* Same item, ignore insertion */ + return false; + } else { + /* Found place to insert at */ + break; + } + } + /* Insert new pair */ + _queue[i + 1] = [item, priority]; + + return true; +} + +function PriorityQueue::Pop() +{ + if (_count == 0) return null; + + local node = _queue.pop(); + _count--; + + return node[0]; +} + +function PriorityQueue::Peek() +{ + if (_count == 0) return null; + + return _queue[_count - 1][0]; +} + +function PriorityQueue::Count() +{ + return _count; +} + +function PriorityQueue::Exists(item) +{ + /* Brute-force find the item (there is no faster way, as we don't have the priority number) */ + foreach (node in _queue) { + if (node[0] == item) return true; + } + + return false; +} -- cgit v1.2.3-70-g09d2