Subversion Repository Public Repository

Divide-Framework

This repository has no backups
This repository's network speed is throttled to 100KB/sec

Diff Revisions 336 vs 337 for /trunk/Source Code/Libs/src/ReCast/DetourCrowd/Source/DetourProximityGrid.cpp

Diff revisions: vs.
  @@ -27,168 +27,168 @@
27 27
28 28 dtProximityGrid* dtAllocProximityGrid()
29 29 {
30 - void* mem = dtAlloc(sizeof(dtProximityGrid), DT_ALLOC_PERM);
31 - if (!mem) return 0;
32 - return new(mem) dtProximityGrid;
30 + void* mem = dtAlloc(sizeof(dtProximityGrid), DT_ALLOC_PERM);
31 + if (!mem) return 0;
32 + return new(mem) dtProximityGrid;
33 33 }
34 34
35 35 void dtFreeProximityGrid(dtProximityGrid* ptr)
36 36 {
37 - if (!ptr) return;
38 - ptr->~dtProximityGrid();
39 - dtFree(ptr);
37 + if (!ptr) return;
38 + ptr->~dtProximityGrid();
39 + dtFree(ptr);
40 40 }
41 41
42 42
43 43 inline int hashPos2(int x, int y, int n)
44 44 {
45 - return ((x*73856093) ^ (y*19349663)) & (n-1);
45 + return ((x*73856093) ^ (y*19349663)) & (n-1);
46 46 }
47 47
48 48
49 49 dtProximityGrid::dtProximityGrid() :
50 - m_maxItems(0),
51 - m_cellSize(0),
52 - m_pool(0),
53 - m_poolHead(0),
54 - m_poolSize(0),
55 - m_buckets(0),
56 - m_bucketsSize(0)
50 + m_maxItems(0),
51 + m_cellSize(0),
52 + m_pool(0),
53 + m_poolHead(0),
54 + m_poolSize(0),
55 + m_buckets(0),
56 + m_bucketsSize(0)
57 57 {
58 58 }
59 59
60 60 dtProximityGrid::~dtProximityGrid()
61 61 {
62 - dtFree(m_buckets);
63 - dtFree(m_pool);
62 + dtFree(m_buckets);
63 + dtFree(m_pool);
64 64 }
65 65
66 66 bool dtProximityGrid::init(const int poolSize, const float cellSize)
67 67 {
68 - dtAssert(poolSize > 0);
69 - dtAssert(cellSize > 0.0f);
70 -
71 - m_cellSize = cellSize;
72 - m_invCellSize = 1.0f / m_cellSize;
73 -
74 - // Allocate hashs buckets
75 - m_bucketsSize = dtNextPow2(poolSize);
76 - m_buckets = (unsigned short*)dtAlloc(sizeof(unsigned short)*m_bucketsSize, DT_ALLOC_PERM);
77 - if (!m_buckets)
78 - return false;
79 -
80 - // Allocate pool of items.
81 - m_poolSize = poolSize;
82 - m_poolHead = 0;
83 - m_pool = (Item*)dtAlloc(sizeof(Item)*m_poolSize, DT_ALLOC_PERM);
84 - if (!m_pool)
85 - return false;
86 -
87 - clear();
88 -
89 - return true;
68 + dtAssert(poolSize > 0);
69 + dtAssert(cellSize > 0.0f);
70 +
71 + m_cellSize = cellSize;
72 + m_invCellSize = 1.0f / m_cellSize;
73 +
74 + // Allocate hashs buckets
75 + m_bucketsSize = dtNextPow2(poolSize);
76 + m_buckets = (unsigned short*)dtAlloc(sizeof(unsigned short)*m_bucketsSize, DT_ALLOC_PERM);
77 + if (!m_buckets)
78 + return false;
79 +
80 + // Allocate pool of items.
81 + m_poolSize = poolSize;
82 + m_poolHead = 0;
83 + m_pool = (Item*)dtAlloc(sizeof(Item)*m_poolSize, DT_ALLOC_PERM);
84 + if (!m_pool)
85 + return false;
86 +
87 + clear();
88 +
89 + return true;
90 90 }
91 91
92 92 void dtProximityGrid::clear()
93 93 {
94 - memset(m_buckets, 0xff, sizeof(unsigned short)*m_bucketsSize);
95 - m_poolHead = 0;
96 - m_bounds[0] = 0xffff;
97 - m_bounds[1] = 0xffff;
98 - m_bounds[2] = -0xffff;
99 - m_bounds[3] = -0xffff;
94 + memset(m_buckets, 0xff, sizeof(unsigned short)*m_bucketsSize);
95 + m_poolHead = 0;
96 + m_bounds[0] = 0xffff;
97 + m_bounds[1] = 0xffff;
98 + m_bounds[2] = -0xffff;
99 + m_bounds[3] = -0xffff;
100 100 }
101 101
102 102 void dtProximityGrid::addItem(const unsigned short id,
103 - const float minx, const float miny,
104 - const float maxx, const float maxy)
103 + const float minx, const float miny,
104 + const float maxx, const float maxy)
105 105 {
106 - const int iminx = (int)dtMathFloorf(minx * m_invCellSize);
107 - const int iminy = (int)dtMathFloorf(miny * m_invCellSize);
108 - const int imaxx = (int)dtMathFloorf(maxx * m_invCellSize);
109 - const int imaxy = (int)dtMathFloorf(maxy * m_invCellSize);
110 -
111 - m_bounds[0] = dtMin(m_bounds[0], iminx);
112 - m_bounds[1] = dtMin(m_bounds[1], iminy);
113 - m_bounds[2] = dtMax(m_bounds[2], imaxx);
114 - m_bounds[3] = dtMax(m_bounds[3], imaxy);
115 -
116 - for (int y = iminy; y <= imaxy; ++y)
117 - {
118 - for (int x = iminx; x <= imaxx; ++x)
119 - {
120 - if (m_poolHead < m_poolSize)
121 - {
122 - const int h = hashPos2(x, y, m_bucketsSize);
123 - const unsigned short idx = (unsigned short)m_poolHead;
124 - m_poolHead++;
125 - Item& item = m_pool[idx];
126 - item.x = (short)x;
127 - item.y = (short)y;
128 - item.id = id;
129 - item.next = m_buckets[h];
130 - m_buckets[h] = idx;
131 - }
132 - }
133 - }
106 + const int iminx = (int)dtMathFloorf(minx * m_invCellSize);
107 + const int iminy = (int)dtMathFloorf(miny * m_invCellSize);
108 + const int imaxx = (int)dtMathFloorf(maxx * m_invCellSize);
109 + const int imaxy = (int)dtMathFloorf(maxy * m_invCellSize);
110 +
111 + m_bounds[0] = dtMin(m_bounds[0], iminx);
112 + m_bounds[1] = dtMin(m_bounds[1], iminy);
113 + m_bounds[2] = dtMax(m_bounds[2], imaxx);
114 + m_bounds[3] = dtMax(m_bounds[3], imaxy);
115 +
116 + for (int y = iminy; y <= imaxy; ++y)
117 + {
118 + for (int x = iminx; x <= imaxx; ++x)
119 + {
120 + if (m_poolHead < m_poolSize)
121 + {
122 + const int h = hashPos2(x, y, m_bucketsSize);
123 + const unsigned short idx = (unsigned short)m_poolHead;
124 + m_poolHead++;
125 + Item& item = m_pool[idx];
126 + item.x = (short)x;
127 + item.y = (short)y;
128 + item.id = id;
129 + item.next = m_buckets[h];
130 + m_buckets[h] = idx;
131 + }
132 + }
133 + }
134 134 }
135 135
136 136 int dtProximityGrid::queryItems(const float minx, const float miny,
137 - const float maxx, const float maxy,
138 - unsigned short* ids, const int maxIds) const
137 + const float maxx, const float maxy,
138 + unsigned short* ids, const int maxIds) const
139 139 {
140 - const int iminx = (int)dtMathFloorf(minx * m_invCellSize);
141 - const int iminy = (int)dtMathFloorf(miny * m_invCellSize);
142 - const int imaxx = (int)dtMathFloorf(maxx * m_invCellSize);
143 - const int imaxy = (int)dtMathFloorf(maxy * m_invCellSize);
144 -
145 - int n = 0;
146 -
147 - for (int y = iminy; y <= imaxy; ++y)
148 - {
149 - for (int x = iminx; x <= imaxx; ++x)
150 - {
151 - const int h = hashPos2(x, y, m_bucketsSize);
152 - unsigned short idx = m_buckets[h];
153 - while (idx != 0xffff)
154 - {
155 - Item& item = m_pool[idx];
156 - if ((int)item.x == x && (int)item.y == y)
157 - {
158 - // Check if the id exists already.
159 - const unsigned short* end = ids + n;
160 - unsigned short* i = ids;
161 - while (i != end && *i != item.id)
162 - ++i;
163 - // Item not found, add it.
164 - if (i == end)
165 - {
166 - if (n >= maxIds)
167 - return n;
168 - ids[n++] = item.id;
169 - }
170 - }
171 - idx = item.next;
172 - }
173 - }
174 - }
175 -
176 - return n;
140 + const int iminx = (int)dtMathFloorf(minx * m_invCellSize);
141 + const int iminy = (int)dtMathFloorf(miny * m_invCellSize);
142 + const int imaxx = (int)dtMathFloorf(maxx * m_invCellSize);
143 + const int imaxy = (int)dtMathFloorf(maxy * m_invCellSize);
144 +
145 + int n = 0;
146 +
147 + for (int y = iminy; y <= imaxy; ++y)
148 + {
149 + for (int x = iminx; x <= imaxx; ++x)
150 + {
151 + const int h = hashPos2(x, y, m_bucketsSize);
152 + unsigned short idx = m_buckets[h];
153 + while (idx != 0xffff)
154 + {
155 + Item& item = m_pool[idx];
156 + if ((int)item.x == x && (int)item.y == y)
157 + {
158 + // Check if the id exists already.
159 + const unsigned short* end = ids + n;
160 + unsigned short* i = ids;
161 + while (i != end && *i != item.id)
162 + ++i;
163 + // Item not found, add it.
164 + if (i == end)
165 + {
166 + if (n >= maxIds)
167 + return n;
168 + ids[n++] = item.id;
169 + }
170 + }
171 + idx = item.next;
172 + }
173 + }
174 + }
175 +
176 + return n;
177 177 }
178 178
179 179 int dtProximityGrid::getItemCountAt(const int x, const int y) const
180 180 {
181 - int n = 0;
182 -
183 - const int h = hashPos2(x, y, m_bucketsSize);
184 - unsigned short idx = m_buckets[h];
185 - while (idx != 0xffff)
186 - {
187 - Item& item = m_pool[idx];
188 - if ((int)item.x == x && (int)item.y == y)
189 - n++;
190 - idx = item.next;
191 - }
192 -
193 - return n;
181 + int n = 0;
182 +
183 + const int h = hashPos2(x, y, m_bucketsSize);
184 + unsigned short idx = m_buckets[h];
185 + while (idx != 0xffff)
186 + {
187 + Item& item = m_pool[idx];
188 + if ((int)item.x == x && (int)item.y == y)
189 + n++;
190 + idx = item.next;
191 + }
192 +
193 + return n;
194 194 }