1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
/* $Id$ */
/*
* This file is part of OpenTTD.
* OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
* OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
*/
/** @file nodelist.hpp List of nodes used for the A-star pathfinder. */
#ifndef NODELIST_HPP
#define NODELIST_HPP
#include "../../misc/array.hpp"
#include "../../misc/hashtable.hpp"
#include "../../misc/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 SmallArray<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.AppendC();
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.Length();}
FORCEINLINE Titem_& ItemAt(int idx) {return m_arr[idx];}
template <class D> void Dump(D &dmp) const
{
dmp.WriteStructT("m_arr", &m_arr);
}
};
#endif /* NODELIST_HPP */
|
