summaryrefslogtreecommitdiff
path: root/yapf
diff options
context:
space:
mode:
authorrubidium <rubidium@openttd.org>2007-01-02 19:19:48 +0000
committerrubidium <rubidium@openttd.org>2007-01-02 19:19:48 +0000
commit66bbf336c6af7353ef0aeed58002c46543b30635 (patch)
treead4a63860df2626b22f77e7dac712e958bea54cb /yapf
parentccc0a3f4dbf58c005b22341ac8874252924690cd (diff)
downloadopenttd-66bbf336c6af7353ef0aeed58002c46543b30635.tar.xz
(svn r7759) -Merge: makefile rewrite. This merge features:
- A proper ./configure, so everything needs to be configured only once, not for every make. - Usage of makedepend when available. This greatly reduces the time needed for generating the dependencies. - A generator for all project files. There is a single file with sources, which is used to generate Makefiles and the project files for MSVC. - Proper support for OSX universal binaries. - Object files for non-MSVC compiles are also placed in separate directories, making is faster to switch between debug and release compiles and it does not touch the directory with the source files. - Functionality to make a bundle of all needed files for for example a nightly or distribution of a binary with all needed GRFs and language files. Note: as this merge moves almost all files, it is recommended to make a backup of your working copy before updating your working copy.
Diffstat (limited to 'yapf')
-rw-r--r--yapf/array.hpp71
-rw-r--r--yapf/autocopyptr.hpp83
-rw-r--r--yapf/binaryheap.hpp225
-rw-r--r--yapf/blob.hpp342
-rw-r--r--yapf/countedptr.hpp100
-rw-r--r--yapf/crc32.hpp65
-rw-r--r--yapf/fixedsizearray.hpp99
-rw-r--r--yapf/follow_track.cpp47
-rw-r--r--yapf/follow_track.hpp279
-rw-r--r--yapf/hashtable.hpp240
-rw-r--r--yapf/nodelist.hpp130
-rw-r--r--yapf/track_dir.hpp35
-rw-r--r--yapf/yapf.h120
-rw-r--r--yapf/yapf.hpp93
-rw-r--r--yapf/yapf_base.hpp331
-rw-r--r--yapf/yapf_common.cpp29
-rw-r--r--yapf/yapf_common.hpp163
-rw-r--r--yapf/yapf_costbase.hpp37
-rw-r--r--yapf/yapf_costcache.hpp196
-rw-r--r--yapf/yapf_costrail.hpp381
-rw-r--r--yapf/yapf_destrail.hpp149
-rw-r--r--yapf/yapf_node.hpp77
-rw-r--r--yapf/yapf_node_rail.hpp113
-rw-r--r--yapf/yapf_node_road.hpp36
-rw-r--r--yapf/yapf_rail.cpp277
-rw-r--r--yapf/yapf_road.cpp451
-rw-r--r--yapf/yapf_settings.h68
-rw-r--r--yapf/yapf_ship.cpp176
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;
-}