Context Navigation

← Previous Revision
Next Revision →
Blame
Revision Log

test_HierPathfinder.h

Last change on this file was 27965, checked in by Vladislav Belov, 13 months ago

Revert non-ASCII characters from source and configuration files introduced in rP27786.

Differential Revision: https://code.wildfiregames.com/D5185

Property svn:eol-style set to native

File size: 20.0 KB

Line
1	/* Copyright (C) 2020 Wildfire Games.
2	* This file is part of 0 A.D.
3	*
4	* 0 A.D. is free software: you can redistribute it and/or modify
5	* it under the terms of the GNU General Public License as published by
6	* the Free Software Foundation, either version 2 of the License, or
7	* (at your option) any later version.
8	*
9	* 0 A.D. is distributed in the hope that it will be useful,
10	* but WITHOUT ANY WARRANTY; without even the implied warranty of
11	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12	* GNU General Public License for more details.
13	*
14	* You should have received a copy of the GNU General Public License
15	* along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
16	*/
17
18	#include "simulation2/system/ComponentTest.h"
19
20	#define TEST
21
22	#include "maths/Vector2D.h"
23	#include "simulation2/helpers/Grid.h"
24	#include "simulation2/helpers/HierarchicalPathfinder.h"
25
26	class TestHierarchicalPathfinder : public CxxTest::TestSuite
27	{
28	public:
29	void setUp()
30	{
31	}
32
33	void tearDown()
34	{
35	}
36
37	const pass_class_t PASS_1 = 1;
38	const pass_class_t PASS_2 = 2;
39	const pass_class_t NON_PASS_1 = 4;
40
41	const u16 mapSize = 240;
42
43	std::map<std::string, pass_class_t> pathClassMask;
44	std::map<std::string, pass_class_t> nonPathClassMask;
45
46	void debug_grid(Grid<NavcellData>& grid)
47	{
48	for (size_t i = 0; i < grid.m_W; ++i)
49	{
50	for (size_t j = 0; j < grid.m_H; ++j)
51	printf("%i", grid.get(i, j));
52	printf("\n");
53	}
54	}
55
56	void debug_grid_points(Grid<NavcellData>& grid, u16 i1, u16 j1, u16 i2, u16 j2)
57	{
58	for (size_t i = 0; i < grid.m_W; ++i)
59	{
60	for (size_t j = 0; j < grid.m_H; ++j)
61	{
62	if (i == i1 && j == j1)
63	printf("A");
64	else if (i == i2 && j == j2)
65	printf("B");
66	else
67	printf("%i", grid.get(i, j));
68	}
69	printf("\n");
70	}
71	}
72
73	void assert_blank(HierarchicalPathfinder& hierPath)
74	{
75	// test that the map has the same global region everywhere
76	HierarchicalPathfinder::GlobalRegionID globalRegionID = hierPath.GetGlobalRegion(35, 23, PASS_1);
77	for (u16 i = 0; i < mapSize; ++i)
78	for (u16 j = 0; j < mapSize; ++j)
79	{
80	TS_ASSERT(globalRegionID == hierPath.GetGlobalRegion(i, j, PASS_1));
81	TS_ASSERT(hierPath.GetGlobalRegion(i, j, PASS_2) == 0);
82	}
83
84	u16 i = 89;
85	u16 j = 34;
86	hierPath.FindNearestPassableNavcell(i, j, PASS_1);
87	TS_ASSERT(i == 89 && j == 34);
88
89	for (auto& chunk : hierPath.m_Chunks[PASS_1])
90	TS_ASSERT(chunk.m_RegionsID.size() == 1);
91
92	// number of connected regions: 4 in the middle, 2 in the corners.
93	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(120, 120, PASS_1)].size() == 4);
94	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(20, 20, PASS_1)].size() == 2);
95	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(220, 220, PASS_1)].size() == 2);
96
97	std::set<HierarchicalPathfinder::RegionID> reachables;
98	hierPath.FindReachableRegions(hierPath.Get(120, 120, PASS_1), reachables, PASS_1);
99	TS_ASSERT(reachables.size() == 9);
100	reachables.clear();
101	hierPath.FindReachableRegions(hierPath.Get(20, 20, PASS_1), reachables, PASS_1);
102	TS_ASSERT(reachables.size() == 9);
103	}
104
105	void test_reachability_and_update()
106	{
107	pathClassMask = std::map<std::string, pass_class_t> {
108	{ "1", 1 },
109	{ "2", 2 },
110	};
111	nonPathClassMask = std::map<std::string, pass_class_t> {
112	{ "3", 4 }
113	};
114
115	HierarchicalPathfinder hierPath;
116	Grid<NavcellData> grid(mapSize, mapSize);
117	Grid<u8> dirtyGrid(mapSize, mapSize);
118
119	// Entirely passable for PASS_1, not for others;
120	for (size_t i = 0; i < mapSize; ++i)
121	for (size_t j = 0; j < mapSize; ++j)
122	grid.set(i, j, 6);
123
124	hierPath.Recompute(&grid, nonPathClassMask, pathClassMask);
125
126	assert_blank(hierPath);
127
128	//////////////////////////////////////////////////////
129	// Split the map in two in the middle.
130	for (u16 j = 0; j < mapSize; ++j)
131	{
132	grid.set(125, j, 7);
133	dirtyGrid.set(125, j, 1);
134	}
135
136	hierPath.Update(&grid, dirtyGrid);
137
138	// Global region: check we are now split in two.
139	TS_ASSERT(hierPath.GetGlobalRegion(50, 50, PASS_1) != hierPath.GetGlobalRegion(150, 50, PASS_1));
140	for (u16 j = 0; j < mapSize; ++j)
141	{
142	TS_ASSERT(hierPath.Get(125, j, PASS_1).r == 0);
143	TS_ASSERT(hierPath.GetGlobalRegion(125, j, PASS_1) == 0);
144	}
145	for (u16 i = 0; i < 125; ++i)
146	for (u16 j = 0; j < mapSize; ++j)
147	{
148	TS_ASSERT(hierPath.GetGlobalRegion(50, 50, PASS_1) == hierPath.GetGlobalRegion(i, j, PASS_1));
149	TS_ASSERT(hierPath.GetGlobalRegion(i, j, PASS_2) == 0);
150	}
151	for (u16 i = 126; i < mapSize; ++i)
152	for (u16 j = 0; j < mapSize; ++j)
153	{
154	TS_ASSERT(hierPath.GetGlobalRegion(150, 50, PASS_1) == hierPath.GetGlobalRegion(i, j, PASS_1));
155	TS_ASSERT(hierPath.GetGlobalRegion(i, j, PASS_2) == 0);
156	}
157
158	// number of connected regions: 3 in the middle (both sides), 2 in the corners.
159	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(120, 120, PASS_1)].size() == 3);
160	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(170, 120, PASS_1)].size() == 3);
161	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(20, 20, PASS_1)].size() == 2);
162	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(220, 220, PASS_1)].size() == 2);
163
164	std::set<HierarchicalPathfinder::RegionID> reachables;
165	hierPath.FindReachableRegions(hierPath.Get(120, 120, PASS_1), reachables, PASS_1);
166	TS_ASSERT(reachables.size() == 6);
167	reachables.clear();
168	hierPath.FindReachableRegions(hierPath.Get(170, 120, PASS_1), reachables, PASS_1);
169	TS_ASSERT(reachables.size() == 6);
170
171	//////////////////////////////////////////////////////
172	// Un-split the map in two in the middle.
173	for (u16 j = 0; j < mapSize; ++j)
174	{
175	grid.set(125, j, 6);
176	dirtyGrid.set(125, j, 1);
177	}
178	hierPath.Update(&grid, dirtyGrid);
179	assert_blank(hierPath);
180
181	//////////////////////////////////////////////////////
182	// Partial split in the middle chunk - no actual connectivity change
183	for (u16 j = 120; j < 150; ++j)
184	{
185	grid.set(125, j, 7);
186	dirtyGrid.set(125, j, 1);
187	}
188	hierPath.Update(&grid, dirtyGrid);
189	reachables.clear();
190	hierPath.FindReachableRegions(hierPath.Get(170, 120, PASS_1), reachables, PASS_1);
191	TS_ASSERT(reachables.size() == 9);
192	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(170, 120, PASS_1)].size() == 4);
193
194	//////////////////////////////////////////////////////
195	// Block a strip along the edge, but regions are still connected.
196	for (u16 j = 70; j < 200; ++j)
197	{
198	grid.set(96, j, 7);
199	dirtyGrid.set(96, j, 1);
200	}
201	hierPath.Update(&grid, dirtyGrid);
202	reachables.clear();
203	hierPath.FindReachableRegions(hierPath.Get(170, 120, PASS_1), reachables, PASS_1);
204	TS_ASSERT(reachables.size() == 9);
205	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(20, 120, PASS_1)].size() == 2);
206	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(170, 120, PASS_1)].size() == 3);
207	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(200, 120, PASS_1)].size() == 3);
208
209	//////////////////////////////////////////////////////
210	// Block the other edge
211	for (u16 j = 70; j < 200; ++j)
212	{
213	grid.set(192, j, 7);
214	dirtyGrid.set(192, j, 1);
215	}
216	hierPath.Update(&grid, dirtyGrid);
217	reachables.clear();
218	hierPath.FindReachableRegions(hierPath.Get(170, 120, PASS_1), reachables, PASS_1);
219	TS_ASSERT(reachables.size() == 9);
220	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(20, 120, PASS_1)].size() == 2);
221	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(170, 120, PASS_1)].size() == 2);
222	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(200, 120, PASS_1)].size() == 2);
223
224	//////////////////////////////////////////////////////
225	// Create an isolated region in the middle chunk
226	for (u16 i = 96; i < 140; ++i)
227	{
228	grid.set(i, 110, 7);
229	dirtyGrid.set(i, 110, 1);
230	}
231	for (u16 i = 96; i < 140; ++i)
232	{
233	grid.set(i, 140, 7);
234	dirtyGrid.set(i, 140, 1);
235	}
236	for (u16 j = 110; j < 141; ++j)
237	{
238	grid.set(140, j, 7);
239	dirtyGrid.set(140, j, 1);
240	}
241	hierPath.Update(&grid, dirtyGrid);
242
243	TS_ASSERT(hierPath.GetGlobalRegion(120, 120, PASS_1) != hierPath.GetGlobalRegion(150, 50, PASS_1));
244
245	reachables.clear();
246	hierPath.FindReachableRegions(hierPath.Get(170, 120, PASS_1), reachables, PASS_1);
247	TS_ASSERT(reachables.size() == 9);
248	reachables.clear();
249	hierPath.FindReachableRegions(hierPath.Get(120, 120, PASS_1), reachables, PASS_1);
250	TS_ASSERT(reachables.size() == 1);
251	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(120, 120, PASS_1)].size() == 0);
252	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(20, 120, PASS_1)].size() == 2);
253	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(170, 120, PASS_1)].size() == 2);
254	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(200, 120, PASS_1)].size() == 2);
255
256	//////////////////////////////////////////////////////
257	// Open it
258	for (u16 j = 110; j < 141; ++j)
259	{
260	grid.set(140, j, 6);
261	dirtyGrid.set(140, j, 1);
262	}
263	hierPath.Update(&grid, dirtyGrid);
264
265	TS_ASSERT(hierPath.GetGlobalRegion(120, 120, PASS_1) == hierPath.GetGlobalRegion(150, 50, PASS_1));
266	reachables.clear();
267	hierPath.FindReachableRegions(hierPath.Get(170, 120, PASS_1), reachables, PASS_1);
268	TS_ASSERT(reachables.size() == 9);
269	reachables.clear();
270	hierPath.FindReachableRegions(hierPath.Get(120, 120, PASS_1), reachables, PASS_1);
271	TS_ASSERT(reachables.size() == 9);
272	TS_ASSERT(hierPath.m_Edges[PASS_1][hierPath.Get(120, 120, PASS_1)].size() == 2);
273	}
274
275	u16 manhattan(u16 i, u16 j, u16 gi, u16 gj)
276	{
277	return abs(i - gi) + abs(j - gj);
278	}
279
280	double euclidian(u16 i, u16 j, u16 gi, u16 gj)
281	{
282	return sqrt((i - gi) * (i - gi) + (j - gj) * (j - gj));
283	}
284
285	void test_passability()
286	{
287	pathClassMask = std::map<std::string, pass_class_t> {
288	{ "1", 1 },
289	{ "2", 2 },
290	};
291	nonPathClassMask = std::map<std::string, pass_class_t> {
292	{ "3", 4 }
293	};
294
295	// 0 is passable, 1 is not.
296	// i is vertical, j is horizontal;
297	#define _ 0
298	#define X 1
299	NavcellData gridDef[40][40] = {
300	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
301	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
302	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
303	{_,_,_,_,X,X,X,X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
304	{_,_,_,_,X,X,X,X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,X,_,_,_,_,_,_,_,_,_,_,_,_,_},
305	{_,_,_,_,X,X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,X,_,_,_,_,_,_,_,_,_,_,_,_,_},
306	{_,_,_,_,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,X,_,_,_,_,_,_,_,_,_,_,_,_,_},
307	{_,_,_,_,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,X,_,_,_,_,_,_,_,_,_,_,_,_,_},
308	{_,_,_,_,X,X,X,X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,X,_,_,_,_,_,_,_,_,_,_,_,_,_},
309	{_,_,_,_,X,X,X,X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,X,_,X,X,X,X,_,_,_,_,_,_,_,_},
310	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,X,_,X,_,_,X,_,_,_,_,_,_,_,_},
311	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,X,_,X,_,_,_,_,_,_,_,_,_,_,_},
312	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,X,_,X,_,_,_,_,_,_,_,_,_,_,_},
313	{_,_,_,_,_,_,X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,X,_,X,_,_,_,_,_,_,_,_,_,_,_},
314	{_,_,_,_,_,_,X,X,X,_,_,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,X,_,X,_,_,_,_,_,_,_,_,_,_,_},
315	{_,_,_,_,_,_,X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,X,_,X,_,_,_,_,_,_,_,_,_,_,_},
316	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,X,_,X,_,_,_,_,_,_,_,_,_,_,_},
317	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,X,X,X,_,_,_,_,_,_,_,_,_,_,_},
318	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
319	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
320	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
321	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
322	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
323	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
324	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
325	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
326	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
327	{_,_,_,_,_,_,X,X,X,X,X,X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
328	{_,_,_,_,_,_,X,X,X,X,X,X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
329	{_,_,_,_,_,_,X,X,X,X,X,X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
330	{_,_,_,_,_,_,X,X,X,X,X,X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
331	{_,_,_,_,_,_,X,X,X,X,X,X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
332	{_,_,_,_,_,_,X,X,X,X,X,X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
333	{_,_,_,_,_,_,X,X,X,X,X,X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
334	{_,_,_,_,_,_,X,X,X,X,X,X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
335	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
336	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
337	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
338	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
339	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_}
340	};
341	#undef _
342	#undef X
343	// upscaled n times
344	const int scale = 6;
345
346	HierarchicalPathfinder hierPath;
347	Grid<NavcellData> grid(40scale, 40scale);
348	Grid<u8> dirtyGrid(40scale, 40scale);
349
350	for (size_t i = 0; i < 40; ++i)
351	for (size_t j = 0; j < 40; ++j)
352	for (size_t ii = 0; ii < scale; ++ii)
353	for (size_t jj = 0; jj < scale; ++jj)
354	grid.set(i * scale + ii, j * scale + jj, gridDef[i][j]);
355
356	hierPath.Recompute(&grid, nonPathClassMask, pathClassMask);
357
358	u16 i = 5, j = 5;
359	hierPath.FindNearestPassableNavcell(i, j, PASS_1);
360	TS_ASSERT(i == 5 && j == 5);
361
362	// use a macro so the lines reported by tests are accurate
363	#define check_closest_passable(i, j, expected_manhattan) \
364	oi = i; oj = j; \
365	pi = i; pj = j; \
366	TS_ASSERT(!IS_PASSABLE(grid.get(pi, pj), PASS_1)); \
367	hierPath.FindNearestPassableNavcell(pi, pj, PASS_1); \
368	\
369	if (expected_manhattan == -1) \
370	{ \
371	TS_ASSERT(oi == pi && oj == pj); \
372	} \
373	else \
374	{ \
375	TS_ASSERT(IS_PASSABLE(grid.get(pi, pj), PASS_1)); \
376	TS_ASSERT_EQUALS(manhattan(pi, pj, oi, oj), expected_manhattan); \
377	}
378	u16 oi, oj, pi, pj;
379
380	check_closest_passable(4 * scale, 4 * scale, 1);
381	check_closest_passable(4 * scale + 1, 4 * scale + 1, 2);
382	check_closest_passable(14 * scale + 2, 7 * scale + 2, 9);
383	check_closest_passable(14 * scale + 2, 7 * scale + 4, 8);
384	check_closest_passable(14 * scale + 2, 7 * scale + 5, 7);
385	check_closest_passable(14 * scale + 2, 7 * scale + 6, 6);
386	check_closest_passable(5 * scale + 3, 7 * scale + 2, 3);
387	#undef check_closest_passable
388
389	PathGoal goal;
390	goal.type = PathGoal::POINT;
391
392	// from the left of the C, goal is unreachable, expect closest navcell to goal
393	oi = 5 * scale + 3; oj = 3 * scale + 3;
394	pi = 5 * scale + 3; pj = 6 * scale + 2; goal.x = fixed::FromInt(pi); goal.z = fixed::FromInt(pj);
395
396	hierPath.MakeGoalReachable(oi, oj, goal, PASS_1);
397	hierPath.FindNearestPassableNavcell(pi, pj, PASS_1);
398	TS_ASSERT_EQUALS(pi, goal.x.ToInt_RoundToNegInfinity());
399	TS_ASSERT_EQUALS(pj, goal.z.ToInt_RoundToNegInfinity());
400
401	// random reachable point.
402	oi = 5 * scale + 3; oj = 3 * scale + 3;
403	pi = 26 * scale + 3; pj = 5 * scale + 2; goal.x = fixed::FromInt(pi) + fixed::FromInt(1)/3; goal.z = fixed::FromInt(pj) + fixed::FromInt(1)/3;
404	hierPath.MakeGoalReachable(oi, oj, goal, PASS_1);
405	TS_ASSERT(pi == goal.x.ToInt_RoundToNegInfinity() && pj == goal.z.ToInt_RoundToNegInfinity());
406
407	// top-left corner
408	goal.x = fixed::FromInt(pi); goal.z = fixed::FromInt(pj);
409	hierPath.MakeGoalReachable(oi, oj, goal, PASS_1);
410	TS_ASSERT(pi == goal.x.ToInt_RoundToNegInfinity() && pj == goal.z.ToInt_RoundToNegInfinity());
411
412	// near bottom-right corner
413	goal.x = fixed::FromInt(pi) + fixed::FromInt(3)/4; goal.z = fixed::FromInt(pj) + fixed::FromInt(3)/4;
414	hierPath.MakeGoalReachable(oi, oj, goal, PASS_1);
415	TS_ASSERT(pi == goal.x.ToInt_RoundToNegInfinity() && pj == goal.z.ToInt_RoundToNegInfinity());
416
417	// Circle
418	goal.type = PathGoal::CIRCLE;
419	goal.hw = fixed::FromInt(1) / 2;
420
421	// from the left of the C, goal is unreachable, expect closest navcell to goal
422	oi = 5 * scale + 3; oj = 3 * scale + 3;
423	pi = 5 * scale + 3; pj = 7 * scale + 2; goal.x = fixed::FromInt(pi); goal.z = fixed::FromInt(pj);
424	hierPath.MakeGoalReachable(oi, oj, goal, PASS_1);
425	hierPath.FindNearestPassableNavcell(pi, pj, PASS_1);
426	TS_ASSERT(pi == goal.x.ToInt_RoundToNegInfinity() && pj == goal.z.ToInt_RoundToNegInfinity());
427
428	// same position, goal is reachable, expect closest navcell to goal
429	goal.hw = fixed::FromInt(3);
430	goal.x = fixed::FromInt(pi); goal.z = fixed::FromInt(pj);
431	hierPath.MakeGoalReachable(oi, oj, goal, PASS_1);
432	hierPath.FindNearestPassableNavcell(pi, pj, PASS_1);
433	TS_ASSERT(pi == goal.x.ToInt_RoundToNegInfinity() && pj == goal.z.ToInt_RoundToNegInfinity());
434
435	// Same position, but goal is unreachable and much farther away.
436	goal.type = PathGoal::POINT;
437	oi = 5 * scale + 3; oj = 3 * scale + 3;
438	pi = 34 * scale + 3; pj = 6 * scale + 2; goal.x = fixed::FromInt(pi); goal.z = fixed::FromInt(pj);
439	hierPath.MakeGoalReachable(oi, oj, goal, PASS_1);
440	hierPath.FindNearestPassableNavcell(pi, pj, PASS_1);
441	TS_ASSERT_EQUALS(pi, goal.x.ToInt_RoundToNegInfinity())
442	TS_ASSERT_EQUALS(pj, goal.z.ToInt_RoundToNegInfinity());
443
444	// Square
445	goal.type = PathGoal::SQUARE;
446	goal.hw = fixed::FromInt(1) / 2;
447	goal.hh = fixed::FromInt(1) / 2;
448
449	// from the left of the C, goal is unreachable, expect closest navcell to goal
450	oi = 5 * scale + 3; oj = 3 * scale + 3;
451	pi = 5 * scale + 3; pj = 7 * scale + 2; goal.x = fixed::FromInt(pi); goal.z = fixed::FromInt(pj);
452	hierPath.MakeGoalReachable(oi, oj, goal, PASS_1);
453	hierPath.FindNearestPassableNavcell(pi, pj, PASS_1);
454	TS_ASSERT(pi == goal.x.ToInt_RoundToNegInfinity() && pj == goal.z.ToInt_RoundToNegInfinity());
455
456	// same position, goal is reachable, expect closest navcell to goal
457	goal.hw = fixed::FromInt(3);
458	goal.hh = fixed::FromInt(3);
459	goal.x = fixed::FromInt(pi); goal.z = fixed::FromInt(pj);
460	hierPath.MakeGoalReachable(oi, oj, goal, PASS_1);
461	hierPath.FindNearestPassableNavcell(pi, pj, PASS_1);
462	TS_ASSERT(pi == goal.x.ToInt_RoundToNegInfinity() && pj == goal.z.ToInt_RoundToNegInfinity());
463
464	// Goal is reachable diagonally (1 cell away)
465	goal.hw = fixed::FromInt(1);
466	goal.hh = fixed::FromInt(1);
467	oi = 5 * scale + 3; oj = 3 * scale + 3;
468	pi = 5 * scale - 1; pj = 7 * scale + 3; goal.x = fixed::FromInt(pi); goal.z = fixed::FromInt(pj);
469	hierPath.MakeGoalReachable(oi, oj, goal, PASS_1);
470	hierPath.FindNearestPassableNavcell(pi, pj, PASS_1);
471	TS_ASSERT(pi == goal.x.ToInt_RoundToNegInfinity() && pj == goal.z.ToInt_RoundToNegInfinity());
472
473	// Huge Circle goal, expect point closest to us.
474	goal.type = PathGoal::CIRCLE;
475	goal.hw = fixed::FromInt(20);
476
477	oi = 5 * scale + 3; oj = 3 * scale + 3;
478	pi = 36 * scale + 3; pj = 7 * scale + 2; goal.x = fixed::FromInt(pi); goal.z = fixed::FromInt(pj);
479
480	hierPath.MakeGoalReachable(oi, oj, goal, PASS_1);
481
482	// bit of leeway for cell placement
483	TS_ASSERT(std::fabs(euclidian(goal.x.ToInt_RoundToNegInfinity(), goal.z.ToInt_RoundToNegInfinity(), pi, pj)-20) < 1.5f);
484	TS_ASSERT(std::fabs(euclidian(goal.x.ToInt_RoundToNegInfinity(), goal.z.ToInt_RoundToNegInfinity(), oi, oj) - euclidian(pi, pj, oi, oj)) < 22.0f);
485	}
486
487	void test_regions_flood_fill()
488	{
489	// Partial test of region inner flood filling.
490	// This highlights that internal region IDs can become higher than the number of regions.
491	pathClassMask = std::map<std::string, pass_class_t> {
492	{ "1", 1 },
493	{ "2", 2 },
494	};
495	nonPathClassMask = std::map<std::string, pass_class_t> {
496	{ "3", 4 }
497	};
498
499	// 0 is passable, 1 is not.
500	// i is vertical, j is horizontal;
501	#define _ 0
502	#define X 1
503	NavcellData gridDef[5][5] = {
504	{X,_,X,_,_},
505	{_,_,X,X,_},
506	{X,_,X,_,_},
507	{_,_,X,X,_},
508	{X,_,X,_,_}
509	};
510	#undef _
511	#undef X
512	HierarchicalPathfinder hierPath;
513	Grid<NavcellData> grid(5, 5);
514	Grid<u8> dirtyGrid(5, 5);
515	for (size_t i = 0; i < 5; ++i)
516	for (size_t j = 0; j < 5; ++j)
517	grid.set(i, j, gridDef[i][j]);
518	hierPath.Recompute(&grid, nonPathClassMask, pathClassMask);
519
520	TS_ASSERT_EQUALS(hierPath.m_Chunks[pathClassMask["1"]][0].m_RegionsID.size(), 2);
521	TS_ASSERT_EQUALS(hierPath.m_Chunks[pathClassMask["1"]][0].m_RegionsID.back(), 4);
522	}
523	};

Note: See TracBrowser for help on using the repository browser.

This Trac instance is not used for development anymore!

Context Navigation

source: ps/trunk/source/simulation2/components/tests/test_HierPathfinder.h

Download in other formats: