diff options
Diffstat (limited to 'yapf')
| -rw-r--r-- | yapf/array.hpp | 71 | ||||
| -rw-r--r-- | yapf/autocopyptr.hpp | 83 | ||||
| -rw-r--r-- | yapf/binaryheap.hpp | 225 | ||||
| -rw-r--r-- | yapf/blob.hpp | 342 | ||||
| -rw-r--r-- | yapf/countedptr.hpp | 100 | ||||
| -rw-r--r-- | yapf/crc32.hpp | 65 | ||||
| -rw-r--r-- | yapf/fixedsizearray.hpp | 99 | ||||
| -rw-r--r-- | yapf/follow_track.cpp | 47 | ||||
| -rw-r--r-- | yapf/follow_track.hpp | 279 | ||||
| -rw-r--r-- | yapf/hashtable.hpp | 240 | ||||
| -rw-r--r-- | yapf/nodelist.hpp | 130 | ||||
| -rw-r--r-- | yapf/track_dir.hpp | 35 | ||||
| -rw-r--r-- | yapf/yapf.h | 120 | ||||
| -rw-r--r-- | yapf/yapf.hpp | 93 | ||||
| -rw-r--r-- | yapf/yapf_base.hpp | 331 | ||||
| -rw-r--r-- | yapf/yapf_common.cpp | 29 | ||||
| -rw-r--r-- | yapf/yapf_common.hpp | 163 | ||||
| -rw-r--r-- | yapf/yapf_costbase.hpp | 37 | ||||
| -rw-r--r-- | yapf/yapf_costcache.hpp | 196 | ||||
| -rw-r--r-- | yapf/yapf_costrail.hpp | 381 | ||||
| -rw-r--r-- | yapf/yapf_destrail.hpp | 149 | ||||
| -rw-r--r-- | yapf/yapf_node.hpp | 77 | ||||
| -rw-r--r-- | yapf/yapf_node_rail.hpp | 113 | ||||
| -rw-r--r-- | yapf/yapf_node_road.hpp | 36 | ||||
| -rw-r--r-- | yapf/yapf_rail.cpp | 277 | ||||
| -rw-r--r-- | yapf/yapf_road.cpp | 451 | ||||
| -rw-r--r-- | yapf/yapf_settings.h | 68 | ||||
| -rw-r--r-- | yapf/yapf_ship.cpp | 176 |
28 files changed, 0 insertions, 4413 deletions
diff --git a/yapf/array.hpp b/yapf/array.hpp deleted file mode 100644 index e8eff1c8c..000000000 --- a/yapf/array.hpp +++ /dev/null @@ -1,71 +0,0 @@ -/* $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: - static const int Tblock_size = Tblock_size_; ///< block size is now visible from outside - static const int Tnum_blocks = Tnum_blocks_; ///< number of blocks is now visible from outside - static const int Tcapacity = Tblock_size * Tnum_blocks; ///< total max number of items - - /** implicit constructor */ - FORCEINLINE CArrayT() { } - /** Clear (destroy) all items */ - FORCEINLINE void Clear() {m_a.Clear();} - /** 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 deleted file mode 100644 index fb6bfa028..000000000 --- a/yapf/autocopyptr.hpp +++ /dev/null @@ -1,83 +0,0 @@ -/* $Id$ */ - -#ifndef AUTOCOPYPTR_HPP -#define AUTOCOPYPTR_HPP - -#if 0 // reenable when needed -/** 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 /* 0 */ -#endif /* AUTOCOPYPTR_HPP */ diff --git a/yapf/binaryheap.hpp b/yapf/binaryheap.hpp deleted file mode 100644 index 7b72a25af..000000000 --- a/yapf/binaryheap.hpp +++ /dev/null @@ -1,225 +0,0 @@ -/* $Id$ */ - -#ifndef BINARYHEAP_HPP -#define BINARYHEAP_HPP - -//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 deleted file mode 100644 index 1a20f3ac2..000000000 --- a/yapf/blob.hpp +++ /dev/null @@ -1,342 +0,0 @@ -/* $Id$ */ - -#ifndef BLOB_HPP -#define BLOB_HPP - -/** Type-safe version of memcpy(). - * @param d destination buffer - * @param s source buffer - * @param num_items number of items to be copied (!not number of bytes!) */ -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 - * - * Internal member layout: - * 1. The only class member is pointer to the first item (see union ptr_u). - * 2. Allocated block contains the blob header (see CHdr) followed by the raw byte data. - * Always, when it allocates memory the allocated size is: - * sizeof(CHdr) + <data capacity> - * 3. Two 'virtual' members (m_size and m_max_size) are stored in the CHdr at beginning - * of the alloated block. - * 4. The pointer (in ptr_u) points behind the header (to the first data byte). - * When memory block is allocated, the sizeof(CHdr) it added to it. - * 5. Benefits of this layout: - * - items are accessed in the simplest possible way - just dereferencing the pointer, - * which is good for performance (assuming that data are accessed most often). - * - sizeof(blob) is the same as the size of any other pointer - * 6. Drawbacks of this layout: - * - the fact, that pointer to the alocated block is adjusted by sizeof(CHdr) before - * it is stored can lead to several confusions: - * - it is not common pattern so the implementation code is bit harder to read - * - valgrind can generate warning that allocated block is lost (not accessible) - * */ -class CBlobBaseSimple { -protected: - /** header of the allocated memory block */ - struct CHdr { - int m_size; ///< actual blob size in bytes - int m_max_size; ///< maximum (allocated) size in bytes - }; - - /** type used as class member */ - union { - int8 *m_pData; ///< pointer to the first byte of data - CHdr *m_pHdr_1; ///< pointer just after the CHdr holding m_size and m_max_size - } ptr_u; - -public: - static const int Ttail_reserve = 4; ///< four extra bytes will be always allocated and zeroed at the end - - /** default constructor - initializes empty blob */ - FORCEINLINE CBlobBaseSimple() { InitEmpty(); } - /** copy constructor */ - FORCEINLINE CBlobBaseSimple(const CBlobBaseSimple& src) - { - InitEmpty(); - AppendRaw(src); - } - /** destructor */ - FORCEINLINE ~CBlobBaseSimple() { Free(); } -protected: - /** initialize the empty blob by setting the ptr_u.m_pHdr_1 pointer to the static CHdr with - * both m_size and m_max_size containing zero */ - FORCEINLINE void InitEmpty() { static CHdr hdrEmpty[] = {{0, 0}, {0, 0}}; ptr_u.m_pHdr_1 = &hdrEmpty[1]; } - /** initialize blob by attaching it to the given header followed by data */ - FORCEINLINE void Init(CHdr* hdr) { ptr_u.m_pHdr_1 = &hdr[1]; } - /** blob header accessor - use it rather than using the pointer arithmetics directly - non-const version */ - FORCEINLINE CHdr& Hdr() { return ptr_u.m_pHdr_1[-1]; } - /** blob header accessor - use it rather than using the pointer arithmetics directly - const version */ - FORCEINLINE const CHdr& Hdr() const { return ptr_u.m_pHdr_1[-1]; } - /** return reference to the actual blob size - used when the size needs to be modified */ - FORCEINLINE int& RawSizeRef() { return Hdr().m_size; }; - -public: - /** return true if blob doesn't contain valid data */ - FORCEINLINE bool IsEmpty() const { return RawSize() == 0; } - /** return the number of valid data bytes in the blob */ - FORCEINLINE int RawSize() const { return Hdr().m_size; }; - /** return the current blob capacity in bytes */ - FORCEINLINE int MaxRawSize() const { return Hdr().m_max_size; }; - /** return pointer to the first byte of data - non-const version */ - FORCEINLINE int8* RawData() { return ptr_u.m_pData; } - /** return pointer to the first byte of data - const version */ - FORCEINLINE const int8* RawData() const { return ptr_u.m_pData; } -#if 0 // reenable when needed - /** return the 32 bit CRC of valid data in the blob */ - FORCEINLINE uint32 Crc32() const {return CCrc32::Calc(RawData(), RawSize());} -#endif //0 - /** invalidate blob's data - doesn't free buffer */ - FORCEINLINE void Clear() { RawSizeRef() = 0; } - /** free the blob's memory */ - FORCEINLINE void Free() { if (MaxRawSize() > 0) {RawFree(&Hdr()); InitEmpty();} } - /** copy data from another blob - replaces any existing blob's data */ - FORCEINLINE void CopyFrom(const CBlobBaseSimple& src) { Clear(); AppendRaw(src); } - /** overtake ownership of data buffer from the source blob - source blob will become empty */ - FORCEINLINE void MoveFrom(CBlobBaseSimple& src) { Free(); ptr_u.m_pData = src.ptr_u.m_pData; src.InitEmpty(); } - /** swap buffers (with data) between two blobs (this and source blob) */ - 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; } - - /** append new bytes at the end of existing data bytes - reallocates if necessary */ - 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); - } - } - - /** append bytes from given source blob to the end of existing data bytes - reallocates if necessary */ - 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; - } - } -}; - -/** Blob - simple dynamic Titem_ array. Titem_ (template argument) is a placeholder for any type. - * Titem_ can be any integral type, pointer, or structure. Using Blob instead of just plain C array - * simplifies the resource management in several ways: - * 1. When adding new item(s) it automatically grows capacity if needed. - * 2. When variable of type Blob comes out of scope it automatically frees the data buffer. - * 3. Takes care about the actual data size (number of used items). - * 4. Dynamically constructs only used items (as opposite of static array which constructs all items) */ -template <class Titem_, class Tbase_ = CBlobBaseSimple> -class CBlobT : public CBlobBaseSimple { - // make template arguments public: -public: - typedef Titem_ Titem; - typedef Tbase_ Tbase; - - static const int Titem_size = sizeof(Titem); - - /** Default constructor - makes new Blob ready to accept any data */ - FORCEINLINE CBlobT() : Tbase() {} - /** Copy constructor - make new blob to become copy of the original (source) blob */ - FORCEINLINE CBlobT(const Tbase& src) : Tbase(src) {assert((RawSize() % Titem_size) == 0);} - /** Destructor - ensures that allocated memory (if any) is freed */ - FORCEINLINE ~CBlobT() { Free(); } - /** Check the validity of item index (only in debug mode) */ - FORCEINLINE void CheckIdx(int idx) { assert(idx >= 0); assert(idx < Size()); } - /** Return pointer to the first data item - non-const version */ - FORCEINLINE Titem* Data() { return (Titem*)RawData(); } - /** Return pointer to the first data item - const version */ - FORCEINLINE const Titem* Data() const { return (const Titem*)RawData(); } - /** Return pointer to the idx-th data item - non-const version */ - FORCEINLINE Titem* Data(int idx) { CheckIdx(idx); return (Data() + idx); } - /** Return pointer to the idx-th data item - const version */ - FORCEINLINE const Titem* Data(int idx) const { CheckIdx(idx); return (Data() + idx); } - /** Return number of items in the Blob */ - FORCEINLINE int Size() const { return (RawSize() / Titem_size); } - /** Free the memory occupied by Blob destroying all items */ - 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(); - } - /** Grow number of data items in Blob by given number - doesn't construct items */ - FORCEINLINE Titem* GrowSizeNC(int num_items) { return (Titem*)GrowRawSize(num_items * Titem_size); } - /** Grow number of data items in Blob by given number - constructs new items (using Titem_'s default constructor) */ - FORCEINLINE Titem* GrowSizeC(int num_items) - { - Titem* pI = GrowSizeNC(num_items); - for (int i = num_items; i > 0; i--, pI++) new (pI) Titem(); - } - /** Destroy given number of items and reduce the Blob's data size */ - 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); - } - /** Append one data item at the end (calls Titem_'s default constructor) */ - FORCEINLINE Titem* AppendNew() - { - Titem& dst = *GrowSizeNC(1); // Grow size by one item - Titem* pNewItem = new (&dst) Titem(); // construct the new item by calling in-place new operator - return pNewItem; - } - /** Append the copy of given item at the end of Blob (using copy constructor) */ - FORCEINLINE Titem* Append(const Titem& src) - { - Titem& dst = *GrowSizeNC(1); // Grow size by one item - Titem* pNewItem = new (&dst) Titem(src); // construct the new item by calling in-place new operator with copy ctor() - return pNewItem; - } - /** Add given items (ptr + number of items) at the end of blob */ - 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; - } - /** Remove item with the given index by replacing it by the last item and reducing the size by one */ - FORCEINLINE void RemoveBySwap(int idx) - { - CheckIdx(idx); - // destroy removed item - Titem* pRemoved = Data(idx); - RemoveBySwap(pRemoved); - } - /** Remove item given by pointer replacing it by the last item and reducing the size by one */ - 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); - } - /** Ensures that given number of items can be added to the end of Blob. Returns pointer to the - * first free (unused) item */ - 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 deleted file mode 100644 index e63e47fb5..000000000 --- a/yapf/countedptr.hpp +++ /dev/null @@ -1,100 +0,0 @@ -/* $Id$ */ - -#ifndef COUNTEDPTR_HPP -#define COUNTEDPTR_HPP - -#if 0 // reenable when needed -/** @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 /* 0 */ -#endif /* COUNTEDPTR_HPP */ diff --git a/yapf/crc32.hpp b/yapf/crc32.hpp deleted file mode 100644 index 10e9a7ac4..000000000 --- a/yapf/crc32.hpp +++ /dev/null @@ -1,65 +0,0 @@ -/* $Id$ */ - -#ifndef CRC32_HPP -#define CRC32_HPP - -#if 0 // reenable when needed -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 // 0 - -#endif /* CRC32_HPP */ diff --git a/yapf/fixedsizearray.hpp b/yapf/fixedsizearray.hpp deleted file mode 100644 index 48b177f3c..000000000 --- a/yapf/fixedsizearray.hpp +++ /dev/null @@ -1,99 +0,0 @@ -/* $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 - - static const int Tcapacity = Tcapacity_; // the array capacity (maximum size) - static const int TitemSize = sizeof(Titem_); // size of item - static 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 = src.m_items; - 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 - - Clear(); - // free the memory block occupied by items - free(((int8*)m_items) - ThdrSize); - m_items = NULL; - } - - /** Clear (destroy) all items */ - FORCEINLINE void Clear() - { - // walk through all allocated items backward and destroy them - for (Titem* pItem = &m_items[Size() - 1]; pItem >= m_items; pItem--) { - pItem->~Titem_(); - } - // number of items become zero - SizeRef() = 0; - } - -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 deleted file mode 100644 index ad2f0b724..000000000 --- a/yapf/follow_track.cpp +++ /dev/null @@ -1,47 +0,0 @@ -/* $Id$ */ - -#include "../stdafx.h" -#include "yapf.hpp" -#include "follow_track.hpp" - -void FollowTrackInit(FollowTrack_t *This, const Vehicle* v) -{ - CFollowTrackWater& F = *(CFollowTrackWater*) This; - F.Init(v, NULL); -} - -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 deleted file mode 100644 index 7864dc5e5..000000000 --- a/yapf/follow_track.hpp +++ /dev/null @@ -1,279 +0,0 @@ -/* $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(const Vehicle* v = NULL, CPerformanceTimer* pPerf = NULL) - { - Init(v, pPerf); - } - - FORCEINLINE void Init(const 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_station = m_is_bridge = m_is_tunnel = false; - m_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 (EnteredDepot()) return true; - if (!CanExitOldTile()) return false; - FollowTileExit(); - if (!QueryNewTileTrackStatus()) return TryReverse(); - 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_tiles_skipped */ - FORCEINLINE void FollowTileExit() - { - m_is_station = m_is_bridge = m_is_tunnel = false; - m_tiles_skipped = 0; - - // 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_tiles_skipped = flotr.length - 1; - return; - } - assert(ReverseDiagDir(tunnel_enterdir) == m_exitdir); - } - - // extra handling for bridge ramp in our direction - if (IsBridgeTile(m_old_tile)) { - DiagDirection bridge_enterdir = GetBridgeRampDirection(m_old_tile); - if (bridge_enterdir == m_exitdir) { - // we are entering the bridge ramp - m_new_tile = GetOtherBridgeEnd(m_old_tile); - uint32 bridge_length = GetBridgeLength(m_old_tile, m_new_tile); - m_tiles_skipped = bridge_length; - m_is_bridge = true; - return; - } - assert(ReverseDiagDir(bridge_enterdir) == m_exitdir); - } - - // normal or station tile, do one step - TileIndexDiff diff = TileOffsByDiagDir(m_exitdir); - m_new_tile = TILE_ADD(m_old_tile, diff); - - // special handling for stations - if (IsRailTT() && IsRailwayStationTile(m_new_tile)) { - m_is_station = true; - } else if (IsRoadTT() && IsRoadStopTile(m_new_tile)) { - m_is_station = true; - } else { - m_is_station = false; - } - } - - /** stores track status (available trackdirs) for the new tile into m_new_td_bits */ - FORCEINLINE bool QueryNewTileTrackStatus() - { - CPerfStart perf(*m_pPerf); - if (IsRailTT() && 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; - // don't try to enter other player's depots - if (GetTileOwner(m_new_tile) != m_veh->owner) { - 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 - 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 holes and bridge ramps can be entered only from proper direction - if (!IsWaterTT() && IsTileType(m_new_tile, MP_TUNNELBRIDGE)) { - if (IsTunnel(m_new_tile)) { - if (!m_is_tunnel) { - DiagDirection tunnel_enterdir = GetTunnelDirection(m_new_tile); - if (tunnel_enterdir != m_exitdir) return false; - } - } else if (IsBridge(m_new_tile)) { - if (!m_is_bridge) { - DiagDirection ramp_enderdir = GetBridgeRampDirection(m_new_tile); - if (ramp_enderdir != m_exitdir) return false; - } - } - } - - // special handling for rail stations - get to the end of platform - if (IsRailTT() && m_is_station) { - // entered railway station - // get platform length - uint length = GetPlatformLength(m_new_tile, TrackdirToExitdir(m_old_td)); - // how big step we must do to get to the last platform tile; - m_tiles_skipped = length - 1; - // move to the platform end - TileIndexDiff diff = TileOffsByDiagDir(m_exitdir); - diff *= m_tiles_skipped; - m_new_tile = TILE_ADD(m_new_tile, diff); - return true; - } - - return true; - } - - /** return true if we entered depot and reversed inside */ - FORCEINLINE bool EnteredDepot() - { - // rail and road depots cause reversing - if (!IsWaterTT() && IsTileDepotType(m_old_tile, TT())) { - DiagDirection exitdir = IsRailTT() ? GetRailDepotDirection(m_old_tile) : GetRoadDepotDirection(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_tiles_skipped = 0; - m_is_tunnel = m_is_bridge = m_is_station = false; - return true; - } - } - return false; - } - - /** return true if we successfully reversed at end of road/track */ - FORCEINLINE bool TryReverse() - { - if (IsRoadTT()) { - // if we reached the end of road, we can reverse the RV and continue moving - m_exitdir = ReverseDiagDir(m_exitdir); - // new tile will be the same as old one - m_new_tile = m_old_tile; - // set new trackdir bits to all reachable trackdirs - QueryNewTileTrackStatus(); - m_new_td_bits &= DiagdirReachesTrackdirs(m_exitdir); - if (m_new_td_bits != TRACKDIR_BIT_NONE) { - // we have some trackdirs reachable after reversal - 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 (!IsWaterTT() && IsBridgeTile(m_old_tile)) { - 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 deleted file mode 100644 index c6b52e50a..000000000 --- a/yapf/hashtable.hpp +++ /dev/null @@ -1,240 +0,0 @@ -/* $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 - clears the slot by simple forgetting its items */ - FORCEINLINE void Clear() {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 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 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 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 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 - static const int Thash_bits = Thash_bits_; // publish num of hash bits - static 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;} - - /** simple clear - forget all items - used by CSegmentCostCacheT.Flush() */ - FORCEINLINE void Clear() const {for (int i = 0; i < Tcapacity; i++) m_slots[i].Clear();} - - /** 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 deleted file mode 100644 index f51afbfd4..000000000 --- a/yapf/nodelist.hpp +++ /dev/null @@ -1,130 +0,0 @@ -/* $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 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 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); - 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 deleted file mode 100644 index 0239f853e..000000000 --- a/yapf/track_dir.hpp +++ /dev/null @@ -1,35 +0,0 @@ -/* $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/yapf.h b/yapf/yapf.h deleted file mode 100644 index 6b58b4e08..000000000 --- a/yapf/yapf.h +++ /dev/null @@ -1,120 +0,0 @@ -/* $Id$ */ - -#ifndef YAPF_H -#define YAPF_H - -#include "../debug.h" - -/** Finds the best path for given ship. - * @param v the ship that needs to find a path - * @param tile the tile to find the path from (should be next tile the ship is about to enter) - * @param enterdir diagonal direction which the ship will enter this new tile from - * @param tracks available tracks on the new tile (to choose from) - * @return the best trackdir for next turn or INVALID_TRACKDIR if the path could not be found - */ -Trackdir YapfChooseShipTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks); - -/** Finds the best path for given road vehicle. - * @param v the RV that needs to find a path - * @param tile the tile to find the path from (should be next tile the RV is about to enter) - * @param enterdir diagonal direction which the RV will enter this new tile from - * @param tracks available tracks on the new tile (to choose from) - * @return the best trackdir for next turn or INVALID_TRACKDIR if the path could not be found - */ -Trackdir YapfChooseRoadTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir); - -/** Finds the best path for given train. - * @param v the train that needs to find a path - * @param tile the tile to find the path from (should be next tile the train is about to enter) - * @param enterdir diagonal direction which the RV will enter this new tile from - * @param trackdirs available trackdirs on the new tile (to choose from) - * @param no_path_found [out] true is returned if no path can be found (returned Trackdir is only a 'guess') - * @return the best trackdir for next turn or INVALID_TRACKDIR if the path could not be found - */ -Trackdir YapfChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool *path_not_found); - -/** Used by RV multistop feature to find the nearest road stop that has a free slot. - * @param v RV (its current tile will be the origin) - * @param tile destination tile - * @return distance from origin tile to the destination (number of road tiles) or UINT_MAX if path not found - */ -uint YapfRoadVehDistanceToTile(const Vehicle* v, TileIndex tile); - -/** Used when user sends RV to the nearest depot or if RV needs servicing. - * Returns the nearest depot (or NULL if depot was not found). - */ -Depot* YapfFindNearestRoadDepot(const Vehicle *v); - -/** Used when user sends train to the nearest depot or if train needs servicing. - * @v train that needs to go to some depot - * @max_distance max distance (number of track tiles) from the current train position - * (used also as optimization - the pathfinder can stop path finding if max_distance - * was reached and no depot was seen) - * @reverse_penalty penalty that should be added for the path that requires reversing the train first - * @depot_tile receives the depot tile if depot was found - * @reversed receives true if train needs to reversed first - * @return the true if depot was found. - */ -bool YapfFindNearestRailDepotTwoWay(Vehicle *v, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed); - -/** Returns true if it is better to reverse the train before leaving station */ -bool YapfCheckReverseTrain(Vehicle* v); - -/** Use this function to notify YAPF that track layout (or signal configuration) has change */ -void YapfNotifyTrackLayoutChange(TileIndex tile, Track track); - -/** performance measurement helpers */ -void* NpfBeginInterval(void); -int NpfEndInterval(void* perf); - - -extern int _aystar_stats_open_size; -extern int _aystar_stats_closed_size; - - -/** Track followers. They should help whenever any new code will need to walk through - * tracks, road or water tiles (pathfinders, signal controllers, vehicle controllers). - * It is an attempt to introduce API that should simplify tasks listed above. - * If you will need to use it: - * 1. allocate/declare FollowTrack_t structure; - * 2. call FollowTrackInit() and provide vehicle (if relevant) - * 3. call one of 6 FollowTrackXxxx() APIs below - * 4. check return value (if true then continue else stop) - * 5. look at FollowTrack_t structure for the result - * 6. optionally repeat steps 3..5 - * 7. in case of troubles contact KUDr - */ - -/** Base struct for track followers. */ -typedef struct FollowTrack_t -{ - const Vehicle* m_veh; ///< moving vehicle - TileIndex m_old_tile; ///< the origin (vehicle moved from) before move - Trackdir m_old_td; ///< the trackdir (the vehicle was on) before move - TileIndex m_new_tile; ///< the new tile (the vehicle has entered) - TrackdirBits m_new_td_bits; ///< the new set of available trackdirs - DiagDirection m_exitdir; ///< exit direction (leaving the old tile) - bool m_is_tunnel; ///< last turn passed tunnel - bool m_is_bridge; ///< last turn passed bridge ramp - bool m_is_station; ///< last turn passed station - int m_tiles_skipped; ///< number of skipped tunnel or station tiles -} FollowTrack_t; - -/** Initializes FollowTrack_t structure */ -void FollowTrackInit(FollowTrack_t *This, const Vehicle* v); - -/** Main track follower routines */ -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); - -/** Base tile length units */ -enum { - YAPF_TILE_LENGTH = 100, - YAPF_TILE_CORNER_LENGTH = 71 -}; - -#endif /* YAPF_H */ diff --git a/yapf/yapf.hpp b/yapf/yapf.hpp deleted file mode 100644 index 208f29c46..000000000 --- a/yapf/yapf.hpp +++ /dev/null @@ -1,93 +0,0 @@ -/* $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.h" -#include "../station_map.h" -#include "../vehicle.h" -#include "../date.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> -#include <new> - -#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());} - - FORCEINLINE int64 QueryTime() {return _rdtsc();} - FORCEINLINE int64 QueryFrequency() {return ((int64)2200 * 1000000);} -}; - -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 deleted file mode 100644 index 1d0417987..000000000 --- a/yapf/yapf_base.hpp +++ /dev/null @@ -1,331 +0,0 @@ -/* $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; ///< the pathfinder class (derived from THIS class) - 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; ///< here should be node closest to the destination if path not found - const YapfSettings *m_settings; ///< current settings (_patches.yapf) - int m_max_search_nodes; ///< maximum number of nodes we are allowed to visit before we give up - const Vehicle* m_veh; ///< vehicle that we are trying to drive - - int m_stats_cost_calcs; ///< stats - how many node's costs were calculated - int m_stats_cache_hits; ///< stats - how many node's costs were reused from cache - -public: - CPerformanceTimer m_perf_cost; ///< stats - total CPU time of this run - CPerformanceTimer m_perf_slope_cost; ///< stats - slope calculation CPU time - CPerformanceTimer m_perf_ts_cost; ///< stats - GetTrackStatus() CPU time - CPerformanceTimer m_perf_other_cost; ///< stats - other CPU time - -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) - , m_settings(&_patches.yapf) - , m_max_search_nodes(PfGetSettings().max_search_nodes) - , m_veh(NULL) - , m_stats_cost_calcs(0) - , m_stats_cache_hits(0) - , m_num_steps(0) - { - } - - /// default destructor - ~CYapfBaseT() {} - -protected: - /// to access inherited path finder - FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);} - -public: - /// return current settings (can be custom - player based - but later) - 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(const 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; - DEBUG(yapf, 3, "[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)); - 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); - // insert the new node only if it is not there - if (m_nodes.FindOpenNode(n.m_key) == NULL) { - m_nodes.InsertOpenNode(n); - } else { - // if we are here, it means that node is already there - how it is possible? - // probably the train is in the position that both its ends point to the same tile/exit-dir - // very unlikely, but it happened - } - } - - /** add multiple nodes - direct children of the given node */ - FORCEINLINE void AddMultipleNodes(Node* parent, TileIndex tile, TrackdirBits td_bits) - { - bool is_choice = (KillFirstBit2x64(td_bits) != 0); - 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, is_choice); - 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); - } - - const 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 deleted file mode 100644 index 39d119858..000000000 --- a/yapf/yapf_common.cpp +++ /dev/null @@ -1,29 +0,0 @@ -/* $Id$ */ - -#include "../stdafx.h" - -#include "yapf.hpp" -#include "follow_track.hpp" -#include "yapf_node_rail.hpp" -#include "yapf_costbase.hpp" -#include "yapf_costcache.hpp" - -/** translate tileh to the bitset of up-hill trackdirs */ -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 deleted file mode 100644 index 869bc820c..000000000 --- a/yapf/yapf_common.hpp +++ /dev/null @@ -1,163 +0,0 @@ -/* $Id$ */ - -#ifndef YAPF_COMMON_HPP -#define YAPF_COMMON_HPP - -/** YAPF origin provider base class - used when origin is one tile / multiple trackdirs */ -template <class Types> -class CYapfOriginTileT -{ -public: - typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) - 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; ///< origin tile - TrackdirBits m_orgTrackdirs; ///< origin trackdir mask - - /// to access inherited path finder - FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);} - -public: - /// Set origin tile / trackdir mask - void SetOrigin(TileIndex tile, TrackdirBits trackdirs) - { - m_orgTile = tile; - m_orgTrackdirs = trackdirs; - } - - /// Called when YAPF needs to place origin nodes into open list - void PfSetStartupNodes() - { - bool is_choice = (KillFirstBit2x64(m_orgTrackdirs) != 0); - 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, is_choice); - Yapf().AddStartupNode(n1); - } - } -}; - -/** YAPF origin provider base class - used when there are two tile/trackdir origins */ -template <class Types> -class CYapfOriginTileTwoWayT -{ -public: - typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) - 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; ///< first origin tile - Trackdir m_orgTd; ///< first origin trackdir - TileIndex m_revTile; ///< second (reversed) origin tile - Trackdir m_revTd; ///< second (reversed) origin trackdir - int m_reverse_penalty; ///< penalty to be added for using the reversed origin - bool m_treat_first_red_two_way_signal_as_eol; ///< in some cases (leaving station) we need to handle first two-way signal differently - - /// to access inherited path finder - FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);} - -public: - /// set origin (tiles, trackdirs, etc.) - 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; - } - - /// Called when YAPF needs to place origin nodes into open list - void PfSetStartupNodes() - { - if (m_orgTile != INVALID_TILE && m_orgTd != INVALID_TRACKDIR) { - Node& n1 = Yapf().CreateNewNode(); - n1.Set(NULL, m_orgTile, m_orgTd, false); - Yapf().AddStartupNode(n1); - } - if (m_revTile != INVALID_TILE && m_revTd != INVALID_TRACKDIR) { - Node& n2 = Yapf().CreateNewNode(); - n2.Set(NULL, m_revTile, m_revTd, false); - n2.m_cost = m_reverse_penalty; - Yapf().AddStartupNode(n2); - } - } - - /// return true if first two-way signal should be treated as dead end - FORCEINLINE bool TreatFirstRedTwoWaySignalAsEOL() - { - return Yapf().PfGetSettings().rail_firstred_twoway_eol && m_treat_first_red_two_way_signal_as_eol; - } -}; - -/** YAPF destination provider base class - used when destination is single tile / multiple trackdirs */ -template <class Types> -class CYapfDestinationTileT -{ -public: - typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) - 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; ///< destination tile - TrackdirBits m_destTrackdirs; ///< destination trackdir mask - -public: - /// set the destination tile / more trackdirs - void SetDestination(TileIndex tile, TrackdirBits trackdirs) - { - m_destTile = tile; - m_destTrackdirs = trackdirs; - } - -protected: - /// to access inherited path finder - Tpf& Yapf() {return *static_cast<Tpf*>(this);} - -public: - /// Called by YAPF to detect if node ends in the desired destination - FORCEINLINE bool PfDetectDestination(Node& n) - { - bool bDest = (n.m_key.m_tile == m_destTile) && ((m_destTrackdirs & TrackdirToTrackdirBits(n.GetTrackdir())) != TRACKDIR_BIT_NONE); - return bDest; - } - - /** Called by YAPF to calculate cost estimate. Calculates distance to the destination - * adds it to the actual cost from origin and stores the sum to the Node::m_estimate */ - 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; - } -}; - -/** YAPF template that uses Ttypes template argument to determine all YAPF - * components (base classes) from which the actual YAPF is composed. - * For example classes consult: CYapfRail_TypesT template and its instantiations: - * CYapfRail1, CYapfRail2, CYapfRail3, CYapfAnyDepotRail1, CYapfAnyDepotRail2, CYapfAnyDepotRail3 */ -template <class Ttypes> -class CYapfT - : public Ttypes::PfBase ///< Instance of CYapfBaseT - main YAPF loop and support base class - , public Ttypes::PfCost ///< Cost calculation provider base class - , public Ttypes::PfCache ///< Segment cost cache provider - , public Ttypes::PfOrigin ///< Origin (tile or two-tile origin) - , public Ttypes::PfDestination ///< Destination detector and distance (estimate) calculation provider - , public Ttypes::PfFollow ///< Node follower (stepping provider) -{ -}; - - - -#endif /* YAPF_COMMON_HPP */ diff --git a/yapf/yapf_costbase.hpp b/yapf/yapf_costbase.hpp deleted file mode 100644 index df4d9e787..000000000 --- a/yapf/yapf_costbase.hpp +++ /dev/null @@ -1,37 +0,0 @@ -/* $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)) { - if (IsBridgeTile(tile)) { - // it is bridge ramp, check if we are entering the bridge - if (GetBridgeRampDirection(tile) != TrackdirToExitdir(td)) return false; // no, we are living it, no penalty - // we are entering the bridge - // if the tile slope is downwards, then bridge ramp has not upward slope - uint tile_slope = GetTileSlope(tile, NULL) & 0x0F; - if ((c_upwards_slopes[tile_slope] & TrackdirToTrackdirBits(ReverseTrackdir(td))) != 0) return false; // tile under ramp goes down, no penalty - // tile under ramp isn't going down, so ramp must go up - return true; - } else { - // not bridge ramp - if (IsTunnelTile(tile)) return false; // tunnel entry/exit doesn't slope - uint tile_slope = GetTileSlope(tile, NULL) & 0x0F; - if ((c_upwards_slopes[tile_slope] & TrackdirToTrackdirBits(td)) != 0) return true; // slopes uphill => apply penalty - } - } - return false; - } -}; - -struct CostRailSettings { - // look-ahead signal penalty -}; - - -#endif /* YAPF_COSTBASE_HPP */ diff --git a/yapf/yapf_costcache.hpp b/yapf/yapf_costcache.hpp deleted file mode 100644 index c90d37302..000000000 --- a/yapf/yapf_costcache.hpp +++ /dev/null @@ -1,196 +0,0 @@ -/* $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; ///< the pathfinder class (derived from THIS class) - typedef typename Types::NodeList::Titem Node; ///< this will be our node type - - /** Called by YAPF to attach cached or local segment cost data to the given node. - * @return true if globally cached data were used or false if local data was used */ - FORCEINLINE bool PfNodeCacheFetch(Node& n) - { - return false; - }; - - /** Called by YAPF to flush the cached segment cost data back into cache storage. - * Current cache implementation doesn't use that. */ - 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; ///< the pathfinder class (derived from THIS class) - 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; - - /// to access inherited path finder - FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);} - -public: - /** Called by YAPF to attach cached or local segment cost data to the given node. - * @return true if globally cached data were used or false if local data was used */ - FORCEINLINE bool PfNodeCacheFetch(Node& n) - { - CacheKey key(n.GetKey()); - Yapf().ConnectNodeToCachedData(n, *new (&m_local_cache.AddNC()) CachedData(key)); - return false; - }; - - /** Called by YAPF to flush the cached segment cost data back into cache storage. - * Current cache implementation doesn't use that. */ - FORCEINLINE void PfNodeCacheFlush(Node& n) - { - }; -}; - - -/** Base class for segment cost cache providers. Contains global counter - * of track layout changes and static notification function called whenever - * the track layout changes. It is implemented as base class because it needs - * to be shared between all rail YAPF types (one shared counter, one notification - * function. */ -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() {} - - /** flush (clear) the cache */ - FORCEINLINE void Flush() {m_map.Clear(); m_heap.Clear();}; - - 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; ///< the pathfinder class (derived from THIS class) - 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()) {}; - - /// to access inherited path finder - FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);} - - FORCEINLINE static Cache& stGetGlobalCache() - { - static int last_rail_change_counter = 0; - static Date last_date = 0; - static Cache C; - - // some statistics - if (last_date != _date) { - last_date = _date; - DEBUG(yapf, 2, "Pf time today: %5d ms", _total_pf_time_us / 1000); - _total_pf_time_us = 0; - } - - // delete the cache sometimes... - if (last_rail_change_counter != Cache::s_rail_change_counter) { - last_rail_change_counter = Cache::s_rail_change_counter; - C.Flush(); - } - return C; - } - -public: - /** Called by YAPF to attach cached or local segment cost data to the given node. - * @return true if globally cached data were used or false if local data was used */ - 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; - }; - - /** Called by YAPF to flush the cached segment cost data back into cache storage. - * Current cache implementation doesn't use that. */ - FORCEINLINE void PfNodeCacheFlush(Node& n) - { - }; - -}; - - - - -#endif /* YAPF_COSTCACHE_HPP */ diff --git a/yapf/yapf_costrail.hpp b/yapf/yapf_costrail.hpp deleted file mode 100644 index 93062b5c2..000000000 --- a/yapf/yapf_costrail.hpp +++ /dev/null @@ -1,381 +0,0 @@ -/* $Id$ */ - -#ifndef YAPF_COSTRAIL_HPP -#define YAPF_COSTRAIL_HPP - - -template <class Types> -class CYapfCostRailT - : public CYapfCostBase - , public CostRailSettings -{ -public: - typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) - 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; -public: - bool m_stopped_on_first_two_way_signal; -protected: - - static const int s_max_segment_cost = 10000; - - CYapfCostRailT() - : m_max_cost(0) - , m_stopped_on_first_two_way_signal(false) - { - // 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); - } - - /// to access inherited path finder - 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); - // cache the look-ahead polynomial constant only if we didn't pass more signals than the look-ahead limit is - int look_ahead_cost = (n.m_num_signals_passed < m_sig_look_ahead_costs.Size()) ? m_sig_look_ahead_costs.Data()[n.m_num_signals_passed] : 0; - if (sig_state != SIGNAL_STATE_RED) { - // green signal - n.flags_u.flags_s.m_last_signal_was_red = false; - // negative look-ahead red-signal penalties would cause problems later, so use them as positive penalties for green signal - if (look_ahead_cost < 0) { - // add its negation to the cost - cost -= look_ahead_cost; - } - } else { - // we have a red signal in our direction - // was it first signal which is two-way? - if (Yapf().TreatFirstRedTwoWaySignalAsEOL() && n.flags_u.flags_s.m_choice_seen && 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; - Yapf().m_stopped_on_first_two_way_signal = 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 (look_ahead_cost > 0) { - // add the look ahead penalty only if it is positive - cost += look_ahead_cost; - } - - // 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; - } - - FORCEINLINE int PlatformLengthPenalty(int platform_length) - { - int cost = 0; - const Vehicle* v = Yapf().GetVehicle(); - assert(v != NULL); - assert(v->type == VEH_Train); - assert(v->u.rail.cached_total_length != 0); - int needed_platform_length = (v->u.rail.cached_total_length + TILE_SIZE - 1) / TILE_SIZE; - if (platform_length > needed_platform_length) { - // apply penalty for longer platform than needed - cost += Yapf().PfGetSettings().rail_longer_platform_penalty; - } else if (needed_platform_length > platform_length) { - // apply penalty for shorter platform than needed - cost += Yapf().PfGetSettings().rail_shorter_platform_penalty; - } - return cost; - } - -public: - FORCEINLINE void SetMaxCost(int max_cost) {m_max_cost = max_cost;} - - /** Called by YAPF to calculate the cost from the origin to the given node. - * Calculates only the cost of given node, adds it to the parent node cost - * and stores the result into Node::m_cost member */ - 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; - const 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 = Yapf().PfDetectDestination(tile, trackdir); - - 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 - 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); - - target_seen = Yapf().PfDetectDestination(tile, trackdir); - - // 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_tiles_skipped; - - // add penalty for skipped station tiles - if (F.m_is_station) - { - if (target_seen) { - // it is our destination station - uint platform_length = F.m_tiles_skipped + 1; - segment_cost += PlatformLengthPenalty(platform_length); - } else { - // station is not our destination station, apply penalty for skipped platform tiles - segment_cost += Yapf().PfGetSettings().rail_station_penalty * F.m_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 deleted file mode 100644 index 9a5bd0536..000000000 --- a/yapf/yapf_destrail.hpp +++ /dev/null @@ -1,149 +0,0 @@ -/* $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; ///< the pathfinder class (derived from THIS class) - typedef typename Types::NodeList::Titem Node; ///< this will be our node type - typedef typename Node::Key Key; ///< key to hash tables - - /// to access inherited path finder - Tpf& Yapf() {return *static_cast<Tpf*>(this);} - - /// Called by YAPF to detect if node ends in the desired destination - FORCEINLINE bool PfDetectDestination(Node& n) - { - return PfDetectDestination(n.GetLastTile(), n.GetLastTrackdir()); - } - - /// Called by YAPF to detect if node ends in the desired destination - FORCEINLINE bool PfDetectDestination(TileIndex tile, Trackdir td) - { - bool bDest = IsTileDepotType(tile, TRANSPORT_RAIL); - return bDest; - } - - /** Called by YAPF to calculate cost estimate. Calculates distance to the destination - * adds it to the actual cost from origin and stores the sum to the Node::m_estimate */ - 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; ///< the pathfinder class (derived from THIS class) - 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; - - /// to access inherited path finder - 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.dest); - m_dest_station_id = v->current_order.dest; - 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); - } - - /// Called by YAPF to detect if node ends in the desired destination - FORCEINLINE bool PfDetectDestination(Node& n) - { - return PfDetectDestination(n.GetLastTile(), n.GetLastTrackdir()); - } - - /// Called by YAPF to detect if node ends in the desired destination - FORCEINLINE bool PfDetectDestination(TileIndex tile, Trackdir td) - { - bool bDest; - if (m_dest_station_id != INVALID_STATION) { - bDest = IsRailwayStationTile(tile) - && (GetStationIndex(tile) == m_dest_station_id) - && (GetRailStationTrack(tile) == TrackdirToTrack(td)); - } else { - bDest = (tile == m_destTile) - && ((m_destTrackdirs & TrackdirToTrackdirBits(td)) != TRACKDIR_BIT_NONE); - } - return bDest; - } - - /** Called by YAPF to calculate cost estimate. Calculates distance to the destination - * adds it to the actual cost from origin and stores the sum to the Node::m_estimate */ - 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 deleted file mode 100644 index 2fa82a6a6..000000000 --- a/yapf/yapf_node.hpp +++ /dev/null @@ -1,77 +0,0 @@ -/* $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, bool is_choice) - { - 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 deleted file mode 100644 index df0186989..000000000 --- a/yapf/yapf_node_rail.hpp +++ /dev/null @@ -1,113 +0,0 @@ -/* $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 { - uint32 m_inherited_flags; - struct { - bool m_targed_seen : 1; - bool m_choice_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, bool is_choice) - { - base::Set(parent, tile, td, is_choice); - 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; - } - flags_u.flags_s.m_choice_seen |= is_choice; - } - - 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 deleted file mode 100644 index dc6f1be3a..000000000 --- a/yapf/yapf_node_road.hpp +++ /dev/null @@ -1,36 +0,0 @@ -/* $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, bool is_choice) - { - base::Set(parent, tile, td, is_choice); - 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 deleted file mode 100644 index 1461b9402..000000000 --- a/yapf/yapf_rail.cpp +++ /dev/null @@ -1,277 +0,0 @@ -/* $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; ///< the pathfinder class (derived from THIS class) - 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: - /// to access inherited path finder - FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);} - -public: - /** Called by YAPF to move from the given node to the next tile. For each - * reachable trackdir on the new tile creates new node, initializes it - * and adds it to the open list by calling Yapf().AddNewNode(n) */ - 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); - } - - /// return debug report character to identify the transportation type - 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(YAPF_TILE_LENGTH * 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; ///< the pathfinder class (derived from THIS class) - 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: - /// to access inherited path finder - FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);} - -public: - /** Called by YAPF to move from the given node to the next tile. For each - * reachable trackdir on the new tile creates new node, initializes it - * and adds it to the open list by calling Yapf().AddNewNode(n) */ - 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); - } - - /// return debug report character to identify the transportation type - FORCEINLINE char TransportTypeChar() const {return 't';} - - static Trackdir stChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool *path_not_found) - { - // create pathfinder instance - Tpf pf; - return pf.ChooseRailTrack(v, tile, enterdir, trackdirs, path_not_found); - } - - FORCEINLINE Trackdir ChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool *path_not_found) - { - // set origin and destination nodes - Yapf().SetOrigin(v->tile, GetVehicleTrackdir(v), INVALID_TILE, INVALID_TRACKDIR, 1, true); - Yapf().SetDestination(v); - - // find the best path - bool path_found = Yapf().FindPath(v); - if (path_not_found != NULL) { - // tell controller that the path was only 'guessed' - // treat the path as found if stopped on the first two way signal(s) - *path_not_found = !(path_found || Yapf().m_stopped_on_first_two_way_signal); - } - - // 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, bool *path_not_found) -{ - // default is YAPF type 2 - typedef Trackdir (*PfnChooseRailTrack)(Vehicle*, TileIndex, DiagDirection, TrackdirBits, bool*); - 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, path_not_found); - - 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); - - TileIndex tile = v->tile; - TileIndex last_tile = last_veh->tile; - - // their trackdirs - Trackdir td = GetVehicleTrackdir(v); - Trackdir td_rev = 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; -} - -/** if any track changes, this counter is incremented - that will invalidate segment cost cache */ -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 deleted file mode 100644 index 02b306b31..000000000 --- a/yapf/yapf_road.cpp +++ /dev/null @@ -1,451 +0,0 @@ -/* $Id$ */ - -#include "../stdafx.h" - -#include "yapf.hpp" -#include "yapf_node_road.hpp" - - -template <class Types> -class CYapfCostRoadT -{ -public: - typedef typename Types::Tpf Tpf; ///< pathfinder (derived from THIS class) - typedef typename Types::TrackFollower TrackFollower; ///< track follower helper - typedef typename Types::NodeList::Titem Node; ///< this will be our node type - typedef typename Node::Key Key; ///< key to hash tables - -protected: - /// to access inherited path finder - 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_SIZE / 2, y1 + TILE_SIZE / 2); - - // 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_SIZE / 2, y2 + TILE_SIZE / 2); - - if (z2 - z1 > 1) { - /* Slope up */ - return Yapf().PfGetSettings().road_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 += YAPF_TILE_LENGTH; - switch (GetTileType(tile)) { - case MP_STREET: - /* Increase the cost for level crossings */ - if (IsLevelCrossing(tile)) - cost += Yapf().PfGetSettings().road_crossing_penalty; - break; - - default: - break; - } - } else { - // non-diagonal trackdir - cost = YAPF_TILE_CORNER_LENGTH + Yapf().PfGetSettings().road_curve_penalty; - } - return cost; - } - -public: - /** Called by YAPF to calculate the cost from the origin to the given node. - * Calculates only the cost of given node, adds it to the parent node cost - * and stores the result into Node::m_cost member */ - 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); - - // stop if we have just entered the depot - if (IsTileDepotType(tile, TRANSPORT_ROAD) && trackdir == DiagdirToDiagTrackdir(ReverseDiagDir(GetRoadDepotDirection(tile)))) { - // next time we will reverse and leave the depot - break; - } - - // if there are no reachable trackdirs on new tile, we have end of road - TrackFollower F(Yapf().GetVehicle()); - 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 += F.m_tiles_skipped * YAPF_TILE_LENGTH; - - // 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); - const 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; ///< the pathfinder class (derived from THIS class) - 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 - - /// to access inherited path finder - Tpf& Yapf() {return *static_cast<Tpf*>(this);} - - /// Called by YAPF to detect if node ends in the desired destination - FORCEINLINE bool PfDetectDestination(Node& n) - { - bool bDest = IsTileDepotType(n.m_segment_last_tile, TRANSPORT_ROAD); - return bDest; - } - - /** Called by YAPF to calculate cost estimate. Calculates distance to the destination - * adds it to the actual cost from origin and stores the sum to the Node::m_estimate */ - FORCEINLINE bool PfCalcEstimate(Node& n) - { - n.m_estimate = n.m_cost; - return true; - } -}; - - -template <class Types> -class CYapfDestinationTileRoadT -{ -public: - typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) - 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: - /// to access inherited path finder - Tpf& Yapf() {return *static_cast<Tpf*>(this);} - -public: - /// Called by YAPF to detect if node ends in the desired destination - 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; - } - - /** Called by YAPF to calculate cost estimate. Calculates distance to the destination - * adds it to the actual cost from origin and stores the sum to the Node::m_estimate */ - 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 * 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; - } -}; - - - -template <class Types> -class CYapfFollowRoadT -{ -public: - typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) - 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: - /// to access inherited path finder - FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);} - -public: - - /** Called by YAPF to move from the given node to the next tile. For each - * reachable trackdir on the new tile creates new node, initializes it - * and adds it to the open list by calling Yapf().AddNewNode(n) */ - inline void PfFollowNode(Node& old_node) - { - TrackFollower F(Yapf().GetVehicle()); - 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); - } - - /// return debug report character to identify the transportation type - 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 uint stDistanceToTile(const Vehicle *v, TileIndex tile) - { - Tpf pf; - return pf.DistanceToTile(v, tile); - } - - FORCEINLINE uint DistanceToTile(const Vehicle *v, TileIndex dst_tile) - { - // handle special case - when current tile is the destination tile - if (dst_tile == v->tile) { - // distance is zero in this case - return 0; - } - - if (!SetOriginFromVehiclePos(v)) return UINT_MAX; - - // set destination tile, trackdir - // get available trackdirs on the destination tile - uint dest_ts = GetTileTrackStatus(dst_tile, TRANSPORT_ROAD); - TrackdirBits dst_td_bits = (TrackdirBits)(dest_ts & TRACKDIR_BIT_MASK); - Yapf().SetDestination(dst_tile, dst_td_bits); - - // find the best path - Yapf().FindPath(v); - - // if path not found - return distance = UINT_MAX - uint dist = UINT_MAX; - Node* pNode = &Yapf().GetBestNode(); - if (pNode != NULL) { - // path was found or at least suggested - // get the path cost estimate - dist = pNode->GetCostEstimate(); - } - - return dist; - } - - /** Return true if the valid origin (tile/trackdir) was set from the current vehicle position. */ - FORCEINLINE bool SetOriginFromVehiclePos(const Vehicle *v) - { - // set origin (tile, trackdir) - TileIndex src_tile = v->tile; - Trackdir src_td = GetVehicleTrackdir(v); - if ((GetTileTrackStatus(src_tile, TRANSPORT_ROAD) & TrackdirToTrackdirBits(src_td)) == 0) { - // sometimes the roadveh is not on the road (it resides on non-existing track) - // how should we handle that situation? - return false; - } - Yapf().SetOrigin(src_tile, TrackdirToTrackdirBits(src_td)); - return true; - } - - static Depot* stFindNearestDepot(const Vehicle* v, TileIndex tile, Trackdir td) - { - Tpf pf; - return pf.FindNearestDepot(v, tile, td); - } - - FORCEINLINE Depot* FindNearestDepot(const 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; -} - -uint YapfRoadVehDistanceToTile(const Vehicle* v, TileIndex tile) -{ - // default is YAPF type 2 - typedef uint (*PfnDistanceToTile)(const Vehicle*, TileIndex); - PfnDistanceToTile pfnDistanceToTile = &CYapfRoad2::stDistanceToTile; // default: ExitDir, allow 90-deg - - // check if non-default YAPF type should be used - if (_patches.yapf.disable_node_optimization) - pfnDistanceToTile = &CYapfRoad1::stDistanceToTile; // Trackdir, allow 90-deg - - // measure distance in YAPF units - uint dist = pfnDistanceToTile(v, tile); - // convert distance to tiles - if (dist != UINT_MAX) - dist = (dist + YAPF_TILE_LENGTH - 1) / YAPF_TILE_LENGTH; - return dist; -} - -Depot* YapfFindNearestRoadDepot(const Vehicle *v) -{ - TileIndex tile = v->tile; - Trackdir trackdir = GetVehicleTrackdir(v); - if ((GetTileTrackStatus(tile, TRANSPORT_ROAD) & TrackdirToTrackdirBits(trackdir)) == 0) - return NULL; - - // handle the case when our vehicle is already in the depot tile - if (IsTileType(tile, MP_STREET) && IsTileDepotType(tile, TRANSPORT_ROAD)) { - // only what we need to return is the Depot* - return GetDepotByTile(tile); - } - - // default is YAPF type 2 - typedef Depot* (*PfnFindNearestDepot)(const 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(v, tile, trackdir); - return ret; -} diff --git a/yapf/yapf_settings.h b/yapf/yapf_settings.h deleted file mode 100644 index 193714dd1..000000000 --- a/yapf/yapf_settings.h +++ /dev/null @@ -1,68 +0,0 @@ -/* $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(uint32, road_slope_penalty) ///< penalty for up-hill slope - YS_DEF(uint32, road_curve_penalty) ///< penalty for curves - YS_DEF(uint32, road_crossing_penalty) ///< penalty for level crossing - 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(uint32, rail_longer_platform_penalty) ///< penalty for longer station platform than train - YS_DEF(uint32, rail_longer_platform_per_tile_penalty) ///< penalty for longer station platform than train (per tile) - YS_DEF(uint32, rail_shorter_platform_penalty) ///< penalty for shorter station platform than train - YS_DEF(uint32, rail_shorter_platform_per_tile_penalty) ///< penalty for shorter station platform than train (per tile) -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 deleted file mode 100644 index 038bdba43..000000000 --- a/yapf/yapf_ship.cpp +++ /dev/null @@ -1,176 +0,0 @@ -/* $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; ///< the pathfinder class (derived from THIS class) - 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: - /// to access inherited path finder - FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);} - -public: - /** Called by YAPF to move from the given node to the next tile. For each - * reachable trackdir on the new tile creates new node, initializes it - * and adds it to the open list by calling Yapf().AddNewNode(n) */ - 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); - } - - /// return debug report character to identify the transportation type - 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, TileOffsByDiagDir(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; ///< the pathfinder class (derived from THIS class) - typedef typename Types::NodeList::Titem Node; ///< this will be our node type - typedef typename Node::Key Key; ///< key to hash tables - -protected: - /// to access inherited path finder - Tpf& Yapf() {return *static_cast<Tpf*>(this);} - -public: - /** Called by YAPF to calculate the cost from the origin to the given node. - * Calculates only the cost of given node, adds it to the parent node cost - * and stores the result into Node::m_cost member */ - 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; -} |