summaryrefslogtreecommitdiff
path: root/yapf
diff options
context:
space:
mode:
Diffstat (limited to 'yapf')
-rw-r--r--yapf/array.hpp69
-rw-r--r--yapf/autocopyptr.hpp82
-rw-r--r--yapf/binaryheap.hpp230
-rw-r--r--yapf/blob.hpp266
-rw-r--r--yapf/countedptr.hpp99
-rw-r--r--yapf/crc32.hpp63
-rw-r--r--yapf/fixedsizearray.hpp90
-rw-r--r--yapf/follow_track.cpp42
-rw-r--r--yapf/follow_track.hpp232
-rw-r--r--yapf/hashtable.hpp234
-rw-r--r--yapf/nodelist.hpp132
-rw-r--r--yapf/track_dir.hpp35
-rw-r--r--yapf/unittest/test_autocopyptr.h43
-rw-r--r--yapf/unittest/test_binaryheap.h103
-rw-r--r--yapf/unittest/test_blob.h61
-rw-r--r--yapf/unittest/test_fixedsizearray.h114
-rw-r--r--yapf/unittest/test_hashtable.h74
-rw-r--r--yapf/unittest/test_yapf.h350
-rw-r--r--yapf/unittest/unittest.cpp166
-rw-r--r--yapf/unittest/unittest.dsp172
-rw-r--r--yapf/unittest/unittest.h34
-rw-r--r--yapf/unittest/unittest.vcproj187
-rw-r--r--yapf/unittest/unittest_vs80.vcproj272
-rw-r--r--yapf/yapf.h54
-rw-r--r--yapf/yapf.hpp111
-rw-r--r--yapf/yapf_base.hpp329
-rw-r--r--yapf/yapf_common.cpp29
-rw-r--r--yapf/yapf_common.hpp144
-rw-r--r--yapf/yapf_costbase.hpp26
-rw-r--r--yapf/yapf_costcache.hpp183
-rw-r--r--yapf/yapf_costrail.hpp331
-rw-r--r--yapf/yapf_destrail.hpp129
-rw-r--r--yapf/yapf_node.hpp77
-rw-r--r--yapf/yapf_node_rail.hpp111
-rw-r--r--yapf/yapf_node_road.hpp36
-rw-r--r--yapf/yapf_rail.cpp265
-rw-r--r--yapf/yapf_road.cpp353
-rw-r--r--yapf/yapf_settings.h60
-rw-r--r--yapf/yapf_ship.cpp168
39 files changed, 5556 insertions, 0 deletions
diff --git a/yapf/array.hpp b/yapf/array.hpp
new file mode 100644
index 000000000..cfee3c3e6
--- /dev/null
+++ b/yapf/array.hpp
@@ -0,0 +1,69 @@
+/* $Id$ */
+
+#ifndef ARRAY_HPP
+#define ARRAY_HPP
+
+#include "fixedsizearray.hpp"
+
+/** Flexible array with size limit. Implemented as fixed size
+ array of fixed size arrays */
+template <class Titem_, int Tblock_size_ = 1024, int Tnum_blocks_ = Tblock_size_>
+class CArrayT {
+public:
+ typedef Titem_ Titem; ///< Titem is now visible from outside
+ typedef CFixedSizeArrayT<Titem_, Tblock_size_> CSubArray; ///< inner array
+ typedef CFixedSizeArrayT<CSubArray, Tnum_blocks_> CSuperArray; ///< outer array
+
+protected:
+ CSuperArray m_a; ///< array of arrays of items
+
+public:
+ ST_CONST(int, Tblock_size = Tblock_size_); ///< block size is now visible from outside
+ ST_CONST(int, Tnum_blocks = Tnum_blocks_); ///< number of blocks is now visible from outside
+ ST_CONST(int, Tcapacity = Tblock_size * Tnum_blocks); ///< total max number of items
+
+ /** implicit constructor */
+ FORCEINLINE CArrayT() { }
+ /** Return actual number of items */
+ FORCEINLINE int Size() const
+ {
+ int super_size = m_a.Size();
+ if (super_size == 0) return 0;
+ int sub_size = m_a[super_size - 1].Size();
+ return (super_size - 1) * Tblock_size + sub_size;
+ }
+ /** return true if array is empty */
+ FORCEINLINE bool IsEmpty() { return m_a.IsEmpty(); }
+ /** return true if array is full */
+ FORCEINLINE bool IsFull() { return m_a.IsFull() && m_a[Tnum_blocks - 1].IsFull(); }
+ /** return first sub-array with free space for new item */
+ FORCEINLINE CSubArray& FirstFreeSubArray()
+ {
+ int super_size = m_a.Size();
+ if (super_size > 0) {
+ CSubArray& sa = m_a[super_size - 1];
+ if (!sa.IsFull()) return sa;
+ }
+ return m_a.Add();
+ }
+ /** allocate but not construct new item */
+ FORCEINLINE Titem_& AddNC() { return FirstFreeSubArray().AddNC(); }
+ /** allocate and construct new item */
+ FORCEINLINE Titem_& Add() { return FirstFreeSubArray().Add(); }
+ /** indexed access (non-const) */
+ FORCEINLINE Titem& operator [] (int idx)
+ {
+ CSubArray& sa = m_a[idx / Tblock_size];
+ Titem& item = sa [idx % Tblock_size];
+ return item;
+ }
+ /** indexed access (const) */
+ FORCEINLINE const Titem& operator [] (int idx) const
+ {
+ CSubArray& sa = m_a[idx / Tblock_size];
+ Titem& item = sa [idx % Tblock_size];
+ return item;
+ }
+};
+
+#endif /* ARRAY_HPP */
diff --git a/yapf/autocopyptr.hpp b/yapf/autocopyptr.hpp
new file mode 100644
index 000000000..2206ca00f
--- /dev/null
+++ b/yapf/autocopyptr.hpp
@@ -0,0 +1,82 @@
+/* $Id$ */
+
+#ifndef AUTOCOPYPTR_HPP
+#define AUTOCOPYPTR_HPP
+
+/** CAutoCopyPtrT - kind of CoW (Copy on Write) pointer.
+ It is non-invasive smart pointer (reference counter is held outside
+ of Tdata).
+ When copied, its new copy shares the same underlaying structure Tdata.
+ When dereferenced, its behavior depends on 2 factors:
+ - whether the data is shared (used by more than one pointer)
+ - type of access (read/write)
+ When shared pointer is dereferenced for write, new clone of Tdata
+ is made first.
+ Can't be used for polymorphic data types (interfaces).
+*/
+template <class Tdata_>
+class CAutoCopyPtrT {
+protected:
+ typedef Tdata_ Tdata;
+
+ struct CItem {
+ int m_ref_cnt; ///< reference counter
+ Tdata m_data; ///< custom data itself
+
+ FORCEINLINE CItem() : m_ref_cnt(1) {};
+ FORCEINLINE CItem(const Tdata& data) : m_ref_cnt(1), m_data(data) {};
+ FORCEINLINE CItem(const CItem& src) : m_ref_cnt(1), m_data(src.m_data) {};
+ };
+
+ mutable CItem* m_pI; ///< points to the ref-counted data
+
+public:
+ FORCEINLINE CAutoCopyPtrT() : m_pI(NULL) {};
+ FORCEINLINE CAutoCopyPtrT(const Tdata& data) : m_pI(new CItem(data)) {};
+ FORCEINLINE CAutoCopyPtrT(const CAutoCopyPtrT& src) : m_pI(src.m_pI) {if (m_pI != NULL) m_pI->m_ref_cnt++;}
+ FORCEINLINE ~CAutoCopyPtrT() {if (m_pI == NULL || (--m_pI->m_ref_cnt) > 0) return; delete m_pI; m_pI = NULL;}
+
+ /** data accessor (read only) */
+ FORCEINLINE const Tdata& GetDataRO() const {if (m_pI == NULL) m_pI = new CItem(); return m_pI->m_data;}
+ /** data accessor (read / write) */
+ FORCEINLINE Tdata& GetDataRW() {CloneIfShared(); if (m_pI == NULL) m_pI = new CItem(); return m_pI->m_data;}
+
+ /** clone data if it is shared */
+ FORCEINLINE void CloneIfShared()
+ {
+ if (m_pI != NULL && m_pI->m_ref_cnt > 1) {
+ // we share data item with somebody, clone it to become an exclusive owner
+ CItem* pNewI = new CItem(*m_pI);
+ m_pI->m_ref_cnt--;
+ m_pI = pNewI;
+ }
+ }
+
+ /** assign pointer from the other one (maintaining ref counts) */
+ FORCEINLINE void Assign(const CAutoCopyPtrT& src)
+ {
+ if (m_pI == src.m_pI) return;
+ if (m_pI != NULL && (--m_pI->m_ref_cnt) <= 0) delete m_pI;
+ m_pI = src.m_pI;
+ if (m_pI != NULL) m_pI->m_ref_cnt++;
+ }
+
+ /** dereference operator (read only) */
+ FORCEINLINE const Tdata* operator -> () const {return &GetDataRO();}
+ /** dereference operator (read / write) */
+ FORCEINLINE Tdata* operator -> () {return &GetDataRW();}
+
+ /** assignment operator */
+ FORCEINLINE CAutoCopyPtrT& operator = (const CAutoCopyPtrT& src) {Assign(src); return *this;}
+
+ /** forwarding 'lower then' operator to the underlaying items */
+ FORCEINLINE bool operator < (const CAutoCopyPtrT& other) const
+ {
+ assert(m_pI != NULL);
+ assert(other.m_pI != NULL);
+ return (m_pI->m_data) < (other.m_pI->m_data);
+ }
+};
+
+
+#endif /* AUTOCOPYPTR_HPP */
diff --git a/yapf/binaryheap.hpp b/yapf/binaryheap.hpp
new file mode 100644
index 000000000..d2ef6e4b8
--- /dev/null
+++ b/yapf/binaryheap.hpp
@@ -0,0 +1,230 @@
+/* $Id$ */
+
+#ifndef BINARYHEAP_HPP
+#define BINARYHEAP_HPP
+
+#include <new>
+
+//void* operator new (size_t size, void* p) {return p;}
+#if defined(_MSC_VER) && (_MSC_VER >= 1400)
+//void operator delete (void* p, void* p2) {}
+#endif
+
+
+/**
+* Binary Heap as C++ template.
+*
+* For information about Binary Heap algotithm,
+* see: http://www.policyalmanac.org/games/binaryHeaps.htm
+*
+* Implementation specific notes:
+*
+* 1) It allocates space for item pointers (array). Items are allocated elsewhere.
+*
+* 2) ItemPtr [0] is never used. Total array size is max_items + 1, because we
+* use indices 1..max_items instead of zero based C indexing.
+*
+* 3) Item of the binary heap should support these public members:
+* - 'lower-then' operator '<' - used for comparing items before moving
+*
+*/
+
+template <class Titem_>
+class CBinaryHeapT {
+public:
+ typedef Titem_ *ItemPtr;
+private:
+ int m_size; ///< Number of items in the heap
+ int m_max_size; ///< Maximum number of items the heap can hold
+ ItemPtr* m_items; ///< The heap item pointers
+
+public:
+ explicit CBinaryHeapT(int max_items = 102400)
+ : m_size(0)
+ , m_max_size(max_items)
+ {
+ m_items = new ItemPtr[max_items + 1];
+ }
+
+ ~CBinaryHeapT()
+ {
+ Clear();
+ delete [] m_items;
+ m_items = NULL;
+ }
+
+public:
+ /** Return the number of items stored in the priority queue.
+ * @return number of items in the queue */
+ FORCEINLINE int Size() const {return m_size;};
+
+ /** Test if the priority queue is empty.
+ * @return true if empty */
+ FORCEINLINE bool IsEmpty() const {return (m_size == 0);};
+
+ /** Test if the priority queue is full.
+ * @return true if full. */
+ FORCEINLINE bool IsFull() const {return (m_size >= m_max_size);};
+
+ /** Find the smallest item in the priority queue.
+ * Return the smallest item, or throw assert if empty. */
+ FORCEINLINE Titem_& GetHead() {assert(!IsEmpty()); return *m_items[1];}
+
+ /** Insert new item into the priority queue, maintaining heap order.
+ * @return false if the queue is full. */
+ bool Push(Titem_& new_item);
+
+ /** Remove and return the smallest item from the priority queue. */
+ FORCEINLINE Titem_& PopHead() {Titem_& ret = GetHead(); RemoveHead(); return ret;};
+
+ /** Remove the smallest item from the priority queue. */
+ void RemoveHead();
+
+ /** Remove item specified by index */
+ void RemoveByIdx(int idx);
+
+ /** return index of the item that matches (using &item1 == &item2) the given item. */
+ int FindLinear(const Titem_& item) const;
+
+ /** Make the priority queue empty.
+ * All remaining items will remain untouched. */
+ void Clear() {m_size = 0;};
+
+ /** verifies the heap consistency (added during first YAPF debug phase) */
+ void CheckConsistency();
+};
+
+
+template <class Titem_>
+FORCEINLINE bool CBinaryHeapT<Titem_>::Push(Titem_& new_item)
+{
+ if (IsFull()) return false;
+
+ // make place for new item
+ int gap = ++m_size;
+ // Heapify up
+ for (int parent = gap / 2; (parent > 0) && (new_item < *m_items[parent]); gap = parent, parent /= 2)
+ m_items[gap] = m_items[parent];
+ m_items[gap] = &new_item;
+ CheckConsistency();
+ return true;
+}
+
+template <class Titem_>
+FORCEINLINE void CBinaryHeapT<Titem_>::RemoveHead()
+{
+ assert(!IsEmpty());
+
+ // at index 1 we have a gap now
+ int gap = 1;
+
+ // Heapify down:
+ // last item becomes a candidate for the head. Call it new_item.
+ Titem_& new_item = *m_items[m_size--];
+
+ // now we must maintain relation between parent and its children:
+ // parent <= any child
+ // from head down to the tail
+ int child = 2; // first child is at [parent * 2]
+
+ // while children are valid
+ while (child <= m_size) {
+ // choose the smaller child
+ if (child < m_size && *m_items[child + 1] < *m_items[child])
+ child++;
+ // is it smaller than our parent?
+ if (!(*m_items[child] < new_item)) {
+ // the smaller child is still bigger or same as parent => we are done
+ break;
+ }
+ // if smaller child is smaller than parent, it will become new parent
+ m_items[gap] = m_items[child];
+ gap = child;
+ // where do we have our new children?
+ child = gap * 2;
+ }
+ // move last item to the proper place
+ if (m_size > 0) m_items[gap] = &new_item;
+ CheckConsistency();
+}
+
+template <class Titem_>
+inline void CBinaryHeapT<Titem_>::RemoveByIdx(int idx)
+{
+ // at position idx we have a gap now
+ int gap = idx;
+ Titem_& last = *m_items[m_size];
+ if (idx < m_size) {
+ assert(idx >= 1);
+ m_size--;
+ // and the candidate item for fixing this gap is our last item 'last'
+ // Move gap / last item up:
+ while (gap > 1)
+ {
+ // compare [gap] with its parent
+ int parent = gap / 2;
+ if (last < *m_items[parent]) {
+ m_items[gap] = m_items[parent];
+ gap = parent;
+ } else {
+ // we don't need to continue upstairs
+ break;
+ }
+ }
+
+ // Heapify (move gap) down:
+ while (true) {
+ // where we do have our children?
+ int child = gap * 2; // first child is at [parent * 2]
+ if (child > m_size) break;
+ // choose the smaller child
+ if (child < m_size && *m_items[child + 1] < *m_items[child])
+ child++;
+ // is it smaller than our parent?
+ if (!(*m_items[child] < last)) {
+ // the smaller child is still bigger or same as parent => we are done
+ break;
+ }
+ // if smaller child is smaller than parent, it will become new parent
+ m_items[gap] = m_items[child];
+ gap = child;
+ }
+ // move parent to the proper place
+ if (m_size > 0) m_items[gap] = &last;
+ }
+ else {
+ assert(idx == m_size);
+ m_size--;
+ }
+ CheckConsistency();
+}
+
+template <class Titem_>
+inline int CBinaryHeapT<Titem_>::FindLinear(const Titem_& item) const
+{
+ if (IsEmpty()) return 0;
+ for (ItemPtr *ppI = m_items + 1, *ppLast = ppI + m_size; ppI <= ppLast; ppI++) {
+ if (*ppI == &item) {
+ return ppI - m_items;
+ }
+ }
+ return 0;
+}
+
+template <class Titem_>
+FORCEINLINE void CBinaryHeapT<Titem_>::CheckConsistency()
+{
+ // enable it if you suspect binary heap doesn't work well
+#if 0
+ for (int child = 2; child <= m_size; child++) {
+ int parent = child / 2;
+ assert(!(m_items[child] < m_items[parent]));
+ }
+#endif
+}
+
+
+#endif /* BINARYHEAP_HPP */
+
+
+
diff --git a/yapf/blob.hpp b/yapf/blob.hpp
new file mode 100644
index 000000000..e454401c4
--- /dev/null
+++ b/yapf/blob.hpp
@@ -0,0 +1,266 @@
+/* $Id$ */
+
+#ifndef BLOB_HPP
+#define BLOB_HPP
+
+template <class Titem_>
+FORCEINLINE void MemCpyT(Titem_* d, const Titem_* s, int num_items = 1)
+{
+ memcpy(d, s, num_items * sizeof(Titem_));
+}
+
+
+/** Base class for simple binary blobs.
+ Item is byte.
+ The word 'simple' means:
+ - no configurable allocator type (always made from heap)
+ - no smart deallocation - deallocation must be called from the same
+ module (DLL) where the blob was allocated
+ - no configurable allocation policy (how big blocks should be allocated)
+ - no extra ownership policy (i.e. 'copy on write') when blob is copied
+ - no thread synchronization at all */
+class CBlobBaseSimple {
+protected:
+ struct CHdr {
+ int m_size; // actual blob size in bytes
+ int m_max_size; // maximum (allocated) size in bytes
+ };
+
+ union {
+ int8 *m_pData;
+ CHdr *m_pHdr_1;
+ } ptr_u;
+
+public:
+ ST_CONST(int, Ttail_reserve = 4); // four extra bytes will be always allocated and zeroed at the end
+
+ FORCEINLINE CBlobBaseSimple() { InitEmpty(); }
+ FORCEINLINE CBlobBaseSimple(const CBlobBaseSimple& src)
+ {
+ InitEmpty();
+ AppendRaw(src);
+ }
+ FORCEINLINE ~CBlobBaseSimple() { Free(); }
+protected:
+ FORCEINLINE void InitEmpty() { static CHdr hdrEmpty[] = {{0, 0}, {0, 0}}; ptr_u.m_pHdr_1 = &hdrEmpty[1]; }
+ FORCEINLINE void Init(CHdr* hdr) { ptr_u.m_pHdr_1 = &hdr[1]; }
+ FORCEINLINE CHdr& Hdr() { return ptr_u.m_pHdr_1[-1]; }
+ FORCEINLINE const CHdr& Hdr() const { return ptr_u.m_pHdr_1[-1]; }
+ FORCEINLINE int& RawSizeRef() { return Hdr().m_size; };
+
+public:
+ FORCEINLINE bool IsEmpty() const { return RawSize() == 0; }
+ FORCEINLINE int RawSize() const { return Hdr().m_size; };
+ FORCEINLINE int MaxRawSize() const { return Hdr().m_max_size; };
+ FORCEINLINE int8* RawData() { return ptr_u.m_pData; }
+ FORCEINLINE const int8* RawData() const { return ptr_u.m_pData; }
+ FORCEINLINE uint32 Crc32() const {return CCrc32::Calc(RawData(), RawSize());}
+ FORCEINLINE void Clear() { RawSizeRef() = 0; }
+ FORCEINLINE void Free() { if (MaxRawSize() > 0) {RawFree(&Hdr()); InitEmpty();} }
+ FORCEINLINE void CopyFrom(const CBlobBaseSimple& src) { Clear(); AppendRaw(src); }
+ FORCEINLINE void MoveFrom(CBlobBaseSimple& src) { Free(); ptr_u.m_pData = src.ptr_u.m_pData; src.InitEmpty(); }
+ FORCEINLINE void Swap(CBlobBaseSimple& src) { int8 *tmp = ptr_u.m_pData; ptr_u.m_pData = src.ptr_u.m_pData; src.ptr_u.m_pData = tmp; }
+
+ FORCEINLINE void AppendRaw(int8 *p, int num_bytes)
+ {
+ assert(p != NULL);
+ if (num_bytes > 0) {
+ memcpy(GrowRawSize(num_bytes), p, num_bytes);
+ } else {
+ assert(num_bytes >= 0);
+ }
+ }
+
+ FORCEINLINE void AppendRaw(const CBlobBaseSimple& src)
+ {
+ if (!src.IsEmpty())
+ memcpy(GrowRawSize(src.RawSize()), src.RawData(), src.RawSize());
+ }
+
+ /** Reallocate if there is no free space for num_bytes bytes.
+ @return pointer to the new data to be added */
+ FORCEINLINE int8* MakeRawFreeSpace(int num_bytes)
+ {
+ assert(num_bytes >= 0);
+ int new_size = RawSize() + num_bytes;
+ if (new_size > MaxRawSize()) SmartAlloc(new_size);
+ FixTail();
+ return ptr_u.m_pData + RawSize();
+ }
+
+ /** Increase RawSize() by num_bytes.
+ @return pointer to the new data added */
+ FORCEINLINE int8* GrowRawSize(int num_bytes)
+ {
+ int8* pNewData = MakeRawFreeSpace(num_bytes);
+ RawSizeRef() += num_bytes;
+ return pNewData;
+ }
+
+ /** Decrease RawSize() by num_bytes. */
+ FORCEINLINE void ReduceRawSize(int num_bytes)
+ {
+ if (MaxRawSize() > 0 && num_bytes > 0) {
+ assert(num_bytes <= RawSize());
+ if (num_bytes < RawSize()) RawSizeRef() -= num_bytes;
+ else RawSizeRef() = 0;
+ }
+ }
+ /** reallocate blob data if needed */
+ void SmartAlloc(int new_size)
+ {
+ int old_max_size = MaxRawSize();
+ if (old_max_size >= new_size) return;
+ // calculate minimum block size we need to allocate
+ int min_alloc_size = sizeof(CHdr) + new_size + Ttail_reserve;
+ // ask allocation policy for some reasonable block size
+ int alloc_size = AllocPolicy(min_alloc_size);
+ // allocate new block
+ CHdr* pNewHdr = RawAlloc(alloc_size);
+ // setup header
+ pNewHdr->m_size = RawSize();
+ pNewHdr->m_max_size = alloc_size - (sizeof(CHdr) + Ttail_reserve);
+ // copy existing data
+ if (RawSize() > 0)
+ memcpy(pNewHdr + 1, ptr_u.m_pData, pNewHdr->m_size);
+ // replace our block with new one
+ CHdr* pOldHdr = &Hdr();
+ Init(pNewHdr);
+ if (old_max_size > 0)
+ RawFree(pOldHdr);
+ }
+ /** simple allocation policy - can be optimized later */
+ FORCEINLINE static int AllocPolicy(int min_alloc)
+ {
+ if (min_alloc < (1 << 9)) {
+ if (min_alloc < (1 << 5)) return (1 << 5);
+ return (min_alloc < (1 << 7)) ? (1 << 7) : (1 << 9);
+ }
+ if (min_alloc < (1 << 15)) {
+ if (min_alloc < (1 << 11)) return (1 << 11);
+ return (min_alloc < (1 << 13)) ? (1 << 13) : (1 << 15);
+ }
+ if (min_alloc < (1 << 20)) {
+ if (min_alloc < (1 << 17)) return (1 << 17);
+ return (min_alloc < (1 << 19)) ? (1 << 19) : (1 << 20);
+ }
+ min_alloc = (min_alloc | ((1 << 20) - 1)) + 1;
+ return min_alloc;
+ }
+
+ /** all allocation should happen here */
+ static FORCEINLINE CHdr* RawAlloc(int num_bytes) { return (CHdr*)malloc(num_bytes); }
+ /** all deallocations should happen here */
+ static FORCEINLINE void RawFree(CHdr* p) { free(p); }
+ /** fixing the four bytes at the end of blob data - useful when blob is used to hold string */
+ FORCEINLINE void FixTail()
+ {
+ if (MaxRawSize() > 0) {
+ int8 *p = &ptr_u.m_pData[RawSize()];
+ for (int i = 0; i < Ttail_reserve; i++) p[i] = 0;
+ }
+ }
+};
+
+template <class Titem_, class Tbase_ = CBlobBaseSimple>
+class CBlobT : public CBlobBaseSimple {
+ // make template arguments public:
+public:
+ typedef Titem_ Titem;
+ typedef Tbase_ Tbase;
+
+ ST_CONST(int, Titem_size = sizeof(Titem));
+
+ FORCEINLINE CBlobT() : Tbase() {}
+ FORCEINLINE CBlobT(const Tbase& src) : Tbase(src) {assert((RawSize() % Titem_size) == 0);}
+ FORCEINLINE ~CBlobT() { Free(); }
+ FORCEINLINE void CheckIdx(int idx) { assert(idx >= 0); assert(idx < Size()); }
+ FORCEINLINE Titem* Data() { return (Titem*)RawData(); }
+ FORCEINLINE const Titem* Data() const { return (const Titem*)RawData(); }
+ FORCEINLINE Titem* Data(int idx) { CheckIdx(idx); return (Data() + idx); }
+ FORCEINLINE const Titem* Data(int idx) const { CheckIdx(idx); return (Data() + idx); }
+ FORCEINLINE int Size() const { return (RawSize() / Titem_size); }
+ FORCEINLINE void Free()
+ {
+ assert((RawSize() % Titem_size) == 0);
+ int old_size = Size();
+ if (old_size > 0) {
+ // destroy removed items;
+ Titem* pI_last_to_destroy = Data(0);
+ for (Titem* pI = Data(old_size - 1); pI >= pI_last_to_destroy; pI--) pI->~Titem_();
+ }
+ Tbase::Free();
+ }
+ FORCEINLINE Titem* GrowSizeNC(int num_items) { return (Titem*)GrowRawSize(num_items * Titem_size); }
+ FORCEINLINE Titem* GrowSizeC(int num_items)
+ {
+ Titem* pI = GrowSizeNC(num_items);
+ for (int i = num_items; i > 0; i--, pI++) new (pI) Titem();
+ }
+ FORCEINLINE void ReduceSize(int num_items)
+ {
+ assert((RawSize() % Titem_size) == 0);
+ int old_size = Size();
+ assert(num_items <= old_size);
+ int new_size = (num_items <= old_size) ? (old_size - num_items) : 0;
+ // destroy removed items;
+ Titem* pI_last_to_destroy = Data(new_size);
+ for (Titem* pI = Data(old_size - 1); pI >= pI_last_to_destroy; pI--) pI->~Titem();
+ // remove them
+ ReduceRawSize(num_items * Titem_size);
+ }
+ FORCEINLINE Titem* AppendNew()
+ {
+ Titem& dst = *GrowSizeNC(1);
+ Titem* pNewItem = new (&dst) Titem();
+ return pNewItem;
+ }
+ FORCEINLINE Titem* Append(const Titem& src)
+ {
+ Titem& dst = *GrowSizeNC(1);
+ Titem* pNewItem = new (&dst) Titem(src);
+ return pNewItem;
+ }
+ FORCEINLINE Titem* Append(const Titem* pSrc, int num_items)
+ {
+ Titem* pDst = GrowSizeNC(num_items);
+ Titem* pDstOrg = pDst;
+ Titem* pDstEnd = pDst + num_items;
+ while (pDst < pDstEnd) new (pDst++) Titem(*(pSrc++));
+ return pDstOrg;
+ }
+ FORCEINLINE void RemoveBySwap(int idx)
+ {
+ CheckIdx(idx);
+ // destroy removed item
+ Titem* pRemoved = Data(idx);
+ RemoveBySwap(pRemoved);
+ }
+ FORCEINLINE void RemoveBySwap(Titem* pItem)
+ {
+ Titem* pLast = Data(Size() - 1);
+ assert(pItem >= Data() && pItem <= pLast);
+ // move last item to its new place
+ if (pItem != pLast) {
+ pItem->~Titem_();
+ new (pItem) Titem_(*pLast);
+ }
+ // destroy the last item
+ pLast->~Titem_();
+ // and reduce the raw blob size
+ ReduceRawSize(Titem_size);
+ }
+ FORCEINLINE Titem* MakeFreeSpace(int num_items) { return (Titem*)MakeRawFreeSpace(num_items * Titem_size); }
+};
+
+// simple string implementation
+struct CStrA : public CBlobT<char>
+{
+ typedef CBlobT<char> base;
+ CStrA(const char* str = NULL) {Append(str);}
+ FORCEINLINE CStrA(const CBlobBaseSimple& src) : base(src) {}
+ void Append(const char* str) {if (str != NULL && str[0] != '\0') base::Append(str, (int)strlen(str));}
+};
+
+#endif /* BLOB_HPP */
+
diff --git a/yapf/countedptr.hpp b/yapf/countedptr.hpp
new file mode 100644
index 000000000..7d9f61fc2
--- /dev/null
+++ b/yapf/countedptr.hpp
@@ -0,0 +1,99 @@
+/* $Id$ */
+
+#ifndef COUNTEDPTR_HPP
+#define COUNTEDPTR_HPP
+
+/** @file CCountedPtr - smart pointer implementation */
+
+/** CCountedPtr - simple reference counting smart pointer.
+*
+* One of the standard ways how to maintain object's lifetime.
+*
+* See http://ootips.org/yonat/4dev/smart-pointers.html for more
+* general info about smart pointers.
+*
+* This class implements ref-counted pointer for objects/interfaces that
+* support AddRef() and Release() methods.
+*/
+template <class Tcls_>
+class CCountedPtr {
+ /** redefine the template argument to make it visible for derived classes */
+public:
+ typedef Tcls_ Tcls;
+
+protected:
+ /** here we hold our pointer to the target */
+ Tcls* m_pT;
+
+public:
+ /** default (NULL) construct or construct from a raw pointer */
+ FORCEINLINE CCountedPtr(Tcls* pObj = NULL) : m_pT(pObj) {AddRef();};
+
+ /** copy constructor (invoked also when initializing from another smart ptr) */
+ FORCEINLINE CCountedPtr(const CCountedPtr& src) : m_pT(src.m_pT) {AddRef();};
+
+ /** destructor releasing the reference */
+ FORCEINLINE ~CCountedPtr() {Release();};
+
+protected:
+ /** add one ref to the underlaying object */
+ FORCEINLINE void AddRef() {if (m_pT != NULL) m_pT->AddRef();}
+
+public:
+ /** release smart pointer (and decrement ref count) if not null */
+ FORCEINLINE void Release() {if (m_pT != NULL) {m_pT->Release(); m_pT = NULL;}}
+
+ /** dereference of smart pointer - const way */
+ FORCEINLINE const Tcls* operator -> () const {assert(m_pT != NULL); return m_pT;};
+
+ /** dereference of smart pointer - non const way */
+ FORCEINLINE Tcls* operator -> () {assert(m_pT != NULL); return m_pT;};
+
+ /** raw pointer casting operator - const way */
+ FORCEINLINE operator const Tcls*() const {assert(m_pT == NULL); return m_pT;}
+
+ /** raw pointer casting operator - non-const way */
+ FORCEINLINE operator Tcls*() {assert(m_pT == NULL); return m_pT;}
+
+ /** operator & to support output arguments */
+ FORCEINLINE Tcls** operator &() {assert(m_pT == NULL); return &m_pT;}
+
+ /** assignment operator from raw ptr */
+ FORCEINLINE CCountedPtr& operator = (Tcls* pT) {Assign(pT); return *this;}
+
+ /** assignment operator from another smart ptr */
+ FORCEINLINE CCountedPtr& operator = (CCountedPtr& src) {Assign(src.m_pT); return *this;}
+
+ /** assignment operator helper */
+ FORCEINLINE void Assign(Tcls* pT);
+
+ /** one way how to test for NULL value */
+ FORCEINLINE bool IsNull() const {return m_pT == NULL;}
+
+ /** another way how to test for NULL value */
+ FORCEINLINE bool operator == (const CCountedPtr& sp) const {return m_pT == sp.m_pT;}
+
+ /** yet another way how to test for NULL value */
+ FORCEINLINE bool operator != (const CCountedPtr& sp) const {return m_pT != sp.m_pT;}
+
+ /** assign pointer w/o incrementing ref count */
+ FORCEINLINE void Attach(Tcls* pT) {Release(); m_pT = pT;}
+
+ /** detach pointer w/o decrementing ref count */
+ FORCEINLINE Tcls* Detach() {Tcls* pT = m_pT; m_pT = NULL; return pT;}
+};
+
+template <class Tcls_>
+FORCEINLINE void CCountedPtr<Tcls_>::Assign(Tcls* pT)
+{
+ // if they are the same, we do nothing
+ if (pT != m_pT) {
+ if (pT) pT->AddRef(); // AddRef new pointer if any
+ Tcls* pTold = m_pT; // save original ptr
+ m_pT = pT; // update m_pT to new value
+ if (pTold) pTold->Release(); // release old ptr if any
+ }
+}
+
+
+#endif /* COUNTEDPTR_HPP */
diff --git a/yapf/crc32.hpp b/yapf/crc32.hpp
new file mode 100644
index 000000000..b03ff5088
--- /dev/null
+++ b/yapf/crc32.hpp
@@ -0,0 +1,63 @@
+/* $Id$ */
+
+#ifndef CRC32_HPP
+#define CRC32_HPP
+
+struct CCrc32
+{
+ static uint32 Calc(const void *pBuffer, int nCount)
+ {
+ uint32 crc = 0xffffffff;
+ const uint32* pTable = CrcTable();
+
+ uint8* begin = (uint8*)pBuffer;
+ uint8* end = begin + nCount;
+ for(uint8* cur = begin; cur < end; cur++)
+ crc = (crc >> 8) ^ pTable[cur[0] ^ (uint8)(crc & 0xff)];
+ crc ^= 0xffffffff;
+
+ return crc;
+ }
+
+ static const uint32* CrcTable()
+ {
+ static const uint32 Table[256] =
+ {
+ 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
+ 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91,
+ 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
+ 0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5,
+ 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
+ 0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
+ 0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F,
+ 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D,
+ 0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
+ 0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
+ 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457,
+ 0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
+ 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB,
+ 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9,
+ 0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
+ 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD,
+ 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683,
+ 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
+ 0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7,
+ 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
+ 0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
+ 0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79,
+ 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236, 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F,
+ 0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
+ 0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
+ 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21,
+ 0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
+ 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45,
+ 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB,
+ 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
+ 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF,
+ 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
+ };
+ return Table;
+ }
+};
+
+#endif /* CRC32_HPP */
diff --git a/yapf/fixedsizearray.hpp b/yapf/fixedsizearray.hpp
new file mode 100644
index 000000000..9d67c6877
--- /dev/null
+++ b/yapf/fixedsizearray.hpp
@@ -0,0 +1,90 @@
+/* $Id$ */
+
+#ifndef FIXEDSIZEARRAY_HPP
+#define FIXEDSIZEARRAY_HPP
+
+
+/** fixed size array
+ Upon construction it preallocates fixed size block of memory
+ for all items, but doesn't construct them. Item's construction
+ is delayed. */
+template <class Titem_, int Tcapacity_>
+struct CFixedSizeArrayT {
+ /** the only member of fixed size array is pointer to the block
+ of C array of items. Header can be found on the offset -sizeof(CHdr). */
+ Titem_ *m_items;
+
+ /** header for fixed size array */
+ struct CHdr
+ {
+ int m_num_items; ///< number of items in the array
+ int m_ref_cnt; ///< block reference counter (used by copy constructor and by destructor)
+ };
+
+ // make types and constants visible from outside
+ typedef Titem_ Titem; // type of array item
+
+ ST_CONST(int, Tcapacity = Tcapacity_); // the array capacity (maximum size)
+ ST_CONST(int, TitemSize = sizeof(Titem_)); // size of item
+ ST_CONST(int, ThdrSize = sizeof(CHdr)); // size of header
+
+ /** Default constructor. Preallocate space for items and header, then initialize header. */
+ CFixedSizeArrayT()
+ {
+ // allocate block for header + items (don't construct items)
+ m_items = (Titem*)(((int8*)malloc(ThdrSize + Tcapacity * sizeof(Titem))) + ThdrSize);
+ SizeRef() = 0; // initial number of items
+ RefCnt() = 1; // initial reference counter
+ }
+
+ /** Copy constructor. Preallocate space for items and header, then initialize header. */
+ CFixedSizeArrayT(const CFixedSizeArrayT<Titem_, Tcapacity_>& src)
+ {
+ // share block (header + items) with the source array
+ m_items = const_cast<Titem*>(src.m_items); // here we break the 'const' modifier
+ RefCnt()++; // now we share block with the source
+ }
+
+ /** destroy remaining items and free the memory block */
+ ~CFixedSizeArrayT()
+ {
+ // release one reference to the shared block
+ if ((--RefCnt()) > 0) return; // and return if there is still some owner
+
+ // walk through all allocated items backward and destroy them
+ for (Titem* pItem = &m_items[Size() - 1]; pItem >= m_items; pItem--) {
+ pItem->~Titem_();
+ }
+ free(((int8*)m_items) - ThdrSize);
+ m_items = NULL;
+ }
+
+protected:
+ /** return reference to the array header (non-const) */
+ FORCEINLINE CHdr& Hdr() { return *(CHdr*)(((int8*)m_items) - ThdrSize); }
+ /** return reference to the array header (const) */
+ FORCEINLINE const CHdr& Hdr() const { return *(CHdr*)(((int8*)m_items) - ThdrSize); }
+ /** return reference to the block reference counter */
+ FORCEINLINE int& RefCnt() { return Hdr().m_ref_cnt; }
+ /** return reference to number of used items */
+ FORCEINLINE int& SizeRef() { return Hdr().m_num_items; }
+public:
+ /** return number of used items */
+ FORCEINLINE int Size() const { return Hdr().m_num_items; }
+ /** return true if array is full */
+ FORCEINLINE bool IsFull() const { return Size() >= Tcapacity; };
+ /** return true if array is empty */
+ FORCEINLINE bool IsEmpty() const { return Size() <= 0; };
+ /** index validation */
+ FORCEINLINE void CheckIdx(int idx) const { assert(idx >= 0); assert(idx < Size()); }
+ /** add (allocate), but don't construct item */
+ FORCEINLINE Titem& AddNC() { assert(!IsFull()); return m_items[SizeRef()++]; }
+ /** add and construct item using default constructor */
+ FORCEINLINE Titem& Add() { Titem& item = AddNC(); new(&item)Titem; return item; }
+ /** return item by index (non-const version) */
+ FORCEINLINE Titem& operator [] (int idx) { CheckIdx(idx); return m_items[idx]; }
+ /** return item by index (const version) */
+ FORCEINLINE const Titem& operator [] (int idx) const { CheckIdx(idx); return m_items[idx]; }
+};
+
+#endif /* FIXEDSIZEARRAY_HPP */
diff --git a/yapf/follow_track.cpp b/yapf/follow_track.cpp
new file mode 100644
index 000000000..26d90578e
--- /dev/null
+++ b/yapf/follow_track.cpp
@@ -0,0 +1,42 @@
+/* $Id$ */
+
+#include "../stdafx.h"
+#include "yapf.hpp"
+#include "follow_track.hpp"
+
+bool FollowTrackWater(FollowTrack_t *This, TileIndex old_tile, Trackdir old_td)
+{
+ CFollowTrackWater& F = *(CFollowTrackWater*) This;
+ return F.Follow(old_tile, old_td);
+}
+
+bool FollowTrackRoad(FollowTrack_t *This, TileIndex old_tile, Trackdir old_td)
+{
+ CFollowTrackRoad& F = *(CFollowTrackRoad*) This;
+ return F.Follow(old_tile, old_td);
+}
+
+bool FollowTrackRail(FollowTrack_t *This, TileIndex old_tile, Trackdir old_td)
+{
+ CFollowTrackRail& F = *(CFollowTrackRail*) This;
+ return F.Follow(old_tile, old_td);
+}
+
+bool FollowTrackWaterNo90(FollowTrack_t *This, TileIndex old_tile, Trackdir old_td)
+{
+ CFollowTrackWaterNo90& F = *(CFollowTrackWaterNo90*) This;
+ return F.Follow(old_tile, old_td);
+}
+
+bool FollowTrackRoadNo90(FollowTrack_t *This, TileIndex old_tile, Trackdir old_td)
+{
+ CFollowTrackRoadNo90& F = *(CFollowTrackRoadNo90*) This;
+ return F.Follow(old_tile, old_td);
+}
+
+bool FollowTrackRailNo90(FollowTrack_t *This, TileIndex old_tile, Trackdir old_td)
+{
+ CFollowTrackRailNo90& F = *(CFollowTrackRailNo90*) This;
+ return F.Follow(old_tile, old_td);
+}
+
diff --git a/yapf/follow_track.hpp b/yapf/follow_track.hpp
new file mode 100644
index 000000000..f09d8fde0
--- /dev/null
+++ b/yapf/follow_track.hpp
@@ -0,0 +1,232 @@
+/* $Id$ */
+
+#ifndef FOLLOW_TRACK_HPP
+#define FOLLOW_TRACK_HPP
+
+#include "yapf.hpp"
+
+/** Track follower helper template class (can serve pathfinders and vehicle
+ controllers). See 6 different typedefs below for 3 different transport
+ types w/ of w/o 90-deg turns allowed */
+template <TransportType Ttr_type_, bool T90deg_turns_allowed_ = true>
+struct CFollowTrackT : public FollowTrack_t
+{
+ CPerformanceTimer* m_pPerf;
+
+ FORCEINLINE CFollowTrackT(Vehicle* v = NULL, CPerformanceTimer* pPerf = NULL)
+ {
+ Init(v, pPerf);
+ }
+
+ FORCEINLINE void Init(Vehicle* v, CPerformanceTimer* pPerf)
+ {
+ assert(!IsRailTT() || (v != NULL && v->type == VEH_Train));
+ m_veh = v;
+ m_pPerf = pPerf;
+ // don't worry, all is inlined so compiler should remove unnecessary initializations
+ m_new_tile = INVALID_TILE;
+ m_new_td_bits = TRACKDIR_BIT_NONE;
+ m_exitdir = INVALID_DIAGDIR;
+ m_is_tunnel = false;
+ m_tunnel_tiles_skipped = 0;
+ }
+
+ FORCEINLINE static TransportType TT() {return Ttr_type_;}
+ FORCEINLINE static bool IsWaterTT() {return TT() == TRANSPORT_WATER;}
+ FORCEINLINE static bool IsRailTT() {return TT() == TRANSPORT_RAIL;}
+ FORCEINLINE static bool IsRoadTT() {return TT() == TRANSPORT_ROAD;}
+ FORCEINLINE static bool Allow90degTurns() {return T90deg_turns_allowed_;}
+
+ /** main follower routine. Fills all members and return true on success.
+ Otherwise returns false if track can't be followed. */
+ FORCEINLINE bool Follow(TileIndex old_tile, Trackdir old_td)
+ {
+ m_old_tile = old_tile;
+ m_old_td = old_td;
+ assert((GetTileTrackStatus(m_old_tile, TT()) & TrackdirToTrackdirBits(m_old_td)) != 0);
+ m_exitdir = TrackdirToExitdir(m_old_td);
+ if (EnteredRailDepot()) return true;
+ if (!CanExitOldTile()) return false;
+ FollowTileExit();
+ if (!QueryNewTileTrackStatus()) return false;
+ if (!CanEnterNewTile()) return false;
+ m_new_td_bits &= DiagdirReachesTrackdirs(m_exitdir);
+ if (!Allow90degTurns())
+ m_new_td_bits &= (TrackdirBits)~(int)TrackdirCrossesTrackdirs(m_old_td);
+ return (m_new_td_bits != TRACKDIR_BIT_NONE);
+ }
+
+protected:
+ /** Follow the m_exitdir from m_old_tile and fill m_new_tile and m_tunnel_tiles_skipped */
+ FORCEINLINE void FollowTileExit()
+ {
+ // extra handling for tunnels in our direction
+ if (IsTunnelTile(m_old_tile)) {
+ DiagDirection tunnel_enterdir = GetTunnelDirection(m_old_tile);
+ if (tunnel_enterdir == m_exitdir) {
+ // we are entering the tunnel
+ FindLengthOfTunnelResult flotr = FindLengthOfTunnel(m_old_tile, m_exitdir);
+ m_new_tile = flotr.tile;
+ m_is_tunnel = true;
+ m_tunnel_tiles_skipped = flotr.length - 1;
+ return;
+ }
+ assert(ReverseDiagDir(tunnel_enterdir) == m_exitdir);
+ }
+ // not a tunnel
+ m_is_tunnel = false;
+ m_tunnel_tiles_skipped = 0;
+ // normal tile
+ TileIndexDiff diff = TileOffsByDir(m_exitdir);
+ m_new_tile = TILE_ADD(m_old_tile, diff);
+ }
+
+ /** stores track status (available trackdirs) for the new tile into m_new_td_bits */
+ FORCEINLINE bool QueryNewTileTrackStatus()
+ {
+ CPerfStart perf(*m_pPerf);
+ if (GetTileType(m_new_tile) == MP_RAILWAY && IsPlainRailTile(m_new_tile)) {
+ m_new_td_bits = (TrackdirBits)(GetTrackBits(m_new_tile) * 0x101);
+ } else {
+ uint32 ts = GetTileTrackStatus(m_new_tile, TT());
+ m_new_td_bits = (TrackdirBits)(ts & TRACKDIR_BIT_MASK);
+ }
+ return (m_new_td_bits != TRACKDIR_BIT_NONE);
+ }
+
+ /** return true if we can leave m_old_tile in m_exitdir */
+ FORCEINLINE bool CanExitOldTile()
+ {
+ // road stop can be left at one direction only
+ if (IsRoadTT() && IsRoadStopTile(m_old_tile)) {
+ DiagDirection exitdir = GetRoadStopDir(m_old_tile);
+ if (exitdir != m_exitdir)
+ return false;
+ }
+
+ // road depots can be also left in one direction only
+ if (IsRoadTT() && IsTileDepotType(m_old_tile, TT())) {
+ DiagDirection exitdir = GetRoadDepotDirection(m_old_tile);
+ if (exitdir != m_exitdir)
+ return false;
+ }
+ return true;
+ }
+
+ /** return true if we can enter m_new_tile from m_exitdir */
+ FORCEINLINE bool CanEnterNewTile()
+ {
+ if (IsRoadTT() && IsRoadStopTile(m_new_tile)) {
+ // road stop can be entered from one direction only
+ DiagDirection exitdir = GetRoadStopDir(m_new_tile);
+ if (ReverseDiagDir(exitdir) != m_exitdir)
+ return false;
+ }
+
+ // road and rail depots can also be entered from one direction only
+ if (IsRoadTT() && IsTileDepotType(m_new_tile, TT())) {
+ DiagDirection exitdir = GetRoadDepotDirection(m_new_tile);
+ if (ReverseDiagDir(exitdir) != m_exitdir)
+ return false;
+ }
+ if (IsRailTT() && IsTileDepotType(m_new_tile, TT())) {
+ DiagDirection exitdir = GetRailDepotDirection(m_new_tile);
+ if (ReverseDiagDir(exitdir) != m_exitdir)
+ return false;
+ }
+
+ // rail transport is possible only on tiles with the same owner as vehicle
+ if (IsRailTT() && GetTileOwner(m_new_tile) != m_veh->owner) {
+ // different owner
+ if (IsBridgeTile(m_new_tile)) {
+ if (IsBridgeMiddle(m_new_tile)) {
+ // bridge middle has no owner - tile is owned by the owner of the under-bridge track
+ if (GetBridgeAxis(m_new_tile) != DiagDirToAxis(m_exitdir)) {
+ // so it must be under bridge track (and wrong owner)
+ return false;
+ }
+ // in the middle of the bridge - when we came here, it should be ok
+ } else {
+ // different owner, on the bridge ramp
+ return false;
+ }
+ } else {
+ // different owner, not a bridge
+ return false;
+ }
+ }
+
+ // rail transport is possible only on compatible rail types
+ if (IsRailTT()) {
+ RailType rail_type = GetTileRailType(m_new_tile, DiagdirToDiagTrackdir(m_exitdir));
+ if (((1 << rail_type) & m_veh->u.rail.compatible_railtypes) == 0) {
+ // incompatible rail type
+ return false;
+ }
+ }
+
+ // tunnel tiles can be entered only from proper direction
+ if (!IsWaterTT() && !m_is_tunnel && IsTunnelTile(m_new_tile)) {
+ DiagDirection tunnel_enterdir = GetTunnelDirection(m_new_tile);
+ if (tunnel_enterdir != m_exitdir)
+ return false;
+ }
+ return true;
+ }
+
+ FORCEINLINE bool EnteredRailDepot()
+ {
+ // rail depots cause reversing
+ if (IsRailTT() && IsTileDepotType(m_old_tile, TT())) {
+ DiagDirection exitdir = GetRailDepotDirection(m_old_tile);
+ if (exitdir != m_exitdir) {
+ // reverse
+ m_new_tile = m_old_tile;
+ m_new_td_bits = TrackdirToTrackdirBits(ReverseTrackdir(m_old_td));
+ m_exitdir = exitdir;
+ m_tunnel_tiles_skipped = 0;
+ m_is_tunnel = false;
+ return true;
+ }
+ }
+ return false;
+ }
+public:
+ /** Helper for pathfinders - get min/max speed on the m_old_tile/m_old_td */
+ int GetSpeedLimit(int *pmin_speed = NULL)
+ {
+ int min_speed = 0;
+ int max_speed = INT_MAX; // no limit
+
+ // for now we handle only on-bridge speed limit
+ if (IsBridgeTile(m_old_tile) && !IsWaterTT() && IsDiagonalTrackdir(m_old_td)) {
+ bool is_on_bridge = true;
+ if (IsBridgeMiddle(m_old_tile)) {
+ // get track axis
+ Axis track_axis = DiagDirToAxis(TrackdirToExitdir(m_old_td));
+ // get under-bridge axis
+ Axis bridge_axis = GetBridgeAxis(m_old_tile);
+ if (track_axis != bridge_axis) is_on_bridge = false;
+ }
+ if (is_on_bridge) {
+ int spd = _bridge[GetBridgeType(m_old_tile)].speed;
+ if (IsRoadTT()) spd *= 2;
+ if (max_speed > spd) max_speed = spd;
+ }
+ }
+
+ // if min speed was requested, return it
+ if (pmin_speed) *pmin_speed = min_speed;
+ return max_speed;
+ }
+};
+
+typedef CFollowTrackT<TRANSPORT_WATER, true > CFollowTrackWater;
+typedef CFollowTrackT<TRANSPORT_ROAD , true > CFollowTrackRoad;
+typedef CFollowTrackT<TRANSPORT_RAIL , true > CFollowTrackRail;
+
+typedef CFollowTrackT<TRANSPORT_WATER, false> CFollowTrackWaterNo90;
+typedef CFollowTrackT<TRANSPORT_ROAD , false> CFollowTrackRoadNo90;
+typedef CFollowTrackT<TRANSPORT_RAIL , false> CFollowTrackRailNo90;
+
+#endif /* FOLLOW_TRACK_HPP */
diff --git a/yapf/hashtable.hpp b/yapf/hashtable.hpp
new file mode 100644
index 000000000..bab5bccfc
--- /dev/null
+++ b/yapf/hashtable.hpp
@@ -0,0 +1,234 @@
+/* $Id$ */
+
+#ifndef HASHTABLE_HPP
+#define HASHTABLE_HPP
+
+template <class Titem_>
+struct CHashTableSlotT
+{
+ typedef typename Titem_::Key Key; // make Titem_::Key a property of HashTable
+
+ Titem_* m_pFirst;
+
+ CHashTableSlotT() : m_pFirst(NULL) {}
+
+ /** hash table slot helper - linear search for item with given key through the given blob - const version */
+ FORCEINLINE const Titem_& Find(const Key& key) const
+ {
+ for (const Titem_* pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) {
+ if (pItem->GetKey() == key) {
+ // we have found the item, return it
+ return *pItem;
+ }
+ }
+ return *(Titem_*)NULL;
+ }
+
+ /** hash table slot helper - linear search for item with given key through the given blob - non-const version */
+ FORCEINLINE Titem_& Find(const Key& key)
+ {
+ for (Titem_* pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) {
+ if (pItem->GetKey() == key) {
+ // we have found the item, return it
+ return *pItem;
+ }
+ }
+ return *(Titem_*)NULL;
+ }
+
+ /** hash table slot helper - add new item to the slot */
+ FORCEINLINE void Attach(Titem_& new_item)
+ {
+ assert(new_item.GetHashNext() == NULL);
+ new_item.SetHashNext(m_pFirst);
+ m_pFirst = &new_item;
+ }
+
+ /** hash table slot helper - remove item from a slot */
+ FORCEINLINE bool Detach(Titem_& item_to_remove)
+ {
+ if (m_pFirst == &item_to_remove) {
+ m_pFirst = item_to_remove.GetHashNext();
+ item_to_remove.SetHashNext(NULL);
+ return true;
+ }
+ Titem_* pItem = m_pFirst;
+ while (true) {
+ if (pItem == NULL) {
+ return false;
+ }
+ Titem_* pNextItem = pItem->GetHashNext();
+ if (pNextItem == &item_to_remove) break;
+ pItem = pNextItem;
+ }
+ pItem->SetHashNext(item_to_remove.GetHashNext());
+ item_to_remove.SetHashNext(NULL);
+ return true;
+ }
+
+ /** hash table slot helper - remove and return item from a slot */
+ FORCEINLINE Titem_& Detach(const Key& key)
+ {
+ // do we have any items?
+ if (m_pFirst == NULL) {
+ return *(Titem_*)NULL;
+ }
+ // is it our first item?
+ if (m_pFirst->GetKey() == key) {
+ Titem_& ret_item = *m_pFirst;
+ m_pFirst = m_pFirst->GetHashNext();
+ ret_item.SetHashNext(NULL);
+ return ret_item;
+ }
+ // find it in the following items
+ Titem_* pPrev = m_pFirst;
+ for (Titem_* pItem = m_pFirst->GetHashNext(); pItem != NULL; pPrev = pItem, pItem = pItem->GetHashNext()) {
+ if (pItem->GetKey() == key) {
+ // we have found the item, unlink and return it
+ pPrev->SetHashNext(pItem->GetHashNext());
+ pItem->SetHashNext(NULL);
+ return *pItem;
+ }
+ }
+ return *(Titem_*)NULL;
+ }
+};
+
+/** @class CHashTableT<Titem, Thash_bits> - simple hash table
+ of pointers allocated elsewhere.
+
+ Supports: Add/Find/Remove of Titems.
+
+ Your Titem must meet some extra requirements to be CHashTableT
+ compliant:
+ - its constructor/destructor (if any) must be public
+ - if the copying of item requires an extra resource management,
+ you must define also copy constructor
+ - must support nested type (struct, class or typedef) Titem::Key
+ that defines the type of key class for that item
+ - must support public method:
+ const Key& GetKey() const; // return the item's key object
+
+ In addition, the Titem::Key class must support:
+ - public method that calculates key's hash:
+ int CalcHash() const;
+ - public 'equality' operator to compare the key with another one
+ bool operator == (const Key& other) const;
+*/
+template <class Titem_, int Thash_bits_>
+class CHashTableT {
+public:
+ typedef Titem_ Titem; // make Titem_ visible from outside of class
+ typedef typename Titem_::Key Tkey; // make Titem_::Key a property of HashTable
+ ST_CONST(int, Thash_bits = Thash_bits_); // publish num of hash bits
+ ST_CONST(int, Tcapacity = 1 << Thash_bits); // and num of slots 2^bits
+
+protected:
+ /** each slot contains pointer to the first item in the list,
+ Titem contains pointer to the next item - GetHashNext(), SetHashNext() */
+ typedef CHashTableSlotT<Titem_> Slot;
+
+ Slot* m_slots; // here we store our data (array of blobs)
+ int m_num_items; // item counter
+
+public:
+ // default constructor
+ FORCEINLINE CHashTableT()
+ {
+ // construct all slots
+ m_slots = new Slot[Tcapacity];
+ m_num_items = 0;
+ }
+
+ ~CHashTableT() {delete [] m_slots; m_num_items = 0; m_slots = NULL;}
+
+protected:
+ /** static helper - return hash for the given key modulo number of slots */
+ FORCEINLINE static int CalcHash(const Tkey& key)
+ {
+ int32 hash = key.CalcHash();
+ if ((8 * Thash_bits) < 32) hash ^= hash >> (min(8 * Thash_bits, 31));
+ if ((4 * Thash_bits) < 32) hash ^= hash >> (min(4 * Thash_bits, 31));
+ if ((2 * Thash_bits) < 32) hash ^= hash >> (min(2 * Thash_bits, 31));
+ if ((1 * Thash_bits) < 32) hash ^= hash >> (min(1 * Thash_bits, 31));
+ hash &= (1 << Thash_bits) - 1;
+ return hash;
+ }
+
+ /** static helper - return hash for the given item modulo number of slots */
+ FORCEINLINE static int CalcHash(const Titem_& item) {return CalcHash(item.GetKey());}
+
+public:
+ /** item count */
+ FORCEINLINE int Count() const {return m_num_items;}
+
+ /** const item search */
+ const Titem_& Find(const Tkey& key) const
+ {
+ int hash = CalcHash(key);
+ const Slot& slot = m_slots[hash];
+ const Titem_& item = slot.Find(key);
+ return item;
+ }
+
+ /** non-const item search */
+ Titem_& Find(const Tkey& key)
+ {
+ int hash = CalcHash(key);
+ Slot& slot = m_slots[hash];
+ Titem_& item = slot.Find(key);
+ return item;
+ }
+
+ /** non-const item search & optional removal (if found) */
+ Titem_& TryPop(const Tkey& key)
+ {
+ int hash = CalcHash(key);
+ Slot& slot = m_slots[hash];
+ Titem_& item = slot.Detach(key);
+ if (&item != NULL) {
+ m_num_items--;
+ }
+ return item;
+ }
+
+ /** non-const item search & removal */
+ Titem_& Pop(const Tkey& key)
+ {
+ Titem_& item = TryPop(key);
+ assert(&item != NULL);
+ return item;
+ }
+
+ /** non-const item search & optional removal (if found) */
+ bool TryPop(Titem_& item)
+ {
+ const Tkey& key = item.GetKey();
+ int hash = CalcHash(key);
+ Slot& slot = m_slots[hash];
+ bool ret = slot.Detach(item);
+ if (ret) {
+ m_num_items--;
+ }
+ return ret;
+ }
+
+ /** non-const item search & removal */
+ void Pop(Titem_& item)
+ {
+ bool ret = TryPop(item);
+ assert(ret);
+ }
+
+ /** add one item - copy it from the given item */
+ void Push(Titem_& new_item)
+ {
+ int hash = CalcHash(new_item);
+ Slot& slot = m_slots[hash];
+ assert(&slot.Find(new_item.GetKey()) == NULL);
+ slot.Attach(new_item);
+ m_num_items++;
+ }
+};
+
+#endif /* HASHTABLE_HPP */
diff --git a/yapf/nodelist.hpp b/yapf/nodelist.hpp
new file mode 100644
index 000000000..204282e93
--- /dev/null
+++ b/yapf/nodelist.hpp
@@ -0,0 +1,132 @@
+/* $Id$ */
+
+#ifndef NODELIST_HPP
+#define NODELIST_HPP
+
+#include "array.hpp"
+#include "hashtable.hpp"
+#include "binaryheap.hpp"
+
+/** Hash table based node list multi-container class.
+ Implements open list, closed list and priority queue for A-star
+ path finder. */
+template <class Titem_, int Thash_bits_open_, int Thash_bits_closed_>
+class CNodeList_HashTableT {
+public:
+ /** make Titem_ visible from outside of class */
+ typedef Titem_ Titem;
+ /** make Titem_::Key a property of HashTable */
+ typedef typename Titem_::Key Key;
+ /** type that we will use as item container */
+ typedef CArrayT<Titem_, 65536, 256> CItemArray;
+ /** how pointers to open nodes will be stored */
+ typedef CHashTableT<Titem_, Thash_bits_open_ > COpenList;
+ /** how pointers to closed nodes will be stored */
+ typedef CHashTableT<Titem_, Thash_bits_closed_> CClosedList;
+ /** how the priority queue will be managed */
+ typedef CBinaryHeapT<Titem_> CPriorityQueue;
+
+protected:
+ /** here we store full item data (Titem_) */
+ CItemArray m_arr;
+ /** hash table of pointers to open item data */
+ COpenList m_open;
+ /** hash table of pointers to closed item data */
+ CClosedList m_closed;
+ /** priority queue of pointers to open item data */
+ CPriorityQueue m_open_queue;
+ /** new open node under construction */
+ Titem *m_new_node;
+public:
+ /** default constructor */
+ CNodeList_HashTableT()
+ : m_open_queue(204800)
+ {
+ m_new_node = NULL;
+ }
+ /** destructor */
+ ~CNodeList_HashTableT()
+ {
+ }
+ /** return number of open nodes */
+ FORCEINLINE int OpenCount() {return m_open.Count();}
+ /** return number of closed nodes */
+ FORCEINLINE int ClosedCount() {return m_closed.Count();}
+ /** allocate new data item from m_arr */
+ FORCEINLINE Titem_* CreateNewNode()
+ {
+ if (m_new_node == NULL) m_new_node = &m_arr.Add();
+ return m_new_node;
+ }
+ /** notify the nodelist, that we don't want to discard the given node */
+ FORCEINLINE void FoundBestNode(Titem_& item)
+ {
+ // for now it is enough to invalidate m_new_node if it is our given node
+ if (&item == m_new_node)
+ m_new_node = NULL;
+ // TODO: do we need to store best nodes found in some extra list/array? Probably not now.
+ }
+ /** insert given item as open node (into m_open and m_open_queue) */
+ FORCEINLINE void InsertOpenNode(Titem_& item)
+ {
+ assert(&m_closed.Find(item.GetKey()) == NULL);
+ m_open.Push(item);
+ // TODO: check if m_open_queue is not full
+ assert(!m_open_queue.IsFull());
+ m_open_queue.Push(item);
+ if (&item == m_new_node)
+ m_new_node = NULL;
+ }
+ /** return the best open node */
+ FORCEINLINE Titem_& GetBestOpenNode()
+ {
+ if (!m_open_queue.IsEmpty()) {
+ Titem_& item = m_open_queue.GetHead();
+ return item;
+ }
+ return *(Titem_*)NULL;
+ }
+ /** remove and return the best open node */
+ FORCEINLINE Titem_& PopBestOpenNode()
+ {
+ if (!m_open_queue.IsEmpty()) {
+ Titem_& item = m_open_queue.PopHead();
+ m_open.Pop(item);
+ return item;
+ }
+ return *(Titem_*)NULL;
+ }
+ /** return the open node specified by a key or NULL if not found */
+ FORCEINLINE Titem_& FindOpenNode(const Key& key)
+ {
+ Titem_& item = m_open.Find(key);
+ return item;
+ }
+ /** remove and return the open node specified by a key */
+ FORCEINLINE Titem_& PopOpenNode(const Key& key)
+ {
+ Titem_& item = m_open.Pop(key);
+ if (&item != NULL) {
+ int idxPop = m_open_queue.FindLinear(item);
+ m_open_queue.RemoveByIdx(idxPop);
+ }
+ return item;
+ }
+ /** close node */
+ FORCEINLINE void InsertClosedNode(Titem_& item)
+ {
+ assert(&m_open.Find(item.GetKey()) == NULL);
+ m_closed.Push(item);
+ }
+ /** return the closed node specified by a key or NULL if not found */
+ FORCEINLINE Titem_& FindClosedNode(const Key& key)
+ {
+ Titem_& item = m_closed.Find(key);
+ return item;
+ }
+
+ FORCEINLINE int TotalCount() {return m_arr.Size();}
+ FORCEINLINE Titem_& ItemAt(int idx) {return m_arr[idx];}
+};
+
+#endif /* NODELIST_HPP */
diff --git a/yapf/track_dir.hpp b/yapf/track_dir.hpp
new file mode 100644
index 000000000..e21dd1b2b
--- /dev/null
+++ b/yapf/track_dir.hpp
@@ -0,0 +1,35 @@
+/* $Id$ */
+
+#ifndef TRACK_DIR_HPP
+#define TRACK_DIR_HPP
+
+EXTERN_C_BEGIN
+#include "../tile.h"
+#include "../openttd.h"
+#include "../map.h"
+#include "../rail.h"
+EXTERN_C_END
+
+/** Helpers to allow to work with enum as with type safe bit set in C++ */
+#define DECLARE_ENUM_AS_BIT_MASK(mask_t) \
+ FORCEINLINE mask_t operator | (mask_t m1, mask_t m2) {return (mask_t)((int)m1 | m2);} \
+ FORCEINLINE mask_t operator & (mask_t m1, mask_t m2) {return (mask_t)((int)m1 & m2);} \
+ FORCEINLINE mask_t operator ^ (mask_t m1, mask_t m2) {return (mask_t)((int)m1 ^ m2);} \
+ FORCEINLINE mask_t& operator |= (mask_t& m1, mask_t m2) {m1 = m1 | m2; return m1;} \
+ FORCEINLINE mask_t& operator &= (mask_t& m1, mask_t m2) {m1 = m1 & m2; return m1;} \
+ FORCEINLINE mask_t& operator ^= (mask_t& m1, mask_t m2) {m1 = m1 ^ m2; return m1;} \
+ FORCEINLINE mask_t operator ~(mask_t m) {return (mask_t)(~(int)m);}
+
+/** probably redundant enum combining operators (as we have conversion functions) */
+#define DECLARE_ENUM_AS_BIT_INDEX(idx_t, mask_t) \
+ FORCEINLINE mask_t operator << (int m, idx_t i) {return (mask_t)(m << (int)i);} \
+ FORCEINLINE mask_t operator << (mask_t m, int i) {return (mask_t)(((int)m) << i);} \
+ FORCEINLINE mask_t operator >> (mask_t m, int i) {return (mask_t)(((int)m) >> i);}
+
+DECLARE_ENUM_AS_BIT_MASK(TrackBits);
+DECLARE_ENUM_AS_BIT_INDEX(Track, TrackBits);
+
+DECLARE_ENUM_AS_BIT_MASK(TrackdirBits);
+DECLARE_ENUM_AS_BIT_INDEX(Trackdir, TrackdirBits);
+
+#endif /* TRACK_DIR_HPP */
diff --git a/yapf/unittest/test_autocopyptr.h b/yapf/unittest/test_autocopyptr.h
new file mode 100644
index 000000000..a08d84a59
--- /dev/null
+++ b/yapf/unittest/test_autocopyptr.h
@@ -0,0 +1,43 @@
+/* $Id$ */
+
+struct CData
+{
+ int val;
+
+ FORCEINLINE CData() : val(0) {NumInstances()++; /*DBG("DCata::ctor()\n");*/}
+ FORCEINLINE CData(const CData& src) : val(src.val) {NumInstances()++; /*DBG("DCata::ctor(%d)\n", val);*/}
+ FORCEINLINE ~CData() {NumInstances()--; /*DBG("DCata::dtor(%d)\n", val);*/}
+
+ FORCEINLINE bool operator < (const CData& other) const {return (val < other.val);}
+
+ FORCEINLINE static int& NumInstances() { static int num_instances = 0; return num_instances; };
+
+};
+
+typedef CAutoCopyPtrT<CData> PData;
+
+static int TestAutoCopyPtr(bool silent)
+{
+ int res = 0;
+ {
+ PData p1, p3;
+ p1->val = 4;
+ PData p2; p2 = p1;
+ p2->val = 6;
+ DBG("\n%d, %d", p1->val, p2->val);
+ CHECK_INT(0, p1->val, 4);
+ CHECK_INT(1, p2->val, 6);
+
+ p2 = p1;
+ p3 = p1;
+ p2->val = 7;
+ DBG("\n%d, %d", p1->val, p2->val);
+ CHECK_INT(2, p3->val, 4);
+ CHECK_INT(3, p2->val, 7);
+
+ CHECK_INT(4, CData::NumInstances(), 3);
+ }
+ CHECK_INT(5, CData::NumInstances(), 0);
+ return res;
+}
+
diff --git a/yapf/unittest/test_binaryheap.h b/yapf/unittest/test_binaryheap.h
new file mode 100644
index 000000000..f0ba44749
--- /dev/null
+++ b/yapf/unittest/test_binaryheap.h
@@ -0,0 +1,103 @@
+/* $Id$ */
+
+// this test uses CData structure defined in test_autocopyptr.h
+
+static int TestBinaryHeap1(bool silent)
+{
+ CData::NumInstances() = 0;
+ int res = 0;
+ {
+ const int max_items = 10000;
+ const int total_adds = 1000000;
+ CBinaryHeapT<CData> bh(max_items);
+ CFixedSizeArrayT<CData, max_items> data;
+
+
+ DBG("\nFilling BinaryHeap with %d items...", max_items);
+ CHECK_INT(0, bh.Size(), 0);
+ CHECK_INT(1, CData::NumInstances(), 0);
+ int i = 0;
+ for (; i < max_items; i++) {
+ CData& d = data.Add();
+ d.val = rand() & 0xFFFF;
+ bh.Push(d);
+ }
+ CHECK_INT(2, bh.Size(), max_items);
+ CHECK_INT(3, CData::NumInstances(), max_items);
+
+
+ DBG("\nShaking items %d times...", total_adds);
+ int num_last = bh.GetHead().val;
+ for (i = 0; i < total_adds; i++) {
+ CData& d = bh.PopHead();
+ //printf("\nd->val = %d, num_last = %d", d->val, num_last);
+ CHECK_INT(4, d.val < num_last, 0);
+ if(d.val < num_last) {
+ printf("Sort error @ item %d", i);
+ }
+ num_last = d.val;
+ d.val += rand() & 0xFFFF;
+ bh.Push(d);
+ }
+
+
+ DBG("\nDone!");
+ CHECK_INT(5, bh.Size(), max_items);
+ CHECK_INT(6, CData::NumInstances(), max_items);
+ }
+ CHECK_INT(7, CData::NumInstances(), 0);
+ return res;
+}
+
+
+
+// this test uses CData and PData structures defined in test_autocopyptr.h
+
+static int TestBinaryHeap2(bool silent)
+{
+ CData::NumInstances() = 0;
+ int res = 0;
+ {
+ const int max_items = 10000;
+ const int total_adds = 1000000;
+ CBinaryHeapT<CData> bh(max_items);
+ CFixedSizeArrayT<CData, max_items> data;
+
+
+ DBG("\nFilling BinaryHeap with %d items...", max_items);
+ CHECK_INT(0, bh.Size(), 0);
+ CHECK_INT(1, CData::NumInstances(), 0);
+ int i = 0;
+ for (; i < max_items; i++) {
+ CData& d = data.Add();
+ d.val = rand() & 0xFFFF;
+ bh.Push(d);
+ }
+ CHECK_INT(2, bh.Size(), max_items);
+ CHECK_INT(3, CData::NumInstances(), max_items);
+
+
+ DBG("\nShaking items %d times...", total_adds);
+ int num_last = bh.GetHead().val;
+ for (i = 0; i < total_adds; i++) {
+ CData& d = bh.GetHead();
+ bh.RemoveHead();
+ //printf("\nd->val = %d, num_last = %d", d->val, num_last);
+ CHECK_INT(4, d.val < num_last, 0);
+ if(d.val < num_last) {
+ printf("Sort error @ item %d", i);
+ }
+ num_last = d.val;
+ d.val += rand() & 0xFFFF;
+ bh.Push(d);
+ }
+
+
+ DBG("\nDone!");
+ CHECK_INT(5, bh.Size(), max_items);
+ CHECK_INT(6, CData::NumInstances(), max_items);
+ }
+ CHECK_INT(7, CData::NumInstances(), 0);
+ return res;
+}
+
diff --git a/yapf/unittest/test_blob.h b/yapf/unittest/test_blob.h
new file mode 100644
index 000000000..5f266b0f7
--- /dev/null
+++ b/yapf/unittest/test_blob.h
@@ -0,0 +1,61 @@
+/* $Id$ */
+
+static int TestBlob1(bool silent)
+{
+ typedef CBlobT<int64> Blob;
+ int res = 0;
+ {
+ Blob a;
+ Blob b;
+ CHECK_INT(0, a.IsEmpty(), true);
+ CHECK_INT(1, a.Size(), 0);
+
+ const int nItems = 10;
+
+ {
+ for (int i = 1; i <= nItems; i++) {
+ a.Append(i);
+ CHECK_INT(2, a.IsEmpty(), false);
+ CHECK_INT(3, a.Size(), i);
+ }
+ }
+
+ {
+ for (int i = 1; i <= nItems; i++) {
+ CHECK_INT(4, *a.Data(i - 1), i);
+ }
+ }
+ }
+ return res;
+}
+
+static int TestBlob2(bool silent)
+{
+ typedef CBlobT<CFsaItem> Blob;
+ int res = 0;
+ {
+ Blob a;
+ Blob b;
+ CHECK_INT(0, a.IsEmpty(), true);
+ CHECK_INT(1, a.Size(), 0);
+
+ const int nItems = 10;
+
+ {
+ for (int i = 1; i <= nItems; i++) {
+ a.Append(CFsaItem(i));
+ CHECK_INT(2, a.IsEmpty(), false);
+ CHECK_INT(3, a.Size(), i);
+ }
+ }
+ {
+ for (int i = 1; i <= nItems; i++) {
+ CHECK_INT(4, a.Data(i - 1)->i, i);
+ }
+ }
+ CHECK_INT(15, CFsaItem::NumInstances(), nItems);
+ }
+ CHECK_INT(16, CFsaItem::NumInstances(), 0);
+
+ return res;
+}
diff --git a/yapf/unittest/test_fixedsizearray.h b/yapf/unittest/test_fixedsizearray.h
new file mode 100644
index 000000000..0065a821e
--- /dev/null
+++ b/yapf/unittest/test_fixedsizearray.h
@@ -0,0 +1,114 @@
+/* $Id$ */
+
+struct CFsaItem
+{
+ int i;
+
+ FORCEINLINE static int& NumInstances() { static int num_instances = 0; return num_instances; };
+
+ FORCEINLINE CFsaItem(int i = 0)
+ {
+ this->i = i;
+ NumInstances()++;
+ DBG("(*)");
+ }
+
+ FORCEINLINE CFsaItem(const CFsaItem& src)
+ {
+ this->i = src.i;
+ NumInstances()++;
+ DBG("(c)");
+ }
+
+ FORCEINLINE ~CFsaItem()
+ {
+ NumInstances()--;
+ DBG("(-)");
+ }
+};
+
+typedef CFixedSizeArrayT<CFsaItem, 4> CSubArray;
+typedef CFixedSizeArrayT<CSubArray, 4> CSuperArray;
+
+static int TestFixedSizeArray(bool silent)
+{
+ int res = 0;
+ {
+ CSuperArray a;
+
+ CHECK_INT(0, a.IsFull(), false);
+ CHECK_INT(1, a.IsEmpty(), true);
+
+ CSubArray& b1 = a.Add();
+ b1.Add().i = 1;
+ new(&b1.AddNC())CFsaItem(2);
+
+ CSubArray& b2 = a.Add();
+ new(&b2.AddNC())CFsaItem(3);
+ b2.Add().i = 4;
+
+ CSubArray& b3 = a.AddNC();
+ new(&b3)CSubArray(b1);
+
+ CSubArray& b4 = a.AddNC();
+ new(&b4)CSubArray(b2);
+
+ CHECK_INT(2, a[0][0].i, 1);
+ CHECK_INT(3, b1[1].i, 2);
+ CHECK_INT(4, b1.Size(), 2);
+ CHECK_INT(5, a[3][0].i, 3);
+ CHECK_INT(6, a[3][1].i, 4);
+ CHECK_INT(7, CFsaItem::NumInstances(), 4);
+ CHECK_INT(8, a.IsFull(), true);
+ CHECK_INT(9, a.IsEmpty(), false);
+ CHECK_INT(10, a[3].IsFull(), false);
+ CHECK_INT(11, a[3].IsEmpty(), false);
+ }
+ CHECK_INT(12, CFsaItem::NumInstances(), 0);
+
+ return res;
+}
+
+typedef CArrayT<CFsaItem, 2> CArray;
+
+static int TestArray(bool silent)
+{
+ int res = 0;
+ {
+ CArray a;
+
+ CHECK_INT(0, a.IsFull(), false);
+ CHECK_INT(1, a.IsEmpty(), true);
+
+ CHECK_INT(2, a.Size(), 0);
+
+ a.Add().i = 1;
+ CHECK_INT(3, a.Size(), 1);
+
+ new(&a.AddNC())CFsaItem(2);
+ CHECK_INT(4, a.Size(), 2);
+
+ CHECK_INT(5, a.IsFull(), false);
+ CHECK_INT(6, a.IsEmpty(), false);
+
+ a.Add().i = 3;
+ CHECK_INT(7, a.Size(), 3);
+
+ new(&a.AddNC())CFsaItem(4);
+ CHECK_INT(8, a.Size(), 4);
+
+ CHECK_INT(9, a[0].i, 1);
+ CHECK_INT(10, a[1].i, 2);
+ CHECK_INT(11, a[2].i, 3);
+ CHECK_INT(12, a[3].i, 4);
+
+ CHECK_INT(13, a.IsFull(), true);
+ CHECK_INT(14, a.IsEmpty(), false);
+
+ CHECK_INT(15, CFsaItem::NumInstances(), 4);
+ }
+ CHECK_INT(16, CFsaItem::NumInstances(), 0);
+
+ return res;
+}
+
diff --git a/yapf/unittest/test_hashtable.h b/yapf/unittest/test_hashtable.h
new file mode 100644
index 000000000..230550f2b
--- /dev/null
+++ b/yapf/unittest/test_hashtable.h
@@ -0,0 +1,74 @@
+/* $Id$ */
+
+struct CHashItem1 {
+ struct CKey {
+ int k;
+ FORCEINLINE int CalcHash() const {return k;};
+ FORCEINLINE bool operator == (const CKey& other) const {return (k == other.k);}
+ };
+ typedef CKey Key;
+ CKey key;
+ int val;
+ CHashItem1* m_next;
+
+ CHashItem1() : m_next(NULL) {}
+ FORCEINLINE const Key& GetKey() const {return key;}
+ CHashItem1* GetHashNext() {return m_next;}
+ void SetHashNext(CHashItem1* next) {m_next = next;}
+};
+
+static int TestHashTable1(bool silent)
+{
+ typedef CHashItem1 Item;
+ typedef CHashTableT<Item, 12> HashTable1_t;
+ typedef CArrayT<Item, 1024, 16384> Array_t;
+ typedef CHashTableT<Item, 16> HashTable2_t;
+
+ int res = 0;
+ {
+ HashTable1_t ht1;
+ HashTable2_t ht2;
+ Array_t ar1;
+ Array_t ar2;
+
+#ifdef _DEBUG
+ static const int nItems = 10000;
+#else
+ static const int nItems = 1000000;
+#endif
+ {
+ srand(0);
+ for (int i = 0; i < nItems; i++) {
+ int r1 = i;
+ int r2 = rand() & 0x0000FFFF | (rand() << 16);
+ Item& I1 = ar1.Add();
+ Item& I2 = ar2.Add();
+ I1.key.k = r1;
+ I2.key.k = r1;
+ I1.val = r2;
+ I2.val = r2;
+ ht1.Push(I1);
+ ht2.Push(I2);
+ }
+ }
+ {
+ srand(0);
+ for (int i = 0; i < nItems; i++) {
+ int r1 = i;
+ int r2 = rand() & 0x0000FFFF | (rand() << 16);
+ HashTable1_t::Tkey k; k.k = r1;
+ Item& i1 = ht1.Find(k);
+ Item& i2 = ht2.Find(k);
+
+ CHECK_INT(0, &i1 != NULL, 1);
+ CHECK_INT(1, &i2 != NULL, 1);
+
+ if (&i1 != NULL) CHECK_INT(2, i1.val, r2);
+ if (&i2 != NULL) CHECK_INT(3, i2.val, r2);
+ }
+ }
+ }
+ return res;
+}
+
+
diff --git a/yapf/unittest/test_yapf.h b/yapf/unittest/test_yapf.h
new file mode 100644
index 000000000..ca4b21de0
--- /dev/null
+++ b/yapf/unittest/test_yapf.h
@@ -0,0 +1,350 @@
+/* $Id$ */
+
+#include "../yapf_base.hpp"
+
+struct CYapfMap1
+{
+ enum {xMax = 32, yMax = 68};
+ static int MapZ(int x, int y)
+ {
+ static const char *z1[yMax] = {
+ "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
+ "A000000000000000000000000000000000000000000000000000000000000000000A",
+ "A000000000000000000000000000000000000000000000000000000000000000000A",
+ "A000000000001000000000000000000000000000000000000000000000000000000A",
+ "A000000000001000000000000000000000000000000000000000000000000000000A",
+ "A000033333333333000000000000000000000000000000000000000000000000000A",
+ "A000030000000000000000000000000000000000000000000000000000000000000A",
+ "A000030000000000000000000000000000000000000000000000000000000000000A",
+ "A000030000000000000000000000000000000000000000000000000000000000000A",
+ "A000030000000000000000000000000000000000000000000000000000000000000A",
+ "A000030000000000000000000000000000000000000000000000000000000000000A",
+ "A210030000000000000000000000000000000000000000000000000000000000000A",
+ "A000000000000000000000000000000000000000000000000000000000000000000A",
+ "A000000000000000000000000000000000000000000000000000000000000000000A",
+ "A000000000000000000000000000000000000000000000000000000000000000000A",
+ "A000000000000000000000000000000000000000000000000000000000000000000A",
+ "A011333323333333233333333333333333333333333333333333333333333000000A",
+ "A000030000000000000000000000000000000000000000000000000000003000000A",
+ "A000030000000000000000000000000000000000000000000000000000003000000A",
+ "A000030000000000000000000000000000000000000000000000000000003000000A",
+ "A210030000000000000000000000000000000000000000000000000000003000000A",
+ "A000030000000000000000000000000000000000000000000000000000003000000A",
+ "A000030000000000000000000000000000000000000000000000000000003000000A",
+ "A000230000000000000000000000000000000000000000000000000000003000000A",
+ "A000030000000000000000000000000000000000000000000000000000003000000A",
+ "A000030000000000000000000000000000000000000000000000000000003000000A",
+ "A000030000000000000000000000000000000000000000000000000000003000000A",
+ "A000000000000000000000000000003333333333333333333333333333333000000A",
+ "A000000000000000000000000000000000000000000000000000000000000000000A",
+ "A000000000000000000000000000000000000000000000000000000000000000000A",
+ "A000000000000000000000000000000000000000000000000000000000000000000A",
+ "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
+ };
+
+ static const char *z2[yMax] = {
+ "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
+ "A000000000000000000000000000000000000000000000000000000000000000000A",
+ "A003333333333333333333333333333333333333333333333333300000000000000A",
+ "A003000000001000000000000000000000000000000000000000300000000000000A",
+ "A003000000001000000000000000000000000000000000000000300000000000000A",
+ "A003333333333333333333333333333333333333300000000000300000000000000A",
+ "A000030000000000000000000000000000000000300000000000300000000000000A",
+ "A000030000000000000000000000000000000000333333333333300000000000000A",
+ "A000030000000000000000000000000000000000300000000000000000000000000A",
+ "A000030000000000000000000000000000000000300000000000000000000000000A",
+ "A000030000000000000000000000000000000000300000000000000000000000000A",
+ "A210030000000000000000000000000000000000300000000000000000000000000A",
+ "A000000000000000000000000000000000000000333300000000000000000000000A",
+ "A000000000000000000000000000000000000000000300000000000000000000000A",
+ "A000000000000000000000000000000000000000000300000000000000000000000A",
+ "A000000000000000000000000000000000000000000300000000000000000000000A",
+ "A012333323333333233333333333333333333333333333333333333333333000000A",
+ "A000030000000000000000000000000000000000000000000000000000003000000A",
+ "A000030000000000000000000000000000000000000000000000000300003000000A",
+ "A000030000000000000000000000000000000000000000000000000300003000000A",
+ "A210030000000000000000000000000000000000000000000000000330003000000A",
+ "A000030000000000000000000000000000000000000000000000000300003000000A",
+ "A000030000000000000000000000000000000000000000000000000300003000000A",
+ "A000230000000000000000000000000000000000000000000000000300003000000A",
+ "A000030000000000000000000000000000000000000000000000000300003000000A",
+ "A000030000000000000000000000000000000000000000000000000300003000000A",
+ "A000030000000000000000000000000000000000000000000000000300003000000A",
+ "A000000000000000000000000000003333333333333333333333333333333000000A",
+ "A000000000000000000000000000000000000000000000000000000000000000000A",
+ "A000000000000000000000000000000000000000000000000000000000000000000A",
+ "A000000000000000000000000000000000000000000000000000000000000000000A",
+ "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
+ };
+
+ static const char **z = z1;
+
+ if (x >= 0 && x < xMax && y >= 0 && y < yMax) {
+ int ret = z[x][y];
+ return ret;
+ }
+ return z[0][0];
+ }
+};
+
+struct CNodeKey1 {
+ int m_x;
+ int m_y;
+ Trackdir m_td;
+ DiagDirection m_exitdir;
+
+ CNodeKey1() : m_x(0), m_y(0), m_td(INVALID_TRACKDIR) {}
+
+ int CalcHash() const {return m_x | (m_y << 5) | (m_td << 10);}
+ bool operator == (const CNodeKey1& other) const {return (m_x == other.m_x) && (m_y == other.m_y) && (m_td == other.m_td);}
+};
+
+struct CNodeKey2 : public CNodeKey1
+{
+ int CalcHash() const {return m_x | (m_y << 5) | (m_exitdir << 10);}
+ bool operator == (const CNodeKey1& other) const {return (m_x == other.m_x) && (m_y == other.m_y) && (m_exitdir == other.m_exitdir);}
+};
+
+template <class Tkey_>
+struct CTestYapfNodeT {
+ typedef Tkey_ Key;
+ typedef CTestYapfNodeT<Tkey_> Node;
+
+ Tkey_ m_key;
+ CTestYapfNodeT *m_parent;
+ int m_cost;
+ int m_estimate;
+ CTestYapfNodeT *m_next;
+
+ CTestYapfNodeT(CTestYapfNodeT* parent = NULL) : m_parent(parent), m_cost(0), m_estimate(0), m_next(NULL) {}
+
+ const Tkey_& GetKey() const {return m_key;}
+ int GetCost() {return m_cost;}
+ int GetCostEstimate() {return m_estimate;}
+ bool operator < (const CTestYapfNodeT& other) const {return m_estimate < other.m_estimate;}
+ CTestYapfNodeT* GetHashNext() {return m_next;}
+ void SetHashNext(CTestYapfNodeT* next) {m_next = next;}
+};
+
+typedef CTestYapfNodeT<CNodeKey1> CYapfNode1;
+typedef CTestYapfNodeT<CNodeKey2> CYapfNode2;
+
+template <class Types>
+struct CYapfTestBaseT
+{
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+ typedef typename Types::Map Map;
+
+ int m_x1, m_y1;
+ int m_x2, m_y2;
+ Trackdir m_td1;
+
+ CYapfTestBaseT()
+ : m_x1(0), m_y1(0), m_x2(0), m_y2(0), m_td1(INVALID_TRACKDIR)
+ {
+ }
+
+ void Set(int x1, int y1, int x2, int y2, Trackdir td1)
+ {
+ m_x1 = x1;
+ m_y1 = y1;
+ m_x2 = x2;
+ m_y2 = y2;
+ m_td1 = td1;
+ }
+
+ Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+ FORCEINLINE char TransportTypeChar() const {return 'T';}
+
+ FORCEINLINE void PfFollowNode(Node& org)
+ {
+ int x_org = org.m_key.m_x;
+ int y_org = org.m_key.m_y;
+ int z_org = Map::MapZ(x_org, y_org);
+ DiagDirection exitdir = TrackdirToExitdir(org.m_key.m_td);
+
+ TileIndexDiffC diff = TileIndexDiffCByDir(exitdir);
+ int x_new = x_org + diff.x;
+ int y_new = y_org + diff.y;
+ int z_new = Map::MapZ(x_new, y_new);
+
+ int z_diff = z_new - z_org;
+ if (abs(z_diff) > 1) return;
+
+ TrackdirBits trackdirs = DiagdirReachesTrackdirs(exitdir);
+ TrackdirBits trackdirs90 = TrackdirCrossesTrackdirs(org.m_key.m_td);
+ trackdirs &= (TrackdirBits)~(int)trackdirs90;
+
+ while (trackdirs != TRACKDIR_BIT_NONE) {
+ Trackdir td_new = (Trackdir)FindFirstBit2x64(trackdirs);
+ trackdirs = (TrackdirBits)KillFirstBit2x64(trackdirs);
+
+ Node& n = Yapf().CreateNewNode();
+ n.m_key.m_x = x_new;
+ n.m_key.m_y = y_new;
+ n.m_key.m_td = td_new;
+ n.m_key.m_exitdir = TrackdirToExitdir(n.m_key.m_td);
+ n.m_parent = &org;
+ Yapf().AddNewNode(n);
+ }
+ }
+
+ FORCEINLINE void PfSetStartupNodes()
+ {
+ Node& n1 = Yapf().CreateNewNode();
+ n1.m_key.m_x = m_x1;
+ n1.m_key.m_y = m_y1;
+ n1.m_key.m_td = m_td1;
+ n1.m_key.m_exitdir = TrackdirToExitdir(n1.m_key.m_td);
+ Yapf().AddStartupNode(n1);
+ }
+
+ FORCEINLINE bool PfCalcCost(Node& n)
+ {
+ // base tile cost depending on distance
+ int c = IsDiagonalTrackdir(n.m_key.m_td) ? 10 : 7;
+ // additional penalty for curve
+ if (n.m_parent != NULL && n.m_key.m_td != n.m_parent->m_key.m_td) c += 3;
+ // z-difference cost
+ int z_new = Map::MapZ(n.m_key.m_x, n.m_key.m_y);
+ int z_old = Map::MapZ(n.m_parent->m_key.m_x, n.m_parent->m_key.m_y);
+ if (z_new > z_old) n.m_cost += (z_new - z_old) * 10;
+ // apply it
+ n.m_cost = n.m_parent->m_cost + c;
+ return true;
+ }
+
+ FORCEINLINE bool PfCalcEstimate(Node& n)
+ {
+ int dx = abs(n.m_key.m_x - m_x2);
+ int dy = abs(n.m_key.m_y - m_y2);
+ int dd = min(dx, dy);
+ int dxy = abs(dx - dy);
+ int d = 14 * dd + 10 * dxy;
+ n.m_estimate = n.m_cost + d /*+ d / 4*/;
+ return true;
+ }
+
+ FORCEINLINE bool PfDetectDestination(Node& n)
+ {
+ bool bDest = (n.m_key.m_x == m_x2) && (n.m_key.m_y == m_y2);
+ return bDest;
+ }
+
+ static int stTestAstar(bool silent)
+ {
+ Tpf pf;
+ pf.Set(3, 3, 20, 56, TRACKDIR_X_NE);
+ int ret = pf.TestAstar(silent);
+ return ret;
+ }
+
+ int TestAstar(bool silent)
+ {
+ CPerformanceTimer pc;
+
+ pc.Start();
+ bool bRet = Yapf().FindPath(NULL);
+ pc.Stop();
+
+ if (!bRet) return 1;
+
+ typedef CFixedSizeArrayT<int, 1024> Row;
+ typedef CFixedSizeArrayT<Row, 1024> Box;
+
+ Box box;
+ {
+ for (int x = 0; x < Map::xMax; x++) {
+ Row& row = box.Add();
+ for (int y = 0; y < Map::yMax; y++) {
+ row.Add() = Map::MapZ(x, y);
+ }
+ }
+ }
+ int nPathTiles = 0;
+ {
+ for (Node* pNode = &Yapf().GetBestNode(); pNode != NULL; pNode = pNode->m_parent) {
+ box[pNode->m_key.m_x][pNode->m_key.m_y] = '.';
+ nPathTiles++;
+ }
+ }
+ {
+ printf("\n\n");
+ for (int x = 0; x < Map::xMax; x++) {
+ for (int y = 0; y < Map::yMax; y++) {
+ printf("%c", box[x][y]);
+ }
+ printf("\n");
+ }
+ }
+
+ {
+ printf("\n");
+ printf("Path Tiles: %6d\n", nPathTiles);
+// printf("Closed nodes: %6d\n", pf.m_nodes.ClosedCount());
+// printf("Open nodes: %6d\n", pf.m_nodes.OpenCount());
+// printf("A-star rounds: %6d\n", pf.m_num_steps);
+ }
+ int total_time = pc.Get(1000000);
+ if (total_time != 0)
+ printf("Total time: %6d us\n", pc.Get(1000000));
+
+ printf("\n");
+
+ {
+ int nCnt = Yapf().m_nodes.TotalCount();
+ for (int i = 0; i < nCnt; i++) {
+ Node& n = Yapf().m_nodes.ItemAt(i);
+ int& z = box[n.m_key.m_x][n.m_key.m_y];
+ z = (z < 'a') ? 'a' : (z + 1);
+ }
+ }
+ {
+ for (int x = 0; x < Map::xMax; x++) {
+ for (int y = 0; y < Map::yMax; y++) {
+ printf("%c", box[x][y]);
+ }
+ printf("\n");
+ }
+ }
+
+ return 0;
+ }
+};
+
+struct CDummy1 {};
+struct CDummy2 {};
+struct CDummy3 {};
+
+template <class Tpf_, class Tnode_list, class Tmap>
+struct CYapf_TypesT
+{
+ typedef CYapf_TypesT<Tpf_, Tnode_list, Tmap> Types;
+
+ typedef Tpf_ Tpf;
+ typedef Tnode_list NodeList;
+ typedef Tmap Map;
+ typedef CYapfBaseT<Types> PfBase;
+ typedef CYapfTestBaseT<Types> PfFollow;
+ typedef CDummy1 PfOrigin;
+ typedef CDummy2 PfDestination;
+ typedef CYapfSegmentCostCacheNoneT<Types> PfCache;
+ typedef CDummy3 PfCost;
+};
+
+typedef CNodeList_HashTableT<CYapfNode1, 12, 16> CNodeList1;
+typedef CNodeList_HashTableT<CYapfNode2, 12, 16> CNodeList2;
+
+struct CTestYapf1
+ : public CYapfT<CYapf_TypesT<CTestYapf1, CNodeList1, CYapfMap1> >
+{
+};
+
+struct CTestYapf2
+ : public CYapfT<CYapf_TypesT<CTestYapf2, CNodeList2, CYapfMap1> >
+{
+};
+
+
diff --git a/yapf/unittest/unittest.cpp b/yapf/unittest/unittest.cpp
new file mode 100644
index 000000000..acd8d0820
--- /dev/null
+++ b/yapf/unittest/unittest.cpp
@@ -0,0 +1,166 @@
+/* $Id$ */
+
+#define UNITTEST
+
+#include "../../stdafx.h"
+
+EXTERN_C_BEGIN
+#include "../../macros.h"
+#include "../../tile.h"
+#include "../../openttd.h"
+#include "../../map.h"
+#include "../../rail.h"
+EXTERN_C_END
+
+//#include "../track_dir.hpp"
+
+#include "../yapf.hpp"
+
+#include "../autocopyptr.hpp"
+
+#include "unittest.h"
+
+#include "test_autocopyptr.h"
+#include "test_binaryheap.h"
+#include "test_fixedsizearray.h"
+#include "test_blob.h"
+#include "test_hashtable.h"
+#include "test_yapf.h"
+
+int _total_pf_time_us = 0;
+
+int num_tests_failed = 0;
+int num_tests_total = 0;
+bool _dbg = false;
+
+int do_test(const char* name, TESTPROC test_proc, bool silent)
+{
+ printf("%s ", name);
+ if (!silent) {printf("[enter]:"); getc(stdin);}
+ _dbg = !silent;
+ fflush(stdout);
+ int res = test_proc(silent);
+ if (res == 0)
+ {
+ printf("%s OK\n", silent ? "..." : "\n");
+ }
+ else {
+ printf("\n ERROR! (0x%X)\n", res);
+ printf("\nFailed cases:");
+ int num_failed = 0;
+ for(int i = 0; i < 32; i++) {
+ if (((1 << i) & res) != 0) {
+ printf(" %d", i);
+ num_failed++;
+ }
+ }
+ printf("\n\nTotal: %d cases failed\n\n", num_failed);
+ }
+
+ num_tests_total++;
+ if (res != 0) num_tests_failed++;
+
+ return (res == 0) ? 0 : 1;
+}
+
+struct TEST_RECORD {
+ const char* name;
+ TESTPROC testproc;
+};
+
+TEST_RECORD tests[] = {
+ {"AutoCopyPtr test" , &TestAutoCopyPtr },
+ {"BinaryHeap test 1" , &TestBinaryHeap1 },
+ {"BinaryHeap test 2" , &TestBinaryHeap2 },
+ {"FixedSizeArray test", &TestFixedSizeArray },
+ {"Array test" , &TestArray },
+ {"Blob test 1" , &TestBlob1 },
+ {"Blob test 2" , &TestBlob2 },
+ {"HashTable test 1" , &TestHashTable1 },
+ {"Yapf test 1" , &CTestYapf1::stTestAstar },
+ {"Yapf test 2" , &CTestYapf2::stTestAstar },
+
+ {NULL , NULL },
+};
+
+int main(int argc, char** argv)
+{
+ bool silent = (argc == 1);
+
+ for (TEST_RECORD* tr = tests; tr->name != NULL; tr++)
+ do_test(tr->name, tr->testproc, silent);
+
+ if (num_tests_failed == 0)
+ printf("\nALL %d TESTS PASSED OK!\n\n", num_tests_total);
+ else
+ printf("\n****** %d (from %d of total) TEST(S) FAILED! ******\n", num_tests_failed, num_tests_total);
+ return 0;
+}
+
+
+
+extern "C"
+const TileIndexDiffC _tileoffs_by_dir[] = {
+ {-1, 0},
+ { 0, 1},
+ { 1, 0},
+ { 0, -1}
+};
+
+extern "C"
+const byte _ffb_64[128] = {
+ 0,0,1,0,2,0,1,0,
+ 3,0,1,0,2,0,1,0,
+ 4,0,1,0,2,0,1,0,
+ 3,0,1,0,2,0,1,0,
+ 5,0,1,0,2,0,1,0,
+ 3,0,1,0,2,0,1,0,
+ 4,0,1,0,2,0,1,0,
+ 3,0,1,0,2,0,1,0,
+
+ 0,0,0,2,0,4,4,6,
+ 0,8,8,10,8,12,12,14,
+ 0,16,16,18,16,20,20,22,
+ 16,24,24,26,24,28,28,30,
+ 0,32,32,34,32,36,36,38,
+ 32,40,40,42,40,44,44,46,
+ 32,48,48,50,48,52,52,54,
+ 48,56,56,58,56,60,60,62,
+};
+
+/* Maps a trackdir to the (4-way) direction the tile is exited when following
+* that trackdir */
+extern "C"
+const DiagDirection _trackdir_to_exitdir[] = {
+ DIAGDIR_NE,DIAGDIR_SE,DIAGDIR_NE,DIAGDIR_SE,DIAGDIR_SW,DIAGDIR_SE, DIAGDIR_NE,DIAGDIR_NE,
+ DIAGDIR_SW,DIAGDIR_NW,DIAGDIR_NW,DIAGDIR_SW,DIAGDIR_NW,DIAGDIR_NE,
+};
+
+/* Maps a diagonal direction to the all trackdirs that are connected to any
+* track entering in this direction (including those making 90 degree turns)
+*/
+extern "C"
+const TrackdirBits _exitdir_reaches_trackdirs[] = {
+ TRACKDIR_BIT_X_NE | TRACKDIR_BIT_LOWER_E | TRACKDIR_BIT_LEFT_N, /* DIAGDIR_NE */
+ TRACKDIR_BIT_Y_SE | TRACKDIR_BIT_LEFT_S | TRACKDIR_BIT_UPPER_E, /* DIAGDIR_SE */
+ TRACKDIR_BIT_X_SW | TRACKDIR_BIT_UPPER_W | TRACKDIR_BIT_RIGHT_S, /* DIAGDIR_SW */
+ TRACKDIR_BIT_Y_NW | TRACKDIR_BIT_RIGHT_N | TRACKDIR_BIT_LOWER_W /* DIAGDIR_NW */
+};
+
+/* Maps a trackdir to all trackdirs that make 90 deg turns with it. */
+extern "C"
+const TrackdirBits _track_crosses_trackdirs[] = {
+ TRACKDIR_BIT_Y_SE | TRACKDIR_BIT_Y_NW, /* TRACK_X */
+ TRACKDIR_BIT_X_NE | TRACKDIR_BIT_X_SW, /* TRACK_Y */
+ TRACKDIR_BIT_RIGHT_N | TRACKDIR_BIT_RIGHT_S | TRACKDIR_BIT_LEFT_N | TRACKDIR_BIT_LEFT_S, /* TRACK_UPPER */
+ TRACKDIR_BIT_RIGHT_N | TRACKDIR_BIT_RIGHT_S | TRACKDIR_BIT_LEFT_N | TRACKDIR_BIT_LEFT_S, /* TRACK_LOWER */
+ TRACKDIR_BIT_UPPER_W | TRACKDIR_BIT_UPPER_E | TRACKDIR_BIT_LOWER_W | TRACKDIR_BIT_LOWER_E, /* TRACK_LEFT */
+ TRACKDIR_BIT_UPPER_W | TRACKDIR_BIT_UPPER_E | TRACKDIR_BIT_LOWER_W | TRACKDIR_BIT_LOWER_E /* TRACK_RIGHT */
+};
+
+
+
+
+
+
+
diff --git a/yapf/unittest/unittest.dsp b/yapf/unittest/unittest.dsp
new file mode 100644
index 000000000..627138ab2
--- /dev/null
+++ b/yapf/unittest/unittest.dsp
@@ -0,0 +1,172 @@
+# Microsoft Developer Studio Project File - Name="unittest" - Package Owner=<4>
+# Microsoft Developer Studio Generated Build File, Format Version 6.00
+# ** DO NOT EDIT **
+
+# TARGTYPE "Win32 (x86) Console Application" 0x0103
+
+CFG=unittest - Win32 Debug
+!MESSAGE This is not a valid makefile. To build this project using NMAKE,
+!MESSAGE use the Export Makefile command and run
+!MESSAGE
+!MESSAGE NMAKE /f "unittest.mak".
+!MESSAGE
+!MESSAGE You can specify a configuration when running NMAKE
+!MESSAGE by defining the macro CFG on the command line. For example:
+!MESSAGE
+!MESSAGE NMAKE /f "unittest.mak" CFG="unittest - Win32 Debug"
+!MESSAGE
+!MESSAGE Possible choices for configuration are:
+!MESSAGE
+!MESSAGE "unittest - Win32 Release" (based on "Win32 (x86) Console Application")
+!MESSAGE "unittest - Win32 Debug" (based on "Win32 (x86) Console Application")
+!MESSAGE
+
+# Begin Project
+# PROP AllowPerConfigDependencies 0
+# PROP Scc_ProjName ""
+# PROP Scc_LocalPath ""
+CPP=cl.exe
+RSC=rc.exe
+
+!IF "$(CFG)" == "unittest - Win32 Release"
+
+# PROP BASE Use_MFC 0
+# PROP BASE Use_Debug_Libraries 0
+# PROP BASE Output_Dir "unittest___Win32_Release"
+# PROP BASE Intermediate_Dir "unittest___Win32_Release"
+# PROP BASE Target_Dir ""
+# PROP Use_MFC 0
+# PROP Use_Debug_Libraries 0
+# PROP Output_Dir "unittest___Win32_Release"
+# PROP Intermediate_Dir "unittest___Win32_Release"
+# PROP Target_Dir ""
+# ADD BASE CPP /nologo /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /c
+# ADD CPP /nologo /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /c
+# ADD BASE RSC /l 0x409 /d "NDEBUG"
+# ADD RSC /l 0x409 /d "NDEBUG"
+BSC32=bscmake.exe
+# ADD BASE BSC32 /nologo
+# ADD BSC32 /nologo
+LINK32=link.exe
+# ADD BASE LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /machine:I386
+# ADD LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /machine:I386
+
+!ELSEIF "$(CFG)" == "unittest - Win32 Debug"
+
+# PROP BASE Use_MFC 0
+# PROP BASE Use_Debug_Libraries 1
+# PROP BASE Output_Dir "unittest___Win32_Debug"
+# PROP BASE Intermediate_Dir "unittest___Win32_Debug"
+# PROP BASE Target_Dir ""
+# PROP Use_MFC 0
+# PROP Use_Debug_Libraries 1
+# PROP Output_Dir "unittest___Win32_Debug"
+# PROP Intermediate_Dir "unittest___Win32_Debug"
+# PROP Target_Dir ""
+# ADD BASE CPP /nologo /W3 /Gm /GX /ZI /Od /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /GZ /c
+# ADD CPP /nologo /W3 /Gm /GX /ZI /Od /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /GZ /c
+# ADD BASE RSC /l 0x409 /d "_DEBUG"
+# ADD RSC /l 0x409 /d "_DEBUG"
+BSC32=bscmake.exe
+# ADD BASE BSC32 /nologo
+# ADD BSC32 /nologo
+LINK32=link.exe
+# ADD BASE LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /debug /machine:I386 /pdbtype:sept
+# ADD LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /debug /machine:I386 /pdbtype:sept
+
+!ENDIF
+
+# Begin Target
+
+# Name "unittest - Win32 Release"
+# Name "unittest - Win32 Debug"
+# Begin Group "Source Files"
+
+# PROP Default_Filter "cpp;c;cxx;rc;def;r;odl;idl;hpj;bat"
+# Begin Source File
+
+SOURCE=.\unittest.cpp
+# End Source File
+# End Group
+# Begin Group "Header Files"
+
+# PROP Default_Filter "h;hpp;hxx;hm;inl"
+# Begin Source File
+
+SOURCE=.\test_autocopyptr.h
+# End Source File
+# Begin Source File
+
+SOURCE=.\test_binaryheap.h
+# End Source File
+# Begin Source File
+
+SOURCE=.\test_blob.h
+# End Source File
+# Begin Source File
+
+SOURCE=.\test_fixedsizearray.h
+# End Source File
+# Begin Source File
+
+SOURCE=.\test_hashtable.h
+# End Source File
+# Begin Source File
+
+SOURCE=.\test_yapf.h
+# End Source File
+# Begin Source File
+
+SOURCE=.\unittest.h
+# End Source File
+# End Group
+# Begin Group "Resource Files"
+
+# PROP Default_Filter "ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe"
+# End Group
+# Begin Group "yapf"
+
+# PROP Default_Filter ""
+# Begin Source File
+
+SOURCE=..\array.hpp
+# End Source File
+# Begin Source File
+
+SOURCE=..\autocopyptr.hpp
+# End Source File
+# Begin Source File
+
+SOURCE=..\binaryheap.hpp
+# End Source File
+# Begin Source File
+
+SOURCE=..\blob.hpp
+# End Source File
+# Begin Source File
+
+SOURCE=..\countedptr.hpp
+# End Source File
+# Begin Source File
+
+SOURCE=..\fixedsizearray.hpp
+# End Source File
+# Begin Source File
+
+SOURCE=..\hashtable.hpp
+# End Source File
+# Begin Source File
+
+SOURCE=..\nodelist.hpp
+# End Source File
+# Begin Source File
+
+SOURCE=..\track_dir.hpp
+# End Source File
+# Begin Source File
+
+SOURCE=..\yapfbase.hpp
+# End Source File
+# End Group
+# End Target
+# End Project
diff --git a/yapf/unittest/unittest.h b/yapf/unittest/unittest.h
new file mode 100644
index 000000000..27ba4ebdd
--- /dev/null
+++ b/yapf/unittest/unittest.h
@@ -0,0 +1,34 @@
+/* $Id$ */
+
+#define UNITTEST
+
+extern int num_tests_failed;
+extern int num_tests_total;
+
+extern bool _dbg;
+#define DBG if(_dbg) printf
+
+
+#define CHECK_INT(case_num, val, should_be) \
+{ \
+ if((val) != (should_be)) { \
+ res |= (1 << case_num); \
+ printf("\n****** ERROR in case %d: " #val " = %d (should be %d)!", case_num, (val), (should_be)); \
+ } \
+}
+
+typedef int(*TESTPROC)(bool silent);
+
+//#undef FORCEINLINE
+//#define FORCEINLINE
+
+
+#if defined(_WIN32) || defined(_WIN64)
+# include <windows.h>
+#else
+#endif
+
+
+
+
+
diff --git a/yapf/unittest/unittest.vcproj b/yapf/unittest/unittest.vcproj
new file mode 100644
index 000000000..59d375bc5
--- /dev/null
+++ b/yapf/unittest/unittest.vcproj
@@ -0,0 +1,187 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+ ProjectType="Visual C++"
+ Version="7.10"
+ Name="unittest"
+ ProjectGUID="{4AECBDC3-D57E-4AFB-90BD-DDF10707588C}"
+ Keyword="Win32Proj">
+ <Platforms>
+ <Platform
+ Name="Win32"/>
+ </Platforms>
+ <Configurations>
+ <Configuration
+ Name="Debug|Win32"
+ OutputDirectory="Debug"
+ IntermediateDirectory="Debug"
+ ConfigurationType="1"
+ CharacterSet="2">
+ <Tool
+ Name="VCCLCompilerTool"
+ Optimization="0"
+ PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE"
+ MinimalRebuild="TRUE"
+ BasicRuntimeChecks="3"
+ RuntimeLibrary="5"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="4"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(OutDir)/unittest.exe"
+ LinkIncremental="2"
+ GenerateDebugInformation="TRUE"
+ ProgramDatabaseFile="$(OutDir)/unittest.pdb"
+ SubSystem="1"
+ TargetMachine="1"/>
+ <Tool
+ Name="VCMIDLTool"/>
+ <Tool
+ Name="VCPostBuildEventTool"/>
+ <Tool
+ Name="VCPreBuildEventTool"/>
+ <Tool
+ Name="VCPreLinkEventTool"/>
+ <Tool
+ Name="VCResourceCompilerTool"/>
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"/>
+ <Tool
+ Name="VCXMLDataGeneratorTool"/>
+ <Tool
+ Name="VCWebDeploymentTool"/>
+ <Tool
+ Name="VCManagedWrapperGeneratorTool"/>
+ <Tool
+ Name="VCAuxiliaryManagedWrapperGeneratorTool"/>
+ </Configuration>
+ <Configuration
+ Name="Release|Win32"
+ OutputDirectory="Release"
+ IntermediateDirectory="Release"
+ ConfigurationType="1"
+ CharacterSet="2">
+ <Tool
+ Name="VCCLCompilerTool"
+ PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE"
+ RuntimeLibrary="4"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="3"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(OutDir)/unittest.exe"
+ LinkIncremental="1"
+ GenerateDebugInformation="TRUE"
+ SubSystem="1"
+ OptimizeReferences="2"
+ EnableCOMDATFolding="2"
+ TargetMachine="1"/>
+ <Tool
+ Name="VCMIDLTool"/>
+ <Tool
+ Name="VCPostBuildEventTool"/>
+ <Tool
+ Name="VCPreBuildEventTool"/>
+ <Tool
+ Name="VCPreLinkEventTool"/>
+ <Tool
+ Name="VCResourceCompilerTool"/>
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"/>
+ <Tool
+ Name="VCXMLDataGeneratorTool"/>
+ <Tool
+ Name="VCWebDeploymentTool"/>
+ <Tool
+ Name="VCManagedWrapperGeneratorTool"/>
+ <Tool
+ Name="VCAuxiliaryManagedWrapperGeneratorTool"/>
+ </Configuration>
+ </Configurations>
+ <References>
+ </References>
+ <Files>
+ <Filter
+ Name="Source Files"
+ Filter="cpp;c;cxx;def;odl;idl;hpj;bat;asm;asmx"
+ UniqueIdentifier="{4FC737F1-C7A5-4376-A066-2A32D752A2FF}">
+ <File
+ RelativePath=".\unittest.cpp">
+ </File>
+ </Filter>
+ <Filter
+ Name="Header Files"
+ Filter="h;hpp;hxx;hm;inl;inc;xsd"
+ UniqueIdentifier="{93995380-89BD-4b04-88EB-625FBE52EBFB}">
+ <File
+ RelativePath=".\test_autocopyptr.h">
+ </File>
+ <File
+ RelativePath=".\test_binaryheap.h">
+ </File>
+ <File
+ RelativePath=".\test_blob.h">
+ </File>
+ <File
+ RelativePath=".\test_fixedsizearray.h">
+ </File>
+ <File
+ RelativePath=".\test_hashtable.h">
+ </File>
+ <File
+ RelativePath=".\test_yapf.h">
+ </File>
+ <File
+ RelativePath=".\unittest.h">
+ </File>
+ </Filter>
+ <Filter
+ Name="Resource Files"
+ Filter="rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx"
+ UniqueIdentifier="{67DA6AB6-F800-4c08-8B7A-83BB121AAD01}">
+ </Filter>
+ <Filter
+ Name="yapf"
+ Filter="">
+ <File
+ RelativePath="..\array.hpp">
+ </File>
+ <File
+ RelativePath="..\autocopyptr.hpp">
+ </File>
+ <File
+ RelativePath="..\binaryheap.hpp">
+ </File>
+ <File
+ RelativePath="..\blob.hpp">
+ </File>
+ <File
+ RelativePath="..\countedptr.hpp">
+ </File>
+ <File
+ RelativePath="..\fixedsizearray.hpp">
+ </File>
+ <File
+ RelativePath="..\hashtable.hpp">
+ </File>
+ <File
+ RelativePath="..\nodelist.hpp">
+ </File>
+ <File
+ RelativePath="..\track_dir.hpp">
+ </File>
+ <File
+ RelativePath="..\yapfbase.hpp">
+ </File>
+ </Filter>
+ </Files>
+ <Globals>
+ </Globals>
+</VisualStudioProject>
diff --git a/yapf/unittest/unittest_vs80.vcproj b/yapf/unittest/unittest_vs80.vcproj
new file mode 100644
index 000000000..34680386f
--- /dev/null
+++ b/yapf/unittest/unittest_vs80.vcproj
@@ -0,0 +1,272 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+ ProjectType="Visual C++"
+ Version="8.00"
+ Name="unittest"
+ ProjectGUID="{01F91A15-3DA0-4FD1-981D-38F935BDD8FE}"
+ RootNamespace="test_bh"
+ Keyword="Win32Proj"
+ >
+ <Platforms>
+ <Platform
+ Name="Win32"
+ />
+ </Platforms>
+ <ToolFiles>
+ </ToolFiles>
+ <Configurations>
+ <Configuration
+ Name="Debug|Win32"
+ OutputDirectory="$(SolutionDir)../$(ConfigurationName)"
+ IntermediateDirectory="$(SolutionDir)../$(ConfigurationName)"
+ ConfigurationType="1"
+ CharacterSet="1"
+ >
+ <Tool
+ Name="VCPreBuildEventTool"
+ />
+ <Tool
+ Name="VCCustomBuildTool"
+ />
+ <Tool
+ Name="VCXMLDataGeneratorTool"
+ />
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"
+ />
+ <Tool
+ Name="VCMIDLTool"
+ />
+ <Tool
+ Name="VCCLCompilerTool"
+ Optimization="0"
+ InlineFunctionExpansion="0"
+ PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE"
+ MinimalRebuild="true"
+ BasicRuntimeChecks="0"
+ RuntimeLibrary="3"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="true"
+ DebugInformationFormat="3"
+ />
+ <Tool
+ Name="VCManagedResourceCompilerTool"
+ />
+ <Tool
+ Name="VCResourceCompilerTool"
+ />
+ <Tool
+ Name="VCPreLinkEventTool"
+ />
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(SolutionDir)../bin/$(ProjectName).exe"
+ LinkIncremental="2"
+ GenerateDebugInformation="true"
+ SubSystem="1"
+ TargetMachine="1"
+ />
+ <Tool
+ Name="VCALinkTool"
+ />
+ <Tool
+ Name="VCManifestTool"
+ />
+ <Tool
+ Name="VCXDCMakeTool"
+ />
+ <Tool
+ Name="VCBscMakeTool"
+ />
+ <Tool
+ Name="VCFxCopTool"
+ />
+ <Tool
+ Name="VCAppVerifierTool"
+ />
+ <Tool
+ Name="VCWebDeploymentTool"
+ />
+ <Tool
+ Name="VCPostBuildEventTool"
+ />
+ </Configuration>
+ <Configuration
+ Name="Release|Win32"
+ OutputDirectory="$(SolutionDir)../$(ConfigurationName)"
+ IntermediateDirectory="$(SolutionDir)../$(ConfigurationName)"
+ ConfigurationType="1"
+ CharacterSet="1"
+ WholeProgramOptimization="1"
+ >
+ <Tool
+ Name="VCPreBuildEventTool"
+ />
+ <Tool
+ Name="VCCustomBuildTool"
+ />
+ <Tool
+ Name="VCXMLDataGeneratorTool"
+ />
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"
+ />
+ <Tool
+ Name="VCMIDLTool"
+ />
+ <Tool
+ Name="VCCLCompilerTool"
+ InlineFunctionExpansion="2"
+ EnableIntrinsicFunctions="true"
+ FavorSizeOrSpeed="1"
+ OmitFramePointers="true"
+ PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE"
+ RuntimeLibrary="2"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="true"
+ DebugInformationFormat="3"
+ />
+ <Tool
+ Name="VCManagedResourceCompilerTool"
+ />
+ <Tool
+ Name="VCResourceCompilerTool"
+ />
+ <Tool
+ Name="VCPreLinkEventTool"
+ />
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(SolutionDir)../bin/$(ProjectName).exe"
+ LinkIncremental="1"
+ GenerateDebugInformation="true"
+ SubSystem="1"
+ OptimizeReferences="2"
+ EnableCOMDATFolding="2"
+ TargetMachine="1"
+ />
+ <Tool
+ Name="VCALinkTool"
+ />
+ <Tool
+ Name="VCManifestTool"
+ />
+ <Tool
+ Name="VCXDCMakeTool"
+ />
+ <Tool
+ Name="VCBscMakeTool"
+ />
+ <Tool
+ Name="VCFxCopTool"
+ />
+ <Tool
+ Name="VCAppVerifierTool"
+ />
+ <Tool
+ Name="VCWebDeploymentTool"
+ />
+ <Tool
+ Name="VCPostBuildEventTool"
+ />
+ </Configuration>
+ </Configurations>
+ <References>
+ </References>
+ <Files>
+ <Filter
+ Name="Source Files"
+ Filter="cpp;c;cc;cxx;def;odl;idl;hpj;bat;asm;asmx"
+ UniqueIdentifier="{4FC737F1-C7A5-4376-A066-2A32D752A2FF}"
+ >
+ <File
+ RelativePath=".\unittest.cpp"
+ >
+ </File>
+ </Filter>
+ <Filter
+ Name="Header Files"
+ Filter="h;hpp;hxx;hm;inl;inc;xsd"
+ UniqueIdentifier="{93995380-89BD-4b04-88EB-625FBE52EBFB}"
+ >
+ <File
+ RelativePath=".\test_autocopyptr.h"
+ >
+ </File>
+ <File
+ RelativePath=".\test_binaryheap.h"
+ >
+ </File>
+ <File
+ RelativePath=".\test_blob.h"
+ >
+ </File>
+ <File
+ RelativePath=".\test_fixedsizearray.h"
+ >
+ </File>
+ <File
+ RelativePath=".\test_hashtable.h"
+ >
+ </File>
+ <File
+ RelativePath=".\test_yapf.h"
+ >
+ </File>
+ <File
+ RelativePath=".\unittest.h"
+ >
+ </File>
+ </Filter>
+ <Filter
+ Name="Resource Files"
+ Filter="rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav"
+ UniqueIdentifier="{67DA6AB6-F800-4c08-8B7A-83BB121AAD01}"
+ >
+ </Filter>
+ <Filter
+ Name="yapf"
+ >
+ <File
+ RelativePath="..\array.hpp"
+ >
+ </File>
+ <File
+ RelativePath="..\autocopyptr.hpp"
+ >
+ </File>
+ <File
+ RelativePath="..\binaryheap.hpp"
+ >
+ </File>
+ <File
+ RelativePath="..\blob.hpp"
+ >
+ </File>
+ <File
+ RelativePath="..\countedptr.hpp"
+ >
+ </File>
+ <File
+ RelativePath="..\fixedsizearray.hpp"
+ >
+ </File>
+ <File
+ RelativePath="..\hashtable.hpp"
+ >
+ </File>
+ <File
+ RelativePath="..\nodelist.hpp"
+ >
+ </File>
+ <File
+ RelativePath="..\track_dir.hpp"
+ >
+ </File>
+ </Filter>
+ </Files>
+ <Globals>
+ </Globals>
+</VisualStudioProject>
diff --git a/yapf/yapf.h b/yapf/yapf.h
new file mode 100644
index 000000000..ae668ac25
--- /dev/null
+++ b/yapf/yapf.h
@@ -0,0 +1,54 @@
+/* $Id$ */
+
+#ifndef YAPF_H
+#define YAPF_H
+
+#include "../debug.h"
+
+Trackdir YapfChooseShipTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks);
+Trackdir YapfChooseRoadTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir);
+Trackdir YapfChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs);
+
+Depot* YapfFindNearestRoadDepot(const Vehicle *v);
+bool YapfFindNearestRailDepotTwoWay(Vehicle *v, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed);
+
+bool YapfCheckReverseTrain(Vehicle* v);
+
+void YapfNotifyTrackLayoutChange(TileIndex tile, Track track);
+
+
+void* NpfBeginInterval(void);
+int NpfEndInterval(void* perf);
+
+extern int _aystar_stats_open_size;
+extern int _aystar_stats_closed_size;
+
+
+/** Base struct for track followers. */
+typedef struct FollowTrack_t
+{
+ Vehicle* m_veh;
+ TileIndex m_old_tile;
+ Trackdir m_old_td;
+ TileIndex m_new_tile;
+ TrackdirBits m_new_td_bits;
+// TrackdirBits m_red_td_bits;
+ DiagDirection m_exitdir;
+ bool m_is_tunnel;
+ int m_tunnel_tiles_skipped;
+} FollowTrack_t;
+
+/** track followers */
+bool FollowTrackWater (FollowTrack_t *This, TileIndex old_tile, Trackdir old_td);
+bool FollowTrackRoad (FollowTrack_t *This, TileIndex old_tile, Trackdir old_td);
+bool FollowTrackRail (FollowTrack_t *This, TileIndex old_tile, Trackdir old_td);
+bool FollowTrackWaterNo90(FollowTrack_t *This, TileIndex old_tile, Trackdir old_td);
+bool FollowTrackRoadNo90 (FollowTrack_t *This, TileIndex old_tile, Trackdir old_td);
+bool FollowTrackRailNo90 (FollowTrack_t *This, TileIndex old_tile, Trackdir old_td);
+
+enum {
+ YAPF_TILE_LENGTH = 100,
+ YAPF_TILE_CORNER_LENGTH = 71
+};
+
+#endif /* YAPF_H */
diff --git a/yapf/yapf.hpp b/yapf/yapf.hpp
new file mode 100644
index 000000000..d4f7b6936
--- /dev/null
+++ b/yapf/yapf.hpp
@@ -0,0 +1,111 @@
+/* $Id$ */
+
+#ifndef YAPF_HPP
+#define YAPF_HPP
+
+
+
+#include "track_dir.hpp"
+
+EXTERN_C_BEGIN
+#include "../depot.h"
+#include "../road_map.h"
+#include "../tunnel_map.h"
+#include "../bridge_map.h"
+#include "../bridge.h"
+#include "../station_map.h"
+#include "../vehicle.h"
+#include "../variables.h"
+#include "../functions.h"
+#include "yapf.h"
+#include "../pathfind.h"
+#include "../waypoint.h"
+#include "../debug.h"
+EXTERN_C_END
+
+EXTERN_C_BEGIN
+ extern Patches _patches_newgame;
+ extern uint64 _rdtsc(void);
+EXTERN_C_END
+
+#include <limits.h>
+
+#if defined(_WIN32) || defined(_WIN64)
+# include <windows.h>
+#else
+# include <time.h>
+#endif
+
+struct CPerformanceTimer
+{
+ int64 m_start;
+ int64 m_acc;
+
+ CPerformanceTimer() : m_start(0), m_acc(0) {}
+
+ FORCEINLINE void Start() {m_start = QueryTime();}
+ FORCEINLINE void Stop() {m_acc += QueryTime() - m_start;}
+ FORCEINLINE int Get(int64 coef) {return (int)(m_acc * coef / QueryFrequency());}
+
+#if !defined(UNITTEST) && 1
+ FORCEINLINE int64 QueryTime() {return _rdtsc();}
+ FORCEINLINE int64 QueryFrequency() {return ((int64)2200 * 1000000);}
+#elif defined(_WIN32) || defined(_WIN64)
+ FORCEINLINE int64 QueryTime() {LARGE_INTEGER c; QueryPerformanceCounter(&c); return c.QuadPart;}
+ FORCEINLINE int64 QueryFrequency() {LARGE_INTEGER f; QueryPerformanceFrequency(&f); return f.QuadPart;}
+#elif defined(CLOCK_THREAD_CPUTIME_ID)
+ FORCEINLINE int64 QueryTime()
+ {
+ timespec ts;
+ int ret = clock_gettime(CLOCK_THREAD_CPUTIME_ID, &ts);
+ if (ret != 0) return 0;
+ return (ts.tv_sec * 1000000000LL) + ts.tv_nsec;
+ }
+ FORCEINLINE int64 QueryFrequency()
+ {
+ return 1000000000;
+ }
+#else
+ int64 QueryTime() {return 0;}
+ int64 QueryFrequency() {return 1;}
+#endif
+};
+
+struct CPerfStartReal
+{
+ CPerformanceTimer* m_pperf;
+
+ FORCEINLINE CPerfStartReal(CPerformanceTimer& perf) : m_pperf(&perf) {if (m_pperf != NULL) m_pperf->Start();}
+ FORCEINLINE ~CPerfStartReal() {Stop();}
+ FORCEINLINE void Stop() {if (m_pperf != NULL) {m_pperf->Stop(); m_pperf = NULL;}}
+};
+
+struct CPerfStartFake
+{
+ FORCEINLINE CPerfStartFake(CPerformanceTimer& perf) {}
+ FORCEINLINE ~CPerfStartFake() {}
+ FORCEINLINE void Stop() {}
+};
+
+typedef CPerfStartFake CPerfStart;
+
+
+//#undef FORCEINLINE
+//#define FORCEINLINE inline
+
+#include "crc32.hpp"
+#include "blob.hpp"
+#include "fixedsizearray.hpp"
+#include "array.hpp"
+#include "hashtable.hpp"
+#include "binaryheap.hpp"
+#include "nodelist.hpp"
+#include "yapf_base.hpp"
+#include "yapf_node.hpp"
+#include "yapf_common.hpp"
+#include "follow_track.hpp"
+#include "yapf_costbase.hpp"
+#include "yapf_costcache.hpp"
+
+
+#endif /* YAPF_HPP */
diff --git a/yapf/yapf_base.hpp b/yapf/yapf_base.hpp
new file mode 100644
index 000000000..c504fc468
--- /dev/null
+++ b/yapf/yapf_base.hpp
@@ -0,0 +1,329 @@
+/* $Id$ */
+
+#ifndef YAPF_BASE_HPP
+#define YAPF_BASE_HPP
+
+EXTERN_C_BEGIN
+#include "../debug.h"
+EXTERN_C_END
+
+#include "fixedsizearray.hpp"
+#include "blob.hpp"
+#include "nodelist.hpp"
+
+extern int _total_pf_time_us;
+
+/** CYapfBaseT - A-star type path finder base class.
+ Derive your own pathfinder from it. You must provide the following template argument:
+ Types - used as collection of local types used in pathfinder
+
+ Requirements for the Types struct:
+ ----------------------------------
+ The following types must be defined in the 'Types' argument:
+ - Types::Tpf - your pathfinder derived from CYapfBaseT
+ - Types::NodeList - open/closed node list (look at CNodeList_HashTableT)
+ NodeList needs to have defined local type Titem - defines the pathfinder node type.
+ Node needs to define local type Key - the node key in the collection ()
+
+ For node list you can use template class CNodeList_HashTableT, for which
+ you need to declare only your node type. Look at test_yapf.h for an example.
+
+
+ Requrements to your pathfinder class derived from CYapfBaseT:
+ -------------------------------------------------------------
+ Your pathfinder derived class needs to implement following methods:
+ FORCEINLINE void PfSetStartupNodes()
+ FORCEINLINE void PfFollowNode(Node& org)
+ FORCEINLINE bool PfCalcCost(Node& n)
+ FORCEINLINE bool PfCalcEstimate(Node& n)
+ FORCEINLINE bool PfDetectDestination(Node& n)
+
+ For more details about those methods, look at the end of CYapfBaseT
+ declaration. There are some examples. For another example look at
+ test_yapf.h (part or unittest project).
+*/
+template <class Types>
+class CYapfBaseT {
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::NodeList NodeList; ///< our node list
+ typedef typename NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+
+ NodeList m_nodes; ///< node list multi-container
+protected:
+ Node* m_pBestDestNode; ///< pointer to the destination node found at last round
+ Node* m_pBestIntermediateNode;
+ const YapfSettings *m_settings;
+ int m_max_search_nodes;
+ Vehicle* m_veh;
+
+ int m_stats_cost_calcs;
+ int m_stats_cache_hits;
+
+public:
+ CPerformanceTimer m_perf_cost;
+ CPerformanceTimer m_perf_slope_cost;
+ CPerformanceTimer m_perf_ts_cost;
+ CPerformanceTimer m_perf_other_cost;
+
+public:
+ int m_num_steps; ///< this is there for debugging purposes (hope it doesn't hurt)
+
+public:
+ // default constructor
+ FORCEINLINE CYapfBaseT()
+ : m_pBestDestNode(NULL)
+ , m_pBestIntermediateNode(NULL)
+#if defined(UNITTEST)
+ , m_settings(NULL)
+ , m_max_search_nodes(100000)
+#else
+ , m_settings(&_patches.yapf)
+ , m_max_search_nodes(PfGetSettings().max_search_nodes)
+#endif
+ , m_veh(NULL)
+ , m_stats_cost_calcs(0)
+ , m_stats_cache_hits(0)
+ , m_num_steps(0)
+ {
+ }
+
+ ~CYapfBaseT() {}
+
+protected:
+ FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+public:
+ FORCEINLINE const YapfSettings& PfGetSettings() const
+ {
+ return *m_settings;
+ }
+
+ /** Main pathfinder routine:
+ - set startup node(s)
+ - main loop that stops if:
+ - the destination was found
+ - or the open list is empty (no route to destination).
+ - or the maximum amount of loops reached - m_max_search_nodes (default = 10000)
+ @return true if the path was found */
+ inline bool FindPath(Vehicle* v)
+ {
+ m_veh = v;
+
+ CPerformanceTimer perf;
+ perf.Start();
+ Yapf().PfSetStartupNodes();
+
+ while (true) {
+ m_num_steps++;
+ Node& n = m_nodes.GetBestOpenNode();
+ if (&n == NULL)
+ break;
+
+ // if the best open node was worse than the best path found, we can finish
+ if (m_pBestDestNode != NULL && m_pBestDestNode->GetCost() < n.GetCostEstimate())
+ break;
+
+ Yapf().PfFollowNode(n);
+ if (m_max_search_nodes == 0 || m_nodes.ClosedCount() < m_max_search_nodes) {
+ m_nodes.PopOpenNode(n.GetKey());
+ m_nodes.InsertClosedNode(n);
+ } else {
+ m_pBestDestNode = m_pBestIntermediateNode;
+ break;
+ }
+ }
+ bool bDestFound = (m_pBestDestNode != NULL);
+
+ int16 veh_idx = (m_veh != NULL) ? m_veh->unitnumber : 0;
+
+// if (veh_idx != 433) return bDestFound;
+
+ perf.Stop();
+ int t = perf.Get(1000000);
+ _total_pf_time_us += t;
+ char ttc = Yapf().TransportTypeChar();
+ float cache_hit_ratio = (float)m_stats_cache_hits / (float)(m_stats_cache_hits + m_stats_cost_calcs) * 100.0f;
+ int cost = bDestFound ? m_pBestDestNode->m_cost : -1;
+ int dist = bDestFound ? m_pBestDestNode->m_estimate - m_pBestDestNode->m_cost : -1;
+#ifdef UNITTEST
+ printf("%c%c%4d-%6d us -%5d rounds -%4d open -%5d closed - CHR %4.1f%% - c/d(%d, %d) - c%d(sc%d, ts%d, o%d) -- \n", bDestFound ? '-' : '!', ttc, veh_idx, t, m_num_steps, m_nodes.OpenCount(), m_nodes.ClosedCount(), cache_hit_ratio, cost, dist, m_perf_cost.Get(1000000), m_perf_slope_cost.Get(1000000), m_perf_ts_cost.Get(1000000), m_perf_other_cost.Get(1000000));
+#else
+ DEBUG(yapf, 1)("[YAPF][YAPF%c]%c%4d- %d us - %d rounds - %d open - %d closed - CHR %4.1f%% - c%d(sc%d, ts%d, o%d) -- ", ttc, bDestFound ? '-' : '!', veh_idx, t, m_num_steps, m_nodes.OpenCount(), m_nodes.ClosedCount(), cache_hit_ratio, cost, dist, m_perf_cost.Get(1000000), m_perf_slope_cost.Get(1000000), m_perf_ts_cost.Get(1000000), m_perf_other_cost.Get(1000000));
+#endif
+ return bDestFound;
+ }
+
+ /** If path was found return the best node that has reached the destination. Otherwise
+ return the best visited node (which was nearest to the destination).
+ */
+ FORCEINLINE Node& GetBestNode()
+ {
+ return (m_pBestDestNode != NULL) ? *m_pBestDestNode : *m_pBestIntermediateNode;
+ }
+
+ /** Calls NodeList::CreateNewNode() - allocates new node that can be filled and used
+ as argument for AddStartupNode() or AddNewNode()
+ */
+ FORCEINLINE Node& CreateNewNode()
+ {
+ Node& node = *m_nodes.CreateNewNode();
+ return node;
+ }
+
+ /** Add new node (created by CreateNewNode and filled with data) into open list */
+ FORCEINLINE void AddStartupNode(Node& n)
+ {
+ Yapf().PfNodeCacheFetch(n);
+ m_nodes.InsertOpenNode(n);
+ }
+
+ /** add multiple nodes - direct children of the given node */
+ FORCEINLINE void AddMultipleNodes(Node* parent, TileIndex tile, TrackdirBits td_bits)
+ {
+ for (TrackdirBits rtds = td_bits; rtds != TRACKDIR_BIT_NONE; rtds = (TrackdirBits)KillFirstBit2x64(rtds)) {
+ Trackdir td = (Trackdir)FindFirstBit2x64(rtds);
+ Node& n = Yapf().CreateNewNode();
+ n.Set(parent, tile, td);
+ Yapf().AddNewNode(n);
+ }
+ }
+
+ /** AddNewNode() - called by Tderived::PfFollowNode() for each child node.
+ Nodes are evaluated here and added into open list */
+ void AddNewNode(Node& n)
+ {
+ // evaluate the node
+ bool bCached = Yapf().PfNodeCacheFetch(n);
+ if (!bCached) {
+ m_stats_cost_calcs++;
+ } else {
+ m_stats_cache_hits++;
+ }
+
+ bool bValid = Yapf().PfCalcCost(n);
+
+ if (bCached) {
+ Yapf().PfNodeCacheFlush(n);
+ }
+
+ if (bValid) bValid = Yapf().PfCalcEstimate(n);
+
+ // have the cost or estimate callbacks marked this node as invalid?
+ if (!bValid) return;
+
+ // detect the destination
+ bool bDestination = Yapf().PfDetectDestination(n);
+ if (bDestination) {
+ if (m_pBestDestNode == NULL || n < *m_pBestDestNode) {
+ m_pBestDestNode = &n;
+ }
+ m_nodes.FoundBestNode(n);
+ return;
+ }
+
+ if (m_max_search_nodes > 0 && (m_pBestIntermediateNode == NULL || (m_pBestIntermediateNode->GetCostEstimate() - m_pBestIntermediateNode->GetCost()) > (n.GetCostEstimate() - n.GetCost()))) {
+ m_pBestIntermediateNode = &n;
+ }
+
+ // check new node against open list
+ Node& openNode = m_nodes.FindOpenNode(n.GetKey());
+ if (&openNode != NULL) {
+ // another node exists with the same key in the open list
+ // is it better than new one?
+ if (n.GetCostEstimate() < openNode.GetCostEstimate()) {
+ // update the old node by value from new one
+ m_nodes.PopOpenNode(n.GetKey());
+ openNode = n;
+ // add the updated old node back to open list
+ m_nodes.InsertOpenNode(openNode);
+ }
+ return;
+ }
+
+ // check new node against closed list
+ Node& closedNode = m_nodes.FindClosedNode(n.GetKey());
+ if (&closedNode != NULL) {
+ // another node exists with the same key in the closed list
+ // is it better than new one?
+ int node_est = n.GetCostEstimate();
+ int closed_est = closedNode.GetCostEstimate();
+ if (node_est < closed_est) {
+ // If this assert occurs, you have probably problem in
+ // your Tderived::PfCalcCost() or Tderived::PfCalcEstimate().
+ // The problem could be:
+ // - PfCalcEstimate() gives too large numbers
+ // - PfCalcCost() gives too small numbers
+ // - You have used negative cost penalty in some cases (cost bonus)
+ assert(0);
+
+ return;
+ }
+ return;
+ }
+ // the new node is really new
+ // add it to the open list
+ m_nodes.InsertOpenNode(n);
+ }
+
+ Vehicle* GetVehicle() const {return m_veh;}
+
+ // methods that should be implemented at derived class Types::Tpf (derived from CYapfBaseT)
+
+#if 0
+ /** Example: PfSetStartupNodes() - set source (origin) nodes */
+ FORCEINLINE void PfSetStartupNodes()
+ {
+ // example:
+ Node& n1 = *base::m_nodes.CreateNewNode();
+ .
+ . // setup node members here
+ .
+ base::m_nodes.InsertOpenNode(n1);
+ }
+
+ /** Example: PfFollowNode() - set following (child) nodes of the given node */
+ FORCEINLINE void PfFollowNode(Node& org)
+ {
+ for (each follower of node org) {
+ Node& n = *base::m_nodes.CreateNewNode();
+ .
+ . // setup node members here
+ .
+ n.m_parent = &org; // set node's parent to allow back tracking
+ AddNewNode(n);
+ }
+ }
+
+ /** Example: PfCalcCost() - set path cost from origin to the given node */
+ FORCEINLINE bool PfCalcCost(Node& n)
+ {
+ // evaluate last step cost
+ int cost = ...;
+ // set the node cost as sum of parent's cost and last step cost
+ n.m_cost = n.m_parent->m_cost + cost;
+ return true; // true if node is valid follower (i.e. no obstacle was found)
+ }
+
+ /** Example: PfCalcEstimate() - set path cost estimate from origin to the target through given node */
+ FORCEINLINE bool PfCalcEstimate(Node& n)
+ {
+ // evaluate the distance to our destination
+ int distance = ...;
+ // set estimate as sum of cost from origin + distance to the target
+ n.m_estimate = n.m_cost + distance;
+ return true; // true if node is valid (i.e. not too far away :)
+ }
+
+ /** Example: PfDetectDestination() - return true if the given node is our destination */
+ FORCEINLINE bool PfDetectDestination(Node& n)
+ {
+ bool bDest = (n.m_key.m_x == m_x2) && (n.m_key.m_y == m_y2);
+ return bDest;
+ }
+#endif
+};
+
+#endif /* YAPF_BASE_HPP */
diff --git a/yapf/yapf_common.cpp b/yapf/yapf_common.cpp
new file mode 100644
index 000000000..a0a911cf9
--- /dev/null
+++ b/yapf/yapf_common.cpp
@@ -0,0 +1,29 @@
+/* $Id$ */
+
+#include "../stdafx.h"
+
+#include "yapf.hpp"
+#include "follow_track.hpp"
+#include "yapf_node_rail.hpp"
+#include "yapf_costbase.hpp"
+#include "yapf_costcache.hpp"
+
+const TrackdirBits CYapfCostBase::c_upwards_slopes[] = {
+ TRACKDIR_BIT_NONE , // no tileh
+ TRACKDIR_BIT_X_SW | TRACKDIR_BIT_Y_NW, // 1
+ TRACKDIR_BIT_X_SW | TRACKDIR_BIT_Y_SE, // 2
+ TRACKDIR_BIT_X_SW , // 3
+ TRACKDIR_BIT_X_NE | TRACKDIR_BIT_Y_SE, // 4
+ TRACKDIR_BIT_NONE , // 5
+ TRACKDIR_BIT_Y_SE , // 6
+ TRACKDIR_BIT_NONE , // 7
+ TRACKDIR_BIT_X_NE | TRACKDIR_BIT_Y_NW, // 8,
+ TRACKDIR_BIT_Y_NW , // 9
+ TRACKDIR_BIT_NONE , //10
+ TRACKDIR_BIT_NONE , //11,
+ TRACKDIR_BIT_X_NE , //12
+ TRACKDIR_BIT_NONE , //13
+ TRACKDIR_BIT_NONE , //14
+ TRACKDIR_BIT_NONE , //15
+};
+
diff --git a/yapf/yapf_common.hpp b/yapf/yapf_common.hpp
new file mode 100644
index 000000000..e4d937a57
--- /dev/null
+++ b/yapf/yapf_common.hpp
@@ -0,0 +1,144 @@
+/* $Id$ */
+
+#ifndef YAPF_COMMON_HPP
+#define YAPF_COMMON_HPP
+
+
+template <class Types>
+class CYapfOriginTileT
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+protected:
+ TileIndex m_orgTile;
+ TrackdirBits m_orgTrackdirs;
+
+ FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+public:
+ void SetOrigin(TileIndex tile, TrackdirBits trackdirs)
+ {
+ m_orgTile = tile;
+ m_orgTrackdirs = trackdirs;
+ }
+
+ void PfSetStartupNodes()
+ {
+ for (TrackdirBits tdb = m_orgTrackdirs; tdb != TRACKDIR_BIT_NONE; tdb = (TrackdirBits)KillFirstBit2x64(tdb)) {
+ Trackdir td = (Trackdir)FindFirstBit2x64(tdb);
+ Node& n1 = Yapf().CreateNewNode();
+ n1.Set(NULL, m_orgTile, td);
+ Yapf().AddStartupNode(n1);
+ }
+ }
+};
+
+template <class Types>
+class CYapfOriginTileTwoWayT
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+protected:
+ TileIndex m_orgTile;
+ Trackdir m_orgTd;
+ TileIndex m_revTile;
+ Trackdir m_revTd;
+ int m_reverse_penalty;
+ bool m_treat_first_red_two_way_signal_as_eol;
+
+ FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+public:
+ void SetOrigin(TileIndex tile, Trackdir td, TileIndex tiler = INVALID_TILE, Trackdir tdr = INVALID_TRACKDIR, int reverse_penalty = 0, bool treat_first_red_two_way_signal_as_eol = true)
+ {
+ m_orgTile = tile;
+ m_orgTd = td;
+ m_revTile = tiler;
+ m_revTd = tdr;
+ m_reverse_penalty = reverse_penalty;
+ m_treat_first_red_two_way_signal_as_eol = treat_first_red_two_way_signal_as_eol;
+ }
+
+ void PfSetStartupNodes()
+ {
+ if (m_orgTile != INVALID_TILE && m_orgTd != INVALID_TRACKDIR) {
+ Node& n1 = Yapf().CreateNewNode();
+ n1.Set(NULL, m_orgTile, m_orgTd);
+ Yapf().AddStartupNode(n1);
+ }
+ if (m_revTile != INVALID_TILE && m_revTd != INVALID_TRACKDIR) {
+ Node& n2 = Yapf().CreateNewNode();
+ n2.Set(NULL, m_revTile, m_revTd);
+ n2.m_cost = m_reverse_penalty;
+ Yapf().AddStartupNode(n2);
+ }
+ }
+
+ FORCEINLINE bool TreatFirstRedTwoWaySignalAsEOL()
+ {
+ return Yapf().PfGetSettings().rail_firstred_twoway_eol && m_treat_first_red_two_way_signal_as_eol;
+ }
+};
+
+template <class Types>
+class CYapfDestinationTileT
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+protected:
+ TileIndex m_destTile;
+ TrackdirBits m_destTrackdirs;
+
+public:
+ void SetDestination(TileIndex tile, TrackdirBits trackdirs)
+ {
+ m_destTile = tile;
+ m_destTrackdirs = trackdirs;
+ }
+
+protected:
+ Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+public:
+ FORCEINLINE bool PfDetectDestination(Node& n)
+ {
+ bool bDest = (n.m_key.m_tile == m_destTile) && ((m_destTrackdirs & TrackdirToTrackdirBits(n.GetTrackdir())) != TRACKDIR_BIT_NONE);
+ return bDest;
+ }
+
+ inline bool PfCalcEstimate(Node& n)
+ {
+ int dx = abs(TileX(n.GetTile()) - TileX(m_destTile));
+ int dy = abs(TileY(n.GetTile()) - TileY(m_destTile));
+ assert(dx >= 0 && dy >= 0);
+ int dd = min(dx, dy);
+ int dxy = abs(dx - dy);
+ int d = 14 * dd + 10 * dxy;
+ n.m_estimate = n.m_cost + d /*+ d / 8*/;
+ return true;
+ }
+};
+
+template <class Ttypes>
+class CYapfT
+ : public Ttypes::PfBase
+ , public Ttypes::PfCost
+ , public Ttypes::PfCache
+ , public Ttypes::PfOrigin
+ , public Ttypes::PfDestination
+ , public Ttypes::PfFollow
+{
+};
+
+
+
+#endif /* YAPF_COMMON_HPP */
diff --git a/yapf/yapf_costbase.hpp b/yapf/yapf_costbase.hpp
new file mode 100644
index 000000000..7aa141bc8
--- /dev/null
+++ b/yapf/yapf_costbase.hpp
@@ -0,0 +1,26 @@
+/* $Id$ */
+
+#ifndef YAPF_COSTBASE_HPP
+#define YAPF_COSTBASE_HPP
+
+struct CYapfCostBase {
+ static const TrackdirBits c_upwards_slopes[16];
+
+ FORCEINLINE static bool stSlopeCost(TileIndex tile, Trackdir td)
+ {
+ if (IsDiagonalTrackdir(td)) {
+ uint tile_slope = GetTileSlope(tile, NULL) & 0x0F;
+ if ((c_upwards_slopes[tile_slope] & TrackdirToTrackdirBits(td)) != 0) {
+ return true;
+ }
+ }
+ return false;
+ }
+};
+
+struct CostRailSettings {
+ // look-ahead signal penalty
+};
+
+
+#endif /* YAPF_COSTBASE_HPP */
diff --git a/yapf/yapf_costcache.hpp b/yapf/yapf_costcache.hpp
new file mode 100644
index 000000000..4947e6cef
--- /dev/null
+++ b/yapf/yapf_costcache.hpp
@@ -0,0 +1,183 @@
+/* $Id$ */
+#ifndef YAPF_COSTCACHE_HPP
+#define YAPF_COSTCACHE_HPP
+
+
+/** CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements
+PfNodeCacheFetch() and PfNodeCacheFlush() callbacks. Used when nodes don't have CachedData
+defined (they don't count with any segment cost caching).
+*/
+template <class Types>
+class CYapfSegmentCostCacheNoneT
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+
+ FORCEINLINE bool PfNodeCacheFetch(Node& n)
+ {
+ return false;
+ };
+
+ FORCEINLINE void PfNodeCacheFlush(Node& n)
+ {
+ };
+};
+
+
+/** CYapfSegmentCostCacheLocalT - the yapf cost cache provider that implements fake segment
+cost caching functionality for yapf. Used when node needs caching, but you don't want to
+cache the segment costs.
+*/
+template <class Types>
+class CYapfSegmentCostCacheLocalT
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+ typedef typename Node::CachedData CachedData;
+ typedef typename CachedData::Key CacheKey;
+ typedef CArrayT<CachedData> LocalCache;
+
+protected:
+ LocalCache m_local_cache;
+
+ FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+public:
+ FORCEINLINE bool PfNodeCacheFetch(Node& n)
+ {
+ CacheKey key(n.GetKey());
+ Yapf().ConnectNodeToCachedData(n, *new (&m_local_cache.AddNC()) CachedData(key));
+ return false;
+ };
+
+ FORCEINLINE void PfNodeCacheFlush(Node& n)
+ {
+ };
+};
+
+
+
+struct CSegmentCostCacheBase
+{
+ static int s_rail_change_counter;
+
+ static void NotifyTrackLayoutChange(TileIndex tile, Track track) {s_rail_change_counter++;}
+};
+
+
+/** CSegmentCostCacheT - template class providing hash-map and storage (heap)
+ of Tsegment structures. Each rail node contains pointer to the segment
+ that contains cached (or non-cached) segment cost information. Nodes can
+ differ by key type, but they use the same segment type. Segment key should
+ be always the same (TileIndex + DiagDirection) that represent the beginning
+ of the segment (origin tile and exit-dir from this tile).
+ Different CYapfCachedCostT types can share the same type of CSegmentCostCacheT.
+ Look at CYapfRailSegment (yapf_node_rail.hpp) for the segment example */
+
+template <class Tsegment>
+struct CSegmentCostCacheT
+ : public CSegmentCostCacheBase
+{
+ enum {c_hash_bits = 14};
+
+ typedef CHashTableT<Tsegment, c_hash_bits> HashTable;
+ typedef CArrayT<Tsegment> Heap;
+ typedef typename Tsegment::Key Key; ///< key to hash table
+
+ HashTable m_map;
+ Heap m_heap;
+
+ FORCEINLINE CSegmentCostCacheT() {}
+
+ FORCEINLINE Tsegment& Get(Key& key, bool *found)
+ {
+ Tsegment* item = &m_map.Find(key);
+ if (item == NULL) {
+ *found = false;
+ item = new (&m_heap.AddNC()) Tsegment(key);
+ m_map.Push(*item);
+ } else {
+ *found = true;
+ }
+ return *item;
+ }
+};
+
+/** CYapfSegmentCostCacheGlobalT - the yapf cost cache provider that adds the segment cost
+ caching functionality to yapf. Using this class as base of your will provide the global
+ segment cost caching services for your Nodes.
+*/
+template <class Types>
+class CYapfSegmentCostCacheGlobalT
+ : public CYapfSegmentCostCacheLocalT<Types>
+{
+public:
+ typedef CYapfSegmentCostCacheLocalT<Types> Tlocal;
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+ typedef typename Node::CachedData CachedData;
+ typedef typename CachedData::Key CacheKey;
+ typedef CSegmentCostCacheT<CachedData> Cache;
+
+protected:
+ Cache& m_global_cache;
+
+ FORCEINLINE CYapfSegmentCostCacheGlobalT() : m_global_cache(stGetGlobalCache()) {};
+
+ FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+ FORCEINLINE static Cache*& stGlobalCachePtr() {static Cache* pC = NULL; return pC;}
+
+ FORCEINLINE static Cache& stGetGlobalCache()
+ {
+ static int last_rail_change_counter = 0;
+ static uint32 last_day = 0;
+
+ // some statistics
+ if (last_day != _date) {
+ last_day = _date;
+ DEBUG(yapf, 1)("pf time today:%5d ms\n", _total_pf_time_us / 1000);
+ _total_pf_time_us = 0;
+ }
+
+ Cache*& pC = stGlobalCachePtr();
+
+ // delete the cache sometimes...
+ if (pC != NULL && last_rail_change_counter != Cache::s_rail_change_counter) {
+ last_rail_change_counter = Cache::s_rail_change_counter;
+ delete pC;
+ pC = NULL;
+ }
+
+ if (pC == NULL)
+ pC = new Cache();
+ return *pC;
+ }
+
+public:
+ FORCEINLINE bool PfNodeCacheFetch(Node& n)
+ {
+ if (!Yapf().CanUseGlobalCache(n)) {
+ return Tlocal::PfNodeCacheFetch(n);
+ }
+ CacheKey key(n.GetKey());
+ bool found;
+ CachedData& item = m_global_cache.Get(key, &found);
+ Yapf().ConnectNodeToCachedData(n, item);
+ return found;
+ };
+
+ FORCEINLINE void PfNodeCacheFlush(Node& n)
+ {
+ };
+
+};
+
+
+
+
+#endif /* YAPF_COSTCACHE_HPP */
diff --git a/yapf/yapf_costrail.hpp b/yapf/yapf_costrail.hpp
new file mode 100644
index 000000000..3c01e47d0
--- /dev/null
+++ b/yapf/yapf_costrail.hpp
@@ -0,0 +1,331 @@
+/* $Id$ */
+
+#ifndef YAPF_COSTRAIL_HPP
+#define YAPF_COSTRAIL_HPP
+
+
+template <class Types>
+class CYapfCostRailT
+ : public CYapfCostBase
+ , public CostRailSettings
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::TrackFollower TrackFollower;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+ typedef typename Node::CachedData CachedData;
+
+protected:
+ int m_max_cost;
+ CBlobT<int> m_sig_look_ahead_costs;
+
+ static const int s_max_segment_cost = 10000;
+
+ CYapfCostRailT() : m_max_cost(0)
+ {
+ // pre-compute look-ahead penalties into array
+ int p0 = Yapf().PfGetSettings().rail_look_ahead_signal_p0;
+ int p1 = Yapf().PfGetSettings().rail_look_ahead_signal_p1;
+ int p2 = Yapf().PfGetSettings().rail_look_ahead_signal_p2;
+ int *pen = m_sig_look_ahead_costs.GrowSizeNC(Yapf().PfGetSettings().rail_look_ahead_max_signals);
+ for (uint i = 0; i < Yapf().PfGetSettings().rail_look_ahead_max_signals; i++)
+ pen[i] = p0 + i * (p1 + i * p2);
+ }
+
+ Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+public:
+ FORCEINLINE int SlopeCost(TileIndex tile, Trackdir td)
+ {
+ CPerfStart perf_cost(Yapf().m_perf_slope_cost);
+ if (!stSlopeCost(tile, td)) return 0;
+ return Yapf().PfGetSettings().rail_slope_penalty;
+ }
+
+ FORCEINLINE int CurveCost(Trackdir td1, Trackdir td2)
+ {
+ int cost = 0;
+ if (TrackFollower::Allow90degTurns()
+ && ((TrackdirToTrackdirBits(td2) & (TrackdirBits)TrackdirCrossesTrackdirs(td1)) != 0)) {
+ // 90-deg curve penalty
+ cost += Yapf().PfGetSettings().rail_curve90_penalty;
+ } else if (td2 != NextTrackdir(td1)) {
+ // 45-deg curve penalty
+ cost += Yapf().PfGetSettings().rail_curve45_penalty;
+ }
+ return cost;
+ }
+
+ /** return one tile cost. If tile is a tunnel entry, it is moved to the end of tunnel */
+ FORCEINLINE int OneTileCost(TileIndex& tile, Trackdir trackdir)
+ {
+ int cost = 0;
+ // set base cost
+ if (IsDiagonalTrackdir(trackdir)) {
+ cost += YAPF_TILE_LENGTH;
+ switch (GetTileType(tile)) {
+ case MP_STREET:
+ /* Increase the cost for level crossings */
+ if (IsLevelCrossing(tile))
+ cost += Yapf().PfGetSettings().rail_crossing_penalty;
+ break;
+
+ case MP_STATION:
+ // penalty for passing station tiles
+ cost += Yapf().PfGetSettings().rail_station_penalty;
+ break;
+
+ default:
+ break;
+ }
+ } else {
+ // non-diagonal trackdir
+ cost = YAPF_TILE_CORNER_LENGTH;
+ }
+ return cost;
+ }
+
+ int SignalCost(Node& n, TileIndex tile, Trackdir trackdir)
+ {
+ int cost = 0;
+ // if there is one-way signal in the opposite direction, then it is not our way
+ CPerfStart perf_cost(Yapf().m_perf_other_cost);
+ if (IsTileType(tile, MP_RAILWAY)) {
+ bool has_signal_against = HasSignalOnTrackdir(tile, ReverseTrackdir(trackdir));
+ bool has_signal_along = HasSignalOnTrackdir(tile, trackdir);
+ if (has_signal_against && !has_signal_along) {
+ // one-way signal in opposite direction
+ n.m_segment->flags_u.flags_s.m_end_of_line = true;
+ } else if (has_signal_along) {
+ SignalState sig_state = GetSignalStateByTrackdir(tile, trackdir);
+ if (sig_state != SIGNAL_STATE_RED) {
+ // green signal
+ n.flags_u.flags_s.m_last_signal_was_red = false;
+ } else {
+ // we have a red signal in our direction
+ // was it first signal which is two-way?
+ if (Yapf().TreatFirstRedTwoWaySignalAsEOL() && has_signal_against && n.m_num_signals_passed == 0) {
+ // yes, the first signal is two-way red signal => DEAD END
+ n.m_segment->flags_u.flags_s.m_end_of_line = true;
+ return -1;
+ }
+ SignalType sig_type = GetSignalType(tile);
+ n.m_last_red_signal_type = sig_type;
+ n.flags_u.flags_s.m_last_signal_was_red = true;
+
+ // look-ahead signal penalty
+ if (n.m_num_signals_passed < m_sig_look_ahead_costs.Size()) {
+ cost += m_sig_look_ahead_costs.Data()[n.m_num_signals_passed];
+ }
+
+ // special signal penalties
+ if (n.m_num_signals_passed == 0) {
+ switch (sig_type) {
+ case SIGTYPE_COMBO:
+ case SIGTYPE_EXIT: cost += Yapf().PfGetSettings().rail_firstred_exit_penalty; break; // first signal is red pre-signal-exit
+ case SIGTYPE_NORMAL:
+ case SIGTYPE_ENTRY: cost += Yapf().PfGetSettings().rail_firstred_penalty; break;
+ };
+ }
+ }
+ n.m_num_signals_passed++;
+ n.m_segment->m_last_signal_tile = tile;
+ n.m_segment->m_last_signal_td = trackdir;
+ }
+ }
+ return cost;
+ }
+
+public:
+ FORCEINLINE void SetMaxCost(int max_cost) {m_max_cost = max_cost;}
+
+ FORCEINLINE bool PfCalcCost(Node& n)
+ {
+ assert(!n.flags_u.flags_s.m_targed_seen);
+ CPerfStart perf_cost(Yapf().m_perf_cost);
+ int parent_cost = (n.m_parent != NULL) ? n.m_parent->m_cost : 0;
+ int first_tile_cost = 0;
+ int segment_cost = 0;
+ int extra_cost = 0;
+ Vehicle* v = Yapf().GetVehicle();
+
+ // start at n.m_key.m_tile / n.m_key.m_td and walk to the end of segment
+ TileIndex prev_tile = (n.m_parent != NULL) ? n.m_parent->GetLastTile() : INVALID_TILE;
+ Trackdir prev_trackdir = (n.m_parent != NULL) ? n.m_parent->GetLastTrackdir() : INVALID_TRACKDIR;
+ TileType prev_tile_type = (n.m_parent != NULL) ? GetTileType(n.m_parent->GetLastTile()) : MP_VOID;
+
+ TileIndex tile = n.m_key.m_tile;
+ Trackdir trackdir = n.m_key.m_td;
+ TileType tile_type = GetTileType(tile);
+
+ RailType rail_type = GetTileRailType(tile, trackdir);
+
+ bool target_seen = false;
+
+ while (true) {
+ segment_cost += Yapf().OneTileCost(tile, trackdir);
+ segment_cost += Yapf().CurveCost(prev_trackdir, trackdir);
+ segment_cost += Yapf().SlopeCost(tile, trackdir);
+ segment_cost += Yapf().SignalCost(n, tile, trackdir);
+ if (n.m_segment->flags_u.flags_s.m_end_of_line) {
+ break;
+ }
+
+ // finish if we have reached the destination
+ target_seen = Yapf().PfDetectDestination(n);
+ if (target_seen) {
+ break;
+ }
+
+ // finish on first station tile - segment should end here to avoid target skipping
+ // when cached segments are used
+ if (tile_type == MP_STATION && prev_tile_type != MP_STATION) {
+ break;
+ }
+
+ // finish also on waypoint - same workaround as for first station tile
+ if (tile_type == MP_RAILWAY && IsRailWaypoint(tile)) {
+ break;
+ }
+
+ // if there are no reachable trackdirs on the next tile, we have end of road
+ TrackFollower F(v, &Yapf().m_perf_ts_cost);
+ if (!F.Follow(tile, trackdir)) {
+ // we can't continue?
+ // n.m_segment->flags_u.flags_s.m_end_of_line = true;
+ break;
+ }
+
+ // if there are more trackdirs available & reachable, we are at the end of segment
+ if (KillFirstBit2x64(F.m_new_td_bits) != 0) {
+ break;
+ }
+
+ Trackdir new_td = (Trackdir)FindFirstBit2x64(F.m_new_td_bits);
+
+ {
+ // end segment if train is about to enter simple loop with no junctions
+ // so next time it should stop on the next if
+ if (segment_cost > s_max_segment_cost && IsTileType(F.m_new_tile, MP_RAILWAY))
+ break;
+
+ // stop if train is on simple loop with no junctions
+ if (F.m_new_tile == n.m_key.m_tile && new_td == n.m_key.m_td)
+ return false;
+ }
+
+ // if tail type changes, finish segment (cached segment can't contain more rail types)
+ {
+ RailType new_rail_type = GetTileRailType(F.m_new_tile, (Trackdir)FindFirstBit2x64(F.m_new_td_bits));
+ if (new_rail_type != rail_type) {
+ break;
+ }
+ rail_type = new_rail_type;
+ }
+
+ // move to the next tile
+ prev_tile = tile;
+ prev_trackdir = trackdir;
+ prev_tile_type = tile_type;
+
+ tile = F.m_new_tile;
+ trackdir = new_td;
+ tile_type = GetTileType(tile);
+
+ // reversing in depot penalty
+ if (tile == prev_tile) {
+ segment_cost += Yapf().PfGetSettings().rail_depot_reverse_penalty;
+ break;
+ }
+
+ // if we skipped some tunnel tiles, add their cost
+ segment_cost += YAPF_TILE_LENGTH * F.m_tunnel_tiles_skipped;
+
+ // add min/max speed penalties
+ int min_speed = 0;
+ int max_speed = F.GetSpeedLimit(&min_speed);
+ if (max_speed < v->max_speed)
+ segment_cost += YAPF_TILE_LENGTH * (v->max_speed - max_speed) / v->max_speed;
+ if (min_speed > v->max_speed)
+ segment_cost += YAPF_TILE_LENGTH * (min_speed - v->max_speed);
+
+ // finish if we already exceeded the maximum cost
+ if (m_max_cost > 0 && (parent_cost + first_tile_cost + segment_cost) > m_max_cost) {
+ return false;
+ }
+
+ if (first_tile_cost == 0) {
+ // we just have done first tile
+ first_tile_cost = segment_cost;
+ segment_cost = 0;
+
+ // look if we can reuse existing (cached) segment cost
+ if (n.m_segment->m_cost >= 0) {
+ // reuse the cached segment cost
+ break;
+ }
+ }
+ // segment cost was not filled yes, we have not cached it yet
+ n.SetLastTileTrackdir(tile, trackdir);
+
+ } // while (true)
+
+ if (first_tile_cost == 0) {
+ // we have just finished first tile
+ first_tile_cost = segment_cost;
+ segment_cost = 0;
+ }
+
+ // do we have cached segment cost?
+ if (n.m_segment->m_cost >= 0) {
+ // reuse the cached segment cost
+ segment_cost = n.m_segment->m_cost;
+ } else {
+ // save segment cost
+ n.m_segment->m_cost = segment_cost;
+
+ // save end of segment back to the node
+ n.SetLastTileTrackdir(tile, trackdir);
+ }
+
+ // special costs for the case we have reached our target
+ if (target_seen) {
+ n.flags_u.flags_s.m_targed_seen = true;
+ if (n.flags_u.flags_s.m_last_signal_was_red) {
+ if (n.m_last_red_signal_type == SIGTYPE_EXIT) {
+ // last signal was red pre-signal-exit
+ extra_cost += Yapf().PfGetSettings().rail_lastred_exit_penalty;
+ } else {
+ // last signal was red, but not exit
+ extra_cost += Yapf().PfGetSettings().rail_lastred_penalty;
+ }
+ }
+ }
+
+ // total node cost
+ n.m_cost = parent_cost + first_tile_cost + segment_cost + extra_cost;
+
+ return !n.m_segment->flags_u.flags_s.m_end_of_line;
+ }
+
+ FORCEINLINE bool CanUseGlobalCache(Node& n) const
+ {
+ return (n.m_parent != NULL)
+ && (n.m_parent->m_num_signals_passed >= m_sig_look_ahead_costs.Size());
+ }
+
+ FORCEINLINE void ConnectNodeToCachedData(Node& n, CachedData& ci)
+ {
+ n.m_segment = &ci;
+ if (n.m_segment->m_cost < 0) {
+ n.m_segment->m_last_tile = n.m_key.m_tile;
+ n.m_segment->m_last_td = n.m_key.m_td;
+ }
+ }
+
+};
+
+
+
+#endif /* YAPF_COSTRAIL_HPP */
diff --git a/yapf/yapf_destrail.hpp b/yapf/yapf_destrail.hpp
new file mode 100644
index 000000000..a0e3e922d
--- /dev/null
+++ b/yapf/yapf_destrail.hpp
@@ -0,0 +1,129 @@
+/* $Id$ */
+
+#ifndef YAPF_DESTRAIL_HPP
+#define YAPF_DESTRAIL_HPP
+
+class CYapfDestinationRailBase
+{
+protected:
+ RailTypeMask m_compatible_railtypes;
+
+public:
+ void SetDestination(Vehicle* v)
+ {
+ m_compatible_railtypes = v->u.rail.compatible_railtypes;
+ }
+
+ bool IsCompatibleRailType(RailType rt)
+ {
+ return HASBIT(m_compatible_railtypes, rt);
+ }
+};
+
+template <class Types>
+class CYapfDestinationAnyDepotRailT
+ : public CYapfDestinationRailBase
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+ Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+ FORCEINLINE bool PfDetectDestination(Node& n)
+ {
+ bool bDest = IsTileDepotType(n.GetLastTile(), TRANSPORT_RAIL);
+ return bDest;
+ }
+
+ FORCEINLINE bool PfCalcEstimate(Node& n)
+ {
+ n.m_estimate = n.m_cost;
+ return true;
+ }
+};
+
+template <class Types>
+class CYapfDestinationTileOrStationRailT
+ : public CYapfDestinationRailBase
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+protected:
+ TileIndex m_destTile;
+ TrackdirBits m_destTrackdirs;
+ StationID m_dest_station_id;
+
+ Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+ static TileIndex CalcStationCenterTile(StationID station)
+ {
+ const Station* st = GetStation(station);
+
+ uint x = TileX(st->train_tile) + st->trainst_w / 2;
+ uint y = TileY(st->train_tile) + st->trainst_h / 2;
+ // return the tile of our target coordinates
+ return TileXY(x, y);
+ }
+
+public:
+ void SetDestination(Vehicle* v)
+ {
+ if (v->current_order.type == OT_GOTO_STATION) {
+ m_destTile = CalcStationCenterTile(v->current_order.station);
+ m_dest_station_id = v->current_order.station;
+ m_destTrackdirs = INVALID_TRACKDIR_BIT;
+ } else {
+ m_destTile = v->dest_tile;
+ m_dest_station_id = INVALID_STATION;
+ m_destTrackdirs = (TrackdirBits)(GetTileTrackStatus(v->dest_tile, TRANSPORT_RAIL) & TRACKDIR_BIT_MASK);
+ }
+ CYapfDestinationRailBase::SetDestination(v);
+ }
+
+ FORCEINLINE bool PfDetectDestination(Node& n)
+ {
+ bool bDest;
+ if (m_dest_station_id != INVALID_STATION) {
+ bDest = IsRailwayStationTile(n.GetLastTile())
+ && (GetStationIndex(n.GetLastTile()) == m_dest_station_id)
+ && (GetRailStationTrack(n.GetLastTile()) == TrackdirToTrack(n.GetLastTrackdir()));
+ } else {
+ bDest = (n.GetLastTile() == m_destTile)
+ && ((m_destTrackdirs & TrackdirToTrackdirBits(n.GetLastTrackdir())) != TRACKDIR_BIT_NONE);
+ }
+ return bDest;
+ }
+
+ FORCEINLINE bool PfCalcEstimate(Node& n)
+ {
+ static int dg_dir_to_x_offs[] = {-1, 0, 1, 0};
+ static int dg_dir_to_y_offs[] = {0, 1, 0, -1};
+ if (PfDetectDestination(n)) {
+ n.m_estimate = n.m_cost;
+ return true;
+ }
+
+ TileIndex tile = n.GetLastTile();
+ DiagDirection exitdir = TrackdirToExitdir(n.GetLastTrackdir());
+ int x1 = 2 * TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
+ int y1 = 2 * TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
+ int x2 = 2 * TileX(m_destTile);
+ int y2 = 2 * TileY(m_destTile);
+ int dx = abs(x1 - x2);
+ int dy = abs(y1 - y2);
+ int dmin = min(dx, dy);
+ int dxy = abs(dx - dy);
+ int d = dmin * YAPF_TILE_CORNER_LENGTH + (dxy - 1) * (YAPF_TILE_LENGTH / 2);
+ n.m_estimate = n.m_cost + d;
+ assert(n.m_estimate >= n.m_parent->m_estimate);
+ return true;
+ }
+};
+
+
+#endif /* YAPF_DESTRAIL_HPP */
diff --git a/yapf/yapf_node.hpp b/yapf/yapf_node.hpp
new file mode 100644
index 000000000..48206ee06
--- /dev/null
+++ b/yapf/yapf_node.hpp
@@ -0,0 +1,77 @@
+/* $Id$ */
+
+#ifndef YAPF_NODE_HPP
+#define YAPF_NODE_HPP
+
+/** Yapf Node Key that evaluates hash from (and compares) tile & exit dir. */
+struct CYapfNodeKeyExitDir {
+ TileIndex m_tile;
+ Trackdir m_td;
+ DiagDirection m_exitdir;
+
+ FORCEINLINE void Set(TileIndex tile, Trackdir td)
+ {
+ m_tile = tile;
+ m_td = td;
+ m_exitdir = (m_td == INVALID_TRACKDIR) ? INVALID_DIAGDIR : TrackdirToExitdir(m_td);
+ }
+
+ FORCEINLINE int CalcHash() const {return m_exitdir | (m_tile << 2);}
+ FORCEINLINE bool operator == (const CYapfNodeKeyExitDir& other) const {return (m_tile == other.m_tile) && (m_exitdir == other.m_exitdir);}
+};
+
+struct CYapfNodeKeyTrackDir : public CYapfNodeKeyExitDir
+{
+ FORCEINLINE int CalcHash() const {return m_td | (m_tile << 4);}
+ FORCEINLINE bool operator == (const CYapfNodeKeyTrackDir& other) const {return (m_tile == other.m_tile) && (m_td == other.m_td);}
+};
+
+/** Yapf Node base */
+template <class Tkey_, class Tnode>
+struct CYapfNodeT {
+ typedef Tkey_ Key;
+ typedef Tnode Node;
+
+ Tkey_ m_key;
+ Node *m_hash_next;
+ Node *m_parent;
+ int m_cost;
+ int m_estimate;
+
+ FORCEINLINE void Set(Node *parent, TileIndex tile, Trackdir td)
+ {
+ m_key.Set(tile, td);
+ m_hash_next = NULL;
+ m_parent = parent;
+ m_cost = 0;
+ m_estimate = 0;
+ }
+
+ FORCEINLINE Node* GetHashNext() {return m_hash_next;}
+ FORCEINLINE void SetHashNext(Node *pNext) {m_hash_next = pNext;}
+ FORCEINLINE TileIndex GetTile() const {return m_key.m_tile;}
+ FORCEINLINE Trackdir GetTrackdir() const {return m_key.m_td;}
+ FORCEINLINE const Tkey_& GetKey() const {return m_key;}
+ FORCEINLINE int GetCost() {return m_cost;}
+ FORCEINLINE int GetCostEstimate() {return m_estimate;}
+ FORCEINLINE bool operator < (const Node& other) const {return m_estimate < other.m_estimate;}
+};
+
+/** Yapf Node for ships */
+template <class Tkey_>
+struct CYapfShipNodeT
+ : CYapfNodeT<Tkey_, CYapfShipNodeT<Tkey_> >
+{
+
+};
+
+// now define two major node types (that differ by key type)
+typedef CYapfShipNodeT<CYapfNodeKeyExitDir> CYapfShipNodeExitDir;
+typedef CYapfShipNodeT<CYapfNodeKeyTrackDir> CYapfShipNodeTrackDir;
+
+// Default NodeList types
+typedef CNodeList_HashTableT<CYapfShipNodeExitDir , 14, 16> CShipNodeListExitDir;
+typedef CNodeList_HashTableT<CYapfShipNodeTrackDir, 16, 20> CShipNodeListTrackDir;
+
+
+#endif /* YAPF_NODE_HPP */
diff --git a/yapf/yapf_node_rail.hpp b/yapf/yapf_node_rail.hpp
new file mode 100644
index 000000000..2d566ab4f
--- /dev/null
+++ b/yapf/yapf_node_rail.hpp
@@ -0,0 +1,111 @@
+/* $Id$ */
+
+#ifndef YAPF_NODE_RAIL_HPP
+#define YAPF_NODE_RAIL_HPP
+
+/** key for cached segment cost for rail YAPF */
+struct CYapfRailSegmentKey
+{
+ uint32 m_value;
+
+ FORCEINLINE CYapfRailSegmentKey(const CYapfRailSegmentKey& src) : m_value(src.m_value) {}
+ FORCEINLINE CYapfRailSegmentKey(const CYapfNodeKeyExitDir& node_key) {Set(node_key);}
+
+ FORCEINLINE void Set(const CYapfRailSegmentKey& src) {m_value = src.m_value;}
+ FORCEINLINE void Set(const CYapfNodeKeyExitDir& node_key) {m_value = (((int)node_key.m_tile) << 2) | node_key.m_exitdir;}
+
+ FORCEINLINE int32 CalcHash() const {return m_value;}
+ FORCEINLINE TileIndex GetTile() const {return (TileIndex)(m_value >> 2);}
+ FORCEINLINE DiagDirection GetExitDir() const {return (DiagDirection)(m_value & 3);}
+ FORCEINLINE bool operator == (const CYapfRailSegmentKey& other) const {return m_value == other.m_value;}
+};
+
+/** cached segment cost for rail YAPF */
+struct CYapfRailSegment
+{
+ typedef CYapfRailSegmentKey Key;
+
+ CYapfRailSegmentKey m_key;
+ TileIndex m_last_tile;
+ Trackdir m_last_td;
+ int m_cost;
+ TileIndex m_last_signal_tile;
+ Trackdir m_last_signal_td;
+ CYapfRailSegment* m_hash_next;
+ union {
+ byte m_flags;
+ struct {
+ bool m_end_of_line : 1;
+ } flags_s;
+ } flags_u;
+ byte m_reserve[3];
+
+ FORCEINLINE CYapfRailSegment(const CYapfRailSegmentKey& key)
+ : m_key(key)
+ , m_last_tile(INVALID_TILE)
+ , m_last_td(INVALID_TRACKDIR)
+ , m_cost(-1)
+ , m_last_signal_tile(INVALID_TILE)
+ , m_last_signal_td(INVALID_TRACKDIR)
+ , m_hash_next(NULL)
+ {
+ flags_u.m_flags = 0;
+ }
+
+ FORCEINLINE const Key& GetKey() const {return m_key;}
+ FORCEINLINE TileIndex GetTile() const {return m_key.GetTile();}
+ FORCEINLINE DiagDirection GetExitDir() const {return m_key.GetExitDir();}
+ FORCEINLINE CYapfRailSegment* GetHashNext() {return m_hash_next;}
+ FORCEINLINE void SetHashNext(CYapfRailSegment* next) {m_hash_next = next;}
+};
+
+/** Yapf Node for rail YAPF */
+template <class Tkey_>
+struct CYapfRailNodeT
+ : CYapfNodeT<Tkey_, CYapfRailNodeT<Tkey_> >
+{
+ typedef CYapfNodeT<Tkey_, CYapfRailNodeT<Tkey_> > base;
+ typedef CYapfRailSegment CachedData;
+
+ CYapfRailSegment *m_segment;
+ uint16 m_num_signals_passed;
+ union {
+ byte m_inherited_flags;
+ struct {
+ bool m_targed_seen : 1;
+ bool m_last_signal_was_red : 1;
+ } flags_s;
+ } flags_u;
+ SignalType m_last_red_signal_type;
+
+ FORCEINLINE void Set(CYapfRailNodeT* parent, TileIndex tile, Trackdir td)
+ {
+ base::Set(parent, tile, td);
+ m_segment = NULL;
+ if (parent == NULL) {
+ m_num_signals_passed = 0;
+ flags_u.m_inherited_flags = 0;
+ m_last_red_signal_type = SIGTYPE_NORMAL;
+ } else {
+ m_num_signals_passed = parent->m_num_signals_passed;
+ flags_u.m_inherited_flags = parent->flags_u.m_inherited_flags;
+ m_last_red_signal_type = parent->m_last_red_signal_type;
+ }
+ }
+
+ FORCEINLINE TileIndex GetLastTile() const {assert(m_segment != NULL); return m_segment->m_last_tile;}
+ FORCEINLINE Trackdir GetLastTrackdir() const {assert(m_segment != NULL); return m_segment->m_last_td;}
+ FORCEINLINE void SetLastTileTrackdir(TileIndex tile, Trackdir td) {assert(m_segment != NULL); m_segment->m_last_tile = tile; m_segment->m_last_td = td;}
+};
+
+// now define two major node types (that differ by key type)
+typedef CYapfRailNodeT<CYapfNodeKeyExitDir> CYapfRailNodeExitDir;
+typedef CYapfRailNodeT<CYapfNodeKeyTrackDir> CYapfRailNodeTrackDir;
+
+// Default NodeList types
+typedef CNodeList_HashTableT<CYapfRailNodeExitDir , 10, 12> CRailNodeListExitDir;
+typedef CNodeList_HashTableT<CYapfRailNodeTrackDir, 12, 16> CRailNodeListTrackDir;
+
+
+
+#endif /* YAPF_NODE_RAIL_HPP */
diff --git a/yapf/yapf_node_road.hpp b/yapf/yapf_node_road.hpp
new file mode 100644
index 000000000..8a6888565
--- /dev/null
+++ b/yapf/yapf_node_road.hpp
@@ -0,0 +1,36 @@
+/* $Id$ */
+
+#ifndef YAPF_NODE_ROAD_HPP
+#define YAPF_NODE_ROAD_HPP
+
+
+
+/** Yapf Node for road YAPF */
+template <class Tkey_>
+struct CYapfRoadNodeT
+ : CYapfNodeT<Tkey_, CYapfRoadNodeT<Tkey_> >
+{
+ typedef CYapfNodeT<Tkey_, CYapfRoadNodeT<Tkey_> > base;
+
+ TileIndex m_segment_last_tile;
+ Trackdir m_segment_last_td;
+
+ void Set(CYapfRoadNodeT* parent, TileIndex tile, Trackdir td)
+ {
+ base::Set(parent, tile, td);
+ m_segment_last_tile = tile;
+ m_segment_last_td = td;
+ }
+};
+
+// now define two major node types (that differ by key type)
+typedef CYapfRoadNodeT<CYapfNodeKeyExitDir> CYapfRoadNodeExitDir;
+typedef CYapfRoadNodeT<CYapfNodeKeyTrackDir> CYapfRoadNodeTrackDir;
+
+// Default NodeList types
+typedef CNodeList_HashTableT<CYapfRoadNodeExitDir , 8, 12> CRoadNodeListExitDir;
+typedef CNodeList_HashTableT<CYapfRoadNodeTrackDir, 10, 14> CRoadNodeListTrackDir;
+
+
+
+#endif /* YAPF_NODE_ROAD_HPP */
diff --git a/yapf/yapf_rail.cpp b/yapf/yapf_rail.cpp
new file mode 100644
index 000000000..08ee143ed
--- /dev/null
+++ b/yapf/yapf_rail.cpp
@@ -0,0 +1,265 @@
+/* $Id$ */
+
+#include "../stdafx.h"
+
+#include "yapf.hpp"
+#include "yapf_node_rail.hpp"
+#include "yapf_costrail.hpp"
+#include "yapf_destrail.hpp"
+
+int _total_pf_time_us = 0;
+
+
+
+
+
+template <class Types>
+class CYapfFollowAnyDepotRailT
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::TrackFollower TrackFollower;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+protected:
+ FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+public:
+ inline void PfFollowNode(Node& old_node)
+ {
+ TrackFollower F(Yapf().GetVehicle());
+ if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir()))
+ Yapf().AddMultipleNodes(&old_node, F.m_new_tile, F.m_new_td_bits);
+ }
+
+ FORCEINLINE char TransportTypeChar() const {return 't';}
+
+ static bool stFindNearestDepotTwoWay(Vehicle *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed)
+ {
+ Tpf pf;
+ return pf.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_distance, reverse_penalty, depot_tile, reversed);
+ }
+
+ FORCEINLINE bool FindNearestDepotTwoWay(Vehicle *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed)
+ {
+ // set origin and destination nodes
+ Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty, true);
+ Yapf().SetDestination(v);
+ Yapf().SetMaxCost(10 * max_distance);
+
+ // find the best path
+ bool bFound = Yapf().FindPath(v);
+ if (!bFound) return false;
+
+ // some path found
+ // get found depot tile
+ Node& n = Yapf().GetBestNode();
+ *depot_tile = n.GetLastTile();
+
+ // walk through the path back to the origin
+ Node* pNode = &n;
+ while (pNode->m_parent != NULL) {
+ pNode = pNode->m_parent;
+ }
+
+ // if the origin node is our front vehicle tile/Trackdir then we didn't reverse
+ // but we can also look at the cost (== 0 -> not reversed, == reverse_penalty -> reversed)
+ *reversed = (pNode->m_cost != 0);
+
+ return true;
+ }
+};
+
+template <class Types>
+class CYapfFollowRailT
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::TrackFollower TrackFollower;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+protected:
+ FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+public:
+ inline void PfFollowNode(Node& old_node)
+ {
+ TrackFollower F(Yapf().GetVehicle());
+ if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir()))
+ Yapf().AddMultipleNodes(&old_node, F.m_new_tile, F.m_new_td_bits);
+ }
+
+ FORCEINLINE char TransportTypeChar() const {return 't';}
+
+ static Trackdir stChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs)
+ {
+ // create pathfinder instance
+ Tpf pf;
+ return pf.ChooseRailTrack(v, tile, enterdir, trackdirs);
+ }
+
+ FORCEINLINE Trackdir ChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs)
+ {
+ // set origin and destination nodes
+ Yapf().SetOrigin(v->tile, GetVehicleTrackdir(v), INVALID_TILE, INVALID_TRACKDIR, 1, true);
+ Yapf().SetDestination(v);
+
+ // find the best path
+ Yapf().FindPath(v);
+
+ // if path not found - return INVALID_TRACKDIR
+ Trackdir next_trackdir = INVALID_TRACKDIR;
+ Node* pNode = &Yapf().GetBestNode();
+ if (pNode != NULL) {
+ // path was found or at least suggested
+ // walk through the path back to the origin
+ Node* pPrev = NULL;
+ while (pNode->m_parent != NULL) {
+ pPrev = pNode;
+ pNode = pNode->m_parent;
+ }
+ // return trackdir from the best origin node (one of start nodes)
+ Node& best_next_node = *pPrev;
+ assert(best_next_node.GetTile() == tile);
+ next_trackdir = best_next_node.GetTrackdir();
+ }
+ return next_trackdir;
+ }
+
+ static bool stCheckReverseTrain(Vehicle* v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2)
+ {
+ Tpf pf;
+ return pf.CheckReverseTrain(v, t1, td1, t2, td2);
+ }
+
+ FORCEINLINE bool CheckReverseTrain(Vehicle* v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2)
+ {
+ // create pathfinder instance
+ // set origin and destination nodes
+ Yapf().SetOrigin(t1, td1, t2, td2, 1, false);
+ Yapf().SetDestination(v);
+
+ // find the best path
+ bool bFound = Yapf().FindPath(v);
+
+ if (!bFound) return false;
+
+ // path was found
+ // walk through the path back to the origin
+ Node* pNode = &Yapf().GetBestNode();
+ while (pNode->m_parent != NULL) {
+ pNode = pNode->m_parent;
+ }
+
+ // check if it was reversed origin
+ Node& best_org_node = *pNode;
+ bool reversed = (best_org_node.m_cost != 0);
+ return reversed;
+ }
+};
+
+template <class Tpf_, class Ttrack_follower, class Tnode_list, template <class Types> class TdestinationT, template <class Types> class TfollowT>
+struct CYapfRail_TypesT
+{
+ typedef CYapfRail_TypesT<Tpf_, Ttrack_follower, Tnode_list, TdestinationT, TfollowT> Types;
+
+ typedef Tpf_ Tpf;
+ typedef Ttrack_follower TrackFollower;
+ typedef Tnode_list NodeList;
+ typedef CYapfBaseT<Types> PfBase;
+ typedef TfollowT<Types> PfFollow;
+ typedef CYapfOriginTileTwoWayT<Types> PfOrigin;
+ typedef TdestinationT<Types> PfDestination;
+ typedef CYapfSegmentCostCacheGlobalT<Types> PfCache;
+ typedef CYapfCostRailT<Types> PfCost;
+};
+
+struct CYapfRail1 : CYapfT<CYapfRail_TypesT<CYapfRail1 , CFollowTrackRail , CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
+struct CYapfRail2 : CYapfT<CYapfRail_TypesT<CYapfRail2 , CFollowTrackRail , CRailNodeListExitDir , CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
+struct CYapfRail3 : CYapfT<CYapfRail_TypesT<CYapfRail3 , CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
+
+struct CYapfAnyDepotRail1 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail1, CFollowTrackRail , CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {};
+struct CYapfAnyDepotRail2 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail2, CFollowTrackRail , CRailNodeListExitDir , CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {};
+struct CYapfAnyDepotRail3 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail3, CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {};
+
+
+Trackdir YapfChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs)
+{
+ // default is YAPF type 2
+ typedef Trackdir (*PfnChooseRailTrack)(Vehicle*, TileIndex, DiagDirection, TrackdirBits);
+ PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail2::stChooseRailTrack;
+
+ // check if non-default YAPF type needed
+ if (_patches.forbid_90_deg)
+ pfnChooseRailTrack = &CYapfRail3::stChooseRailTrack; // Trackdir, forbid 90-deg
+ else if (_patches.yapf.disable_node_optimization)
+ pfnChooseRailTrack = &CYapfRail1::stChooseRailTrack; // Trackdir, allow 90-deg
+
+ Trackdir td_ret = pfnChooseRailTrack(v, tile, enterdir, trackdirs);
+
+ return td_ret;
+}
+
+bool YapfCheckReverseTrain(Vehicle* v)
+{
+ // tile where the engine is
+ TileIndex tile = v->tile;
+ // tile where we have last wagon
+ Vehicle* last_veh = GetLastVehicleInChain(v);
+ // if we are in tunnel then give up
+ if (v->u.rail.track == 0x40 || last_veh->u.rail.track == 0x40) return false;
+ // get trackdirs of both ends
+ Trackdir td = GetVehicleTrackdir(v);
+ Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));
+
+
+ typedef bool (*PfnCheckReverseTrain)(Vehicle*, TileIndex, Trackdir, TileIndex, Trackdir);
+ PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail2::stCheckReverseTrain;
+
+ // check if non-default YAPF type needed
+ if (_patches.forbid_90_deg)
+ pfnCheckReverseTrain = &CYapfRail3::stCheckReverseTrain; // Trackdir, forbid 90-deg
+ else if (_patches.yapf.disable_node_optimization)
+ pfnCheckReverseTrain = &CYapfRail1::stCheckReverseTrain; // Trackdir, allow 90-deg
+
+ bool reverse = pfnCheckReverseTrain(v, tile, td, last_veh->tile, td_rev);
+
+ return reverse;
+}
+
+bool YapfFindNearestRailDepotTwoWay(Vehicle *v, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed)
+{
+ *depot_tile = INVALID_TILE;
+ *reversed = false;
+
+ Vehicle* last_veh = GetLastVehicleInChain(v);
+
+ bool first_in_tunnel = v->u.rail.track == 0x40;
+ bool last_in_tunnel = last_veh->u.rail.track == 0x40;
+
+ // tile where the engine and last wagon are
+ TileIndex tile = first_in_tunnel ? INVALID_TILE : v->tile;
+ TileIndex last_tile = last_in_tunnel ? INVALID_TILE : last_veh->tile;
+
+ // their trackdirs
+ Trackdir td = first_in_tunnel ? INVALID_TRACKDIR : GetVehicleTrackdir(v);
+ Trackdir td_rev = last_in_tunnel ? INVALID_TRACKDIR : ReverseTrackdir(GetVehicleTrackdir(last_veh));
+
+ typedef bool (*PfnFindNearestDepotTwoWay)(Vehicle*, TileIndex, Trackdir, TileIndex, Trackdir, int, int, TileIndex*, bool*);
+ PfnFindNearestDepotTwoWay pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail2::stFindNearestDepotTwoWay;
+
+ // check if non-default YAPF type needed
+ if (_patches.forbid_90_deg)
+ pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail3::stFindNearestDepotTwoWay; // Trackdir, forbid 90-deg
+ else if (_patches.yapf.disable_node_optimization)
+ pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail1::stFindNearestDepotTwoWay; // Trackdir, allow 90-deg
+
+ bool ret = pfnFindNearestDepotTwoWay(v, tile, td, last_tile, td_rev, max_distance, reverse_penalty, depot_tile, reversed);
+ return ret;
+}
+
+int CSegmentCostCacheBase::s_rail_change_counter = 0;
+
+void YapfNotifyTrackLayoutChange(TileIndex tile, Track track) {CSegmentCostCacheBase::NotifyTrackLayoutChange(tile, track);}
diff --git a/yapf/yapf_road.cpp b/yapf/yapf_road.cpp
new file mode 100644
index 000000000..dd3529aff
--- /dev/null
+++ b/yapf/yapf_road.cpp
@@ -0,0 +1,353 @@
+/* $Id$ */
+
+#include "../stdafx.h"
+
+#include "yapf.hpp"
+#include "yapf_node_road.hpp"
+
+
+template <class Types>
+class CYapfCostRoadT
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::TrackFollower TrackFollower;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+protected:
+ Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+ int SlopeCost(TileIndex tile, TileIndex next_tile, Trackdir trackdir)
+ {
+ // height of the center of the current tile
+ int x1 = TileX(tile) * TILE_SIZE;
+ int y1 = TileY(tile) * TILE_SIZE;
+ int z1 = GetSlopeZ(x1 + TILE_HEIGHT, y1 + TILE_HEIGHT);
+
+ // height of the center of the next tile
+ int x2 = TileX(next_tile) * TILE_SIZE;
+ int y2 = TileY(next_tile) * TILE_SIZE;
+ int z2 = GetSlopeZ(x2 + TILE_HEIGHT, y2 + TILE_HEIGHT);
+
+ if (z2 - z1 > 1) {
+ /* Slope up */
+ return Yapf().PfGetSettings().rail_slope_penalty;
+ }
+ return 0;
+ }
+
+ /** return one tile cost */
+ FORCEINLINE int OneTileCost(TileIndex tile, Trackdir trackdir)
+ {
+ int cost = 0;
+ // set base cost
+ if (IsDiagonalTrackdir(trackdir)) {
+ cost += 10;
+ switch (GetTileType(tile)) {
+ case MP_STREET:
+ /* Increase the cost for level crossings */
+ if (IsLevelCrossing(tile))
+ cost += Yapf().PfGetSettings().rail_crossing_penalty;
+ break;
+
+ default:
+ break;
+ }
+ } else {
+ // non-diagonal trackdir
+ cost = 7;
+ }
+ return cost;
+ }
+
+public:
+ FORCEINLINE bool PfCalcCost(Node& n)
+ {
+ int segment_cost = 0;
+ // start at n.m_key.m_tile / n.m_key.m_td and walk to the end of segment
+ TileIndex tile = n.m_key.m_tile;
+ Trackdir trackdir = n.m_key.m_td;
+ while (true) {
+ // base tile cost depending on distance between edges
+ segment_cost += Yapf().OneTileCost(tile, trackdir);
+
+ // if there are no reachable trackdirs n new tile, we have end of road
+ TrackFollower F;
+ if (!F.Follow(tile, trackdir)) break;
+
+ // if there are more trackdirs available & reachable, we are at the end of segment
+ if (KillFirstBit2x64(F.m_new_td_bits) != 0) break;
+
+ Trackdir new_td = (Trackdir)FindFirstBit2x64(F.m_new_td_bits);
+
+ // stop if RV is on simple loop with no junctions
+ if (F.m_new_tile == n.m_key.m_tile && new_td == n.m_key.m_td) return false;
+
+ // if we skipped some tunnel tiles, add their cost
+ segment_cost += 10 * F.m_tunnel_tiles_skipped;
+
+ // add hilly terrain penalty
+ segment_cost += Yapf().SlopeCost(tile, F.m_new_tile, trackdir);
+
+ // add min/max speed penalties
+ int min_speed = 0;
+ int max_speed = F.GetSpeedLimit(&min_speed);
+ Vehicle* v = Yapf().GetVehicle();
+ if (max_speed < v->max_speed) segment_cost += 1 * (v->max_speed - max_speed);
+ if (min_speed > v->max_speed) segment_cost += 10 * (min_speed - v->max_speed);
+
+ // move to the next tile
+ tile = F.m_new_tile;
+ trackdir = new_td;
+ };
+
+ // save end of segment back to the node
+ n.m_segment_last_tile = tile;
+ n.m_segment_last_td = trackdir;
+
+ // save also tile cost
+ int parent_cost = (n.m_parent != NULL) ? n.m_parent->m_cost : 0;
+ n.m_cost = parent_cost + segment_cost;
+ return true;
+ }
+};
+
+
+template <class Types>
+class CYapfDestinationAnyDepotRoadT
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::TrackFollower TrackFollower;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+ Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+ FORCEINLINE bool PfDetectDestination(Node& n)
+ {
+ bool bDest = IsTileDepotType(n.m_segment_last_tile, TRANSPORT_ROAD);
+ return bDest;
+ }
+
+ FORCEINLINE bool PfCalcEstimate(Node& n)
+ {
+ n.m_estimate = n.m_cost;
+ return true;
+ }
+};
+
+
+template <class Types>
+class CYapfDestinationTileRoadT
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::TrackFollower TrackFollower;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+protected:
+ TileIndex m_destTile;
+ TrackdirBits m_destTrackdirs;
+
+public:
+ void SetDestination(TileIndex tile, TrackdirBits trackdirs)
+ {
+ m_destTile = tile;
+ m_destTrackdirs = trackdirs;
+ }
+
+protected:
+ Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+public:
+ FORCEINLINE bool PfDetectDestination(Node& n)
+ {
+ bool bDest = (n.m_segment_last_tile == m_destTile) && ((m_destTrackdirs & TrackdirToTrackdirBits(n.m_segment_last_td)) != TRACKDIR_BIT_NONE);
+ return bDest;
+ }
+
+ inline bool PfCalcEstimate(Node& n)
+ {
+ static int dg_dir_to_x_offs[] = {-1, 0, 1, 0};
+ static int dg_dir_to_y_offs[] = {0, 1, 0, -1};
+ if (PfDetectDestination(n)) {
+ n.m_estimate = n.m_cost;
+ return true;
+ }
+
+ TileIndex tile = n.m_segment_last_tile;
+ DiagDirection exitdir = TrackdirToExitdir(n.m_segment_last_td);
+ int x1 = 2 * TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
+ int y1 = 2 * TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
+ int x2 = 2 * TileX(m_destTile);
+ int y2 = 2 * TileY(m_destTile);
+ int dx = abs(x1 - x2);
+ int dy = abs(y1 - y2);
+ int dmin = min(dx, dy);
+ int dxy = abs(dx - dy);
+ int d = dmin * 7 + (dxy - 1) * 5;
+ n.m_estimate = n.m_cost + d;
+ assert(n.m_estimate >= n.m_parent->m_estimate);
+ return true;
+ }
+};
+
+
+
+template <class Types>
+class CYapfFollowRoadT
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::TrackFollower TrackFollower;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+protected:
+ FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+public:
+
+ inline void PfFollowNode(Node& old_node)
+ {
+ TrackFollower F;
+ if (F.Follow(old_node.m_segment_last_tile, old_node.m_segment_last_td))
+ Yapf().AddMultipleNodes(&old_node, F.m_new_tile, F.m_new_td_bits);
+ }
+
+ FORCEINLINE char TransportTypeChar() const {return 'r';}
+
+ static Trackdir stChooseRoadTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir)
+ {
+ Tpf pf;
+ return pf.ChooseRoadTrack(v, tile, enterdir);
+ }
+
+ FORCEINLINE Trackdir ChooseRoadTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir)
+ {
+ // handle special case - when next tile is destination tile
+ if (tile == v->dest_tile) {
+ // choose diagonal trackdir reachable from enterdir
+ return (Trackdir)DiagdirToDiagTrackdir(enterdir);
+ }
+ // our source tile will be the next vehicle tile (should be the given one)
+ TileIndex src_tile = tile;
+ // get available trackdirs on the start tile
+ uint ts = GetTileTrackStatus(tile, TRANSPORT_ROAD);
+ TrackdirBits src_trackdirs = (TrackdirBits)(ts & TRACKDIR_BIT_MASK);
+ // select reachable trackdirs only
+ src_trackdirs &= DiagdirReachesTrackdirs(enterdir);
+
+ // get available trackdirs on the destination tile
+ TileIndex dest_tile = v->dest_tile;
+ uint dest_ts = GetTileTrackStatus(dest_tile, TRANSPORT_ROAD);
+ TrackdirBits dest_trackdirs = (TrackdirBits)(dest_ts & TRACKDIR_BIT_MASK);
+
+ // set origin and destination nodes
+ Yapf().SetOrigin(src_tile, src_trackdirs);
+ Yapf().SetDestination(dest_tile, dest_trackdirs);
+
+ // find the best path
+ Yapf().FindPath(v);
+
+ // if path not found - return INVALID_TRACKDIR
+ Trackdir next_trackdir = INVALID_TRACKDIR;
+ Node* pNode = &Yapf().GetBestNode();
+ if (pNode != NULL) {
+ // path was found or at least suggested
+ // walk through the path back to its origin
+ while (pNode->m_parent != NULL) {
+ pNode = pNode->m_parent;
+ }
+ // return trackdir from the best origin node (one of start nodes)
+ Node& best_next_node = *pNode;
+ assert(best_next_node.GetTile() == tile);
+ next_trackdir = best_next_node.GetTrackdir();
+ }
+ return next_trackdir;
+ }
+
+ static Depot* stFindNearestDepot(Vehicle* v, TileIndex tile, Trackdir td)
+ {
+ Tpf pf;
+ return pf.FindNearestDepot(v, tile, td);
+ }
+
+ FORCEINLINE Depot* FindNearestDepot(Vehicle* v, TileIndex tile, Trackdir td)
+ {
+ // set origin and destination nodes
+ Yapf().SetOrigin(tile, TrackdirToTrackdirBits(td));
+
+ // find the best path
+ bool bFound = Yapf().FindPath(v);
+ if (!bFound) return false;
+
+ // some path found
+ // get found depot tile
+ Node& n = Yapf().GetBestNode();
+ TileIndex depot_tile = n.m_segment_last_tile;
+ assert(IsTileDepotType(depot_tile, TRANSPORT_ROAD));
+ Depot* ret = GetDepotByTile(depot_tile);
+ return ret;
+ }
+};
+
+template <class Tpf_, class Tnode_list, template <class Types> class Tdestination>
+struct CYapfRoad_TypesT
+{
+ typedef CYapfRoad_TypesT<Tpf_, Tnode_list, Tdestination> Types;
+
+ typedef Tpf_ Tpf;
+ typedef CFollowTrackRoad TrackFollower;
+ typedef Tnode_list NodeList;
+ typedef CYapfBaseT<Types> PfBase;
+ typedef CYapfFollowRoadT<Types> PfFollow;
+ typedef CYapfOriginTileT<Types> PfOrigin;
+ typedef Tdestination<Types> PfDestination;
+ typedef CYapfSegmentCostCacheNoneT<Types> PfCache;
+ typedef CYapfCostRoadT<Types> PfCost;
+};
+
+struct CYapfRoad1 : CYapfT<CYapfRoad_TypesT<CYapfRoad1 , CRoadNodeListTrackDir, CYapfDestinationTileRoadT > > {};
+struct CYapfRoad2 : CYapfT<CYapfRoad_TypesT<CYapfRoad2 , CRoadNodeListExitDir , CYapfDestinationTileRoadT > > {};
+
+struct CYapfRoadAnyDepot1 : CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot1, CRoadNodeListTrackDir, CYapfDestinationAnyDepotRoadT> > {};
+struct CYapfRoadAnyDepot2 : CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot2, CRoadNodeListExitDir , CYapfDestinationAnyDepotRoadT> > {};
+
+
+Trackdir YapfChooseRoadTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir)
+{
+ // default is YAPF type 2
+ typedef Trackdir (*PfnChooseRoadTrack)(Vehicle*, TileIndex, DiagDirection);
+ PfnChooseRoadTrack pfnChooseRoadTrack = &CYapfRoad2::stChooseRoadTrack; // default: ExitDir, allow 90-deg
+
+ // check if non-default YAPF type should be used
+ if (_patches.yapf.disable_node_optimization)
+ pfnChooseRoadTrack = &CYapfRoad1::stChooseRoadTrack; // Trackdir, allow 90-deg
+
+ Trackdir td_ret = pfnChooseRoadTrack(v, tile, enterdir);
+ return td_ret;
+}
+
+Depot* YapfFindNearestRoadDepot(const Vehicle *v)
+{
+ TileIndex tile = v->tile;
+ if (v->u.road.state == 255) tile = GetVehicleOutOfTunnelTile(v);
+ Trackdir trackdir = GetVehicleTrackdir(v);
+ if ((GetTileTrackStatus(tile, TRANSPORT_ROAD) & TrackdirToTrackdirBits(trackdir)) == 0)
+ return NULL;
+
+ // default is YAPF type 2
+ typedef Depot* (*PfnFindNearestDepot)(Vehicle*, TileIndex, Trackdir);
+ PfnFindNearestDepot pfnFindNearestDepot = &CYapfRoadAnyDepot2::stFindNearestDepot;
+
+ // check if non-default YAPF type should be used
+ if (_patches.yapf.disable_node_optimization)
+ pfnFindNearestDepot = &CYapfRoadAnyDepot1::stFindNearestDepot; // Trackdir, allow 90-deg
+
+ Depot* ret = pfnFindNearestDepot(const_cast<Vehicle*>(v), tile, trackdir);
+ return ret;
+}
diff --git a/yapf/yapf_settings.h b/yapf/yapf_settings.h
new file mode 100644
index 000000000..3596b6ac3
--- /dev/null
+++ b/yapf/yapf_settings.h
@@ -0,0 +1,60 @@
+/* $Id$ */
+#if !defined(YAPF_SETTINGS_H) || defined(YS_DEF)
+
+# ifndef YAPF_SETTINGS_H
+# define YAPF_SETTINGS_H
+# endif
+
+# ifndef YS_DEF
+/*
+* if YS_DEF is not defined, we will only do following declaration:
+* typedef struct YapfSettings {
+* bool disable_node_optimization;
+* uint32 max_search_nodes;
+* .... all other yapf related settings ...
+* } YapfSettings;
+*
+* otherwise we will just expand YS_DEF_xx macros and then #undef them
+*/
+# define YS_DEF_BEGIN typedef struct YapfSettings {
+# define YS_DEF(type, name) type name;
+# define YS_DEF_END } YapfSettings;
+
+# endif /* !YS_DEF */
+
+# ifndef YS_DEF_BEGIN
+# define YS_DEF_BEGIN
+# endif // YS_DEF_BEGIN
+
+# ifndef YS_DEF_END
+# define YS_DEF_END
+# endif // YS_DEF_END
+
+YS_DEF_BEGIN
+ YS_DEF(bool , disable_node_optimization) ///< whether to use exit-dir instead of trackdir in node key
+ YS_DEF(uint32, max_search_nodes) ///< stop path-finding when this number of nodes visited
+ YS_DEF(bool , ship_use_yapf) ///< use YAPF for ships
+ YS_DEF(bool , road_use_yapf) ///< use YAPF for road
+ YS_DEF(bool , rail_use_yapf) ///< use YAPF for rail
+ YS_DEF(bool , rail_firstred_twoway_eol) ///< treat first red two-way signal as dead end
+ YS_DEF(uint32, rail_firstred_penalty) ///< penalty for first red signal
+ YS_DEF(uint32, rail_firstred_exit_penalty) ///< penalty for first red exit signal
+ YS_DEF(uint32, rail_lastred_penalty) ///< penalty for last red signal
+ YS_DEF(uint32, rail_lastred_exit_penalty) ///< penalty for last red exit signal
+ YS_DEF(uint32, rail_station_penalty) ///< penalty for non-target station tile
+ YS_DEF(uint32, rail_slope_penalty) ///< penalty for up-hill slope
+ YS_DEF(uint32, rail_curve45_penalty) ///< penalty for curve
+ YS_DEF(uint32, rail_curve90_penalty) ///< penalty for 90-deg curve
+ YS_DEF(uint32, rail_depot_reverse_penalty) ///< penalty for reversing in the depot
+ YS_DEF(uint32, rail_crossing_penalty) ///< penalty for level crossing
+ YS_DEF(uint32, rail_look_ahead_max_signals)///< max. number of signals taken into consideration in look-ahead load balancer
+ YS_DEF(int32 , rail_look_ahead_signal_p0) ///< constant in polynomial penalty function
+ YS_DEF(int32 , rail_look_ahead_signal_p1) ///< constant in polynomial penalty function
+ YS_DEF(int32 , rail_look_ahead_signal_p2) ///< constant in polynomial penalty function
+YS_DEF_END;
+
+#undef YS_DEF_BEGIN
+#undef YS_DEF
+#undef YS_DEF_END
+
+#endif /* !YAPF_SETTINGS_H || YS_DEF */
diff --git a/yapf/yapf_ship.cpp b/yapf/yapf_ship.cpp
new file mode 100644
index 000000000..c19f6bbdd
--- /dev/null
+++ b/yapf/yapf_ship.cpp
@@ -0,0 +1,168 @@
+/* $Id$ */
+
+#include "../stdafx.h"
+
+#include "yapf.hpp"
+
+/** Node Follower module of YAPF for ships */
+template <class Types>
+class CYapfFollowShipT
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::TrackFollower TrackFollower;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+protected:
+ FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+public:
+ inline void PfFollowNode(Node& old_node)
+ {
+ TrackFollower F;
+ if (F.Follow(old_node.m_key.m_tile, old_node.m_key.m_td))
+ Yapf().AddMultipleNodes(&old_node, F.m_new_tile, F.m_new_td_bits);
+ }
+
+ FORCEINLINE char TransportTypeChar() const {return 'w';}
+
+ static Trackdir ChooseShipTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)
+ {
+ // handle special case - when next tile is destination tile
+ if (tile == v->dest_tile) {
+ // convert tracks to trackdirs
+ TrackdirBits trackdirs = (TrackdirBits)(tracks | ((int)tracks << 8));
+ // choose any trackdir reachable from enterdir
+ trackdirs &= DiagdirReachesTrackdirs(enterdir);
+ return (Trackdir)FindFirstBit2x64(trackdirs);
+ }
+
+ // move back to the old tile/trackdir (where ship is coming from)
+ TileIndex src_tile = TILE_ADD(tile, TileOffsByDir(ReverseDiagDir(enterdir)));
+ Trackdir trackdir = GetVehicleTrackdir(v);
+ assert(IsValidTrackdir(trackdir));
+
+ // convert origin trackdir to TrackdirBits
+ TrackdirBits trackdirs = TrackdirToTrackdirBits(trackdir);
+ // get available trackdirs on the destination tile
+ TrackdirBits dest_trackdirs = (TrackdirBits)(GetTileTrackStatus(v->dest_tile, TRANSPORT_WATER) & TRACKDIR_BIT_MASK);
+
+ // create pathfinder instance
+ Tpf pf;
+ // set origin and destination nodes
+ pf.SetOrigin(src_tile, trackdirs);
+ pf.SetDestination(v->dest_tile, dest_trackdirs);
+ // find best path
+ bool bFound = pf.FindPath(v);
+
+ Trackdir next_trackdir = INVALID_TRACKDIR; // this would mean "path not found"
+ if (bFound) {
+ // path was found
+ // walk through the path back to the origin
+ Node* pNode = &pf.GetBestNode();
+ Node* pPrevNode = NULL;
+ while (pNode->m_parent != NULL) {
+ pPrevNode = pNode;
+ pNode = pNode->m_parent;
+ }
+ // return trackdir from the best next node (direct child of origin)
+ Node& best_next_node = *pPrevNode;
+ assert(best_next_node.GetTile() == tile);
+ next_trackdir = best_next_node.GetTrackdir();
+ }
+ return next_trackdir;
+ }
+};
+
+/** Cost Provider module of YAPF for ships */
+template <class Types>
+class CYapfCostShipT
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+protected:
+ Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+public:
+ FORCEINLINE bool PfCalcCost(Node& n)
+ {
+ // base tile cost depending on distance
+ int c = IsDiagonalTrackdir(n.GetTrackdir()) ? 10 : 7;
+ // additional penalty for curves
+ if (n.m_parent != NULL && n.GetTrackdir() != n.m_parent->GetTrackdir()) c += 3;
+ // apply it
+ n.m_cost = n.m_parent->m_cost + c;
+ return true;
+ }
+};
+
+/** Config struct of YAPF for ships.
+ Defines all 6 base YAPF modules as classes providing services for CYapfBaseT.
+*/
+template <class Tpf_, class Ttrack_follower, class Tnode_list>
+struct CYapfShip_TypesT
+{
+ /** Types - shortcut for this struct type */
+ typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list> Types;
+
+ /** Tpf - pathfinder type */
+ typedef Tpf_ Tpf;
+ /** track follower helper class */
+ typedef Ttrack_follower TrackFollower;
+ /** node list type */
+ typedef Tnode_list NodeList;
+ /** pathfinder components (modules) */
+ typedef CYapfBaseT<Types> PfBase; // base pathfinder class
+ typedef CYapfFollowShipT<Types> PfFollow; // node follower
+ typedef CYapfOriginTileT<Types> PfOrigin; // origin provider
+ typedef CYapfDestinationTileT<Types> PfDestination; // destination/distance provider
+ typedef CYapfSegmentCostCacheNoneT<Types> PfCache; // segment cost cache provider
+ typedef CYapfCostShipT<Types> PfCost; // cost provider
+};
+
+// YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns
+struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater , CShipNodeListTrackDir> > {};
+// YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns
+struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater , CShipNodeListExitDir > > {};
+// YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns
+struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};
+
+/** Ship controller helper - path finder invoker */
+Trackdir YapfChooseShipTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)
+{
+ // default is YAPF type 2
+ typedef Trackdir (*PfnChooseShipTrack)(Vehicle*, TileIndex, DiagDirection, TrackBits);
+ PfnChooseShipTrack pfnChooseShipTrack = CYapfShip2::ChooseShipTrack; // default: ExitDir, allow 90-deg
+
+ // check if non-default YAPF type needed
+ if (_patches.forbid_90_deg)
+ pfnChooseShipTrack = &CYapfShip3::ChooseShipTrack; // Trackdir, forbid 90-deg
+ else if (_patches.yapf.disable_node_optimization)
+ pfnChooseShipTrack = &CYapfShip1::ChooseShipTrack; // Trackdir, allow 90-deg
+
+ Trackdir td_ret = pfnChooseShipTrack(v, tile, enterdir, tracks);
+ return td_ret;
+}
+
+/** performance measurement helper */
+void* NpfBeginInterval()
+{
+ CPerformanceTimer& perf = *new CPerformanceTimer;
+ perf.Start();
+ return &perf;
+}
+
+/** performance measurement helper */
+int NpfEndInterval(void* vperf)
+{
+ CPerformanceTimer& perf = *(CPerformanceTimer*)vperf;
+ perf.Stop();
+ int t = perf.Get(1000000);
+ delete &perf;
+ return t;
+}
+