1 /*
2  Copyright (c) 2013 yvt
3  based on code of pysnip (c) Mathias Kaerlev 2011-2012.
4 
5  This file is part of OpenSpades.
6 
7  OpenSpades is free software: you can redistribute it and/or modify
8  it under the terms of the GNU General Public License as published by
9  the Free Software Foundation, either version 3 of the License, or
10  (at your option) any later version.
11 
12  OpenSpades is distributed in the hope that it will be useful,
13  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  GNU General Public License for more details.
16 
17  You should have received a copy of the GNU General Public License
18  along with OpenSpades.  If not, see <http://www.gnu.org/licenses/>.
19 
20  */
21 
22 #include <algorithm>
23 #include <cmath>
24 #include <cstdlib>
25 #include <vector>
26 
27 #include "GameMap.h"
28 #include <Core/AutoLocker.h>
29 #include <Core/Debug.h>
30 #include <Core/Exception.h>
31 #include <Core/FileManager.h>
32 #include <Core/IStream.h>
33 
34 namespace spades {
35 	namespace client {
36 
GameMap()37 		GameMap::GameMap() {
38 			SPADES_MARK_FUNCTION();
39 
40 			for (int x = 0; x < DefaultWidth; x++)
41 				for (int y = 0; y < DefaultHeight; y++) {
42 					solidMap[x][y] = 1; // ground only
43 					for (int z = 0; z < DefaultDepth; z++) {
44 						uint32_t col = 0x00284067;
45 						col ^= 0x070707 & static_cast<uint32_t>(SampleRandom());
46 						colorMap[x][y][z] = col + (100UL * 0x1000000UL);
47 					}
48 				}
49 		}
~GameMap()50 		GameMap::~GameMap() { SPADES_MARK_FUNCTION(); }
51 
AddListener(spades::client::IGameMapListener * l)52 		void GameMap::AddListener(spades::client::IGameMapListener *l) {
53 			AutoLocker guard(&listenersMutex);
54 			listeners.push_back(l);
55 		}
56 
RemoveListener(spades::client::IGameMapListener * l)57 		void GameMap::RemoveListener(spades::client::IGameMapListener *l) {
58 			AutoLocker guard(&listenersMutex);
59 			auto it = std::find(listeners.begin(), listeners.end(), l);
60 			if (it != listeners.end()) {
61 				listeners.erase(it);
62 			}
63 		}
64 
IsSurface(int x,int y,int z)65 		bool GameMap::IsSurface(int x, int y, int z) {
66 			if (!IsSolid(x, y, z))
67 				return false;
68 			if (z == 0)
69 				return true;
70 			if (x > 0 && !IsSolid(x - 1, y, z))
71 				return true;
72 			if (x < Width() - 1 && !IsSolid(x + 1, y, z))
73 				return true;
74 			if (y > 0 && !IsSolid(x, y - 1, z))
75 				return true;
76 			if (y < Height() - 1 && !IsSolid(x, y + 1, z))
77 				return true;
78 			if (!IsSolid(x, y, z - 1))
79 				return true;
80 			if (z < Depth() - 1 && !IsSolid(x, y, z + 1))
81 				return true;
82 			return false;
83 		}
84 
WriteColor(std::vector<char> & buffer,int color)85 		static void WriteColor(std::vector<char> &buffer, int color) {
86 			buffer.push_back((char)(color >> 16));
87 			buffer.push_back((char)(color >> 8));
88 			buffer.push_back((char)(color >> 0));
89 			buffer.push_back((char)(color >> 24));
90 		}
91 
92 		// base on pysnip
Save(spades::IStream * stream)93 		void GameMap::Save(spades::IStream *stream) {
94 			int w = Width();
95 			int h = Height();
96 			int d = Depth();
97 			std::vector<char> buffer;
98 			buffer.reserve(10 * 1024 * 1024);
99 			for (int y = 0; y < h; y++) {
100 				for (int x = 0; x < w; x++) {
101 					int k = 0;
102 					while (k < d) {
103 						int z;
104 
105 						int air_start;
106 						int top_colors_start;
107 						int top_colors_end; // exclusive
108 						int bottom_colors_start;
109 						int bottom_colors_end; // exclusive
110 						int top_colors_len;
111 						int bottom_colors_len;
112 						int colors;
113 						air_start = k;
114 						while (k < d && !IsSolid(x, y, k))
115 							++k;
116 						top_colors_start = k;
117 						while (k < d && IsSurface(x, y, k))
118 							++k;
119 						top_colors_end = k;
120 
121 						while (k < d && IsSolid(x, y, k) && !IsSurface(x, y, k))
122 							++k;
123 
124 						bottom_colors_start = k;
125 
126 						z = k;
127 						while (z < d && IsSurface(x, y, z))
128 							++z;
129 
130 						if (z != d) {
131 							while (IsSurface(x, y, k))
132 								++k;
133 						}
134 						bottom_colors_end = k;
135 
136 						top_colors_len = top_colors_end - top_colors_start;
137 						bottom_colors_len = bottom_colors_end - bottom_colors_start;
138 
139 						colors = top_colors_len + bottom_colors_len;
140 
141 						if (k == d) {
142 							buffer.push_back(0);
143 						} else {
144 							buffer.push_back(colors + 1);
145 						}
146 						buffer.push_back(top_colors_start);
147 						buffer.push_back(top_colors_end - 1);
148 						buffer.push_back(air_start);
149 
150 						for (z = 0; z < top_colors_len; ++z) {
151 							WriteColor(buffer, GetColor(x, y, top_colors_start + z));
152 						}
153 						for (z = 0; z < bottom_colors_len; ++z) {
154 							WriteColor(buffer, GetColor(x, y, bottom_colors_start + z));
155 						}
156 					}
157 				}
158 			}
159 			stream->Write(buffer.data(), buffer.size());
160 		}
161 
ClipBox(int x,int y,int z)162 		bool GameMap::ClipBox(int x, int y, int z) {
163 			int sz;
164 
165 			if (x < 0 || x >= 512 || y < 0 || y >= 512)
166 				return true;
167 			else if (z < 0)
168 				return false;
169 			sz = (int)z;
170 			if (sz == 63)
171 				sz = 62;
172 			else if (sz >= 64)
173 				return true;
174 			return IsSolid((int)x, (int)y, sz);
175 		}
176 
ClipWorld(int x,int y,int z)177 		bool GameMap::ClipWorld(int x, int y, int z) {
178 			int sz;
179 
180 			if (x < 0 || x >= 512 || y < 0 || y >= 512)
181 				return 0;
182 			if (z < 0)
183 				return 0;
184 			sz = (int)z;
185 			if (sz == 63)
186 				sz = 62;
187 			else if (sz >= 63)
188 				return 1;
189 			else if (sz < 0)
190 				return 0;
191 			return IsSolid((int)x, (int)y, sz);
192 		}
193 
ClipBox(float x,float y,float z)194 		bool GameMap::ClipBox(float x, float y, float z) {
195 			SPAssert(!std::isnan(x));
196 			SPAssert(!std::isnan(y));
197 			SPAssert(!std::isnan(z));
198 			return ClipBox((int)floorf(x), (int)floorf(y), (int)floorf(z));
199 		}
200 
ClipWorld(float x,float y,float z)201 		bool GameMap::ClipWorld(float x, float y, float z) {
202 			SPAssert(!std::isnan(x));
203 			SPAssert(!std::isnan(y));
204 			SPAssert(!std::isnan(z));
205 			return ClipWorld((int)floorf(x), (int)floorf(y), (int)floorf(z));
206 		}
207 
CastRay(spades::Vector3 v0,spades::Vector3 v1,float length,spades::IntVector3 & vOut)208 		bool GameMap::CastRay(spades::Vector3 v0, spades::Vector3 v1, float length,
209 		                      spades::IntVector3 &vOut) {
210 			SPADES_MARK_FUNCTION_DEBUG();
211 
212 			SPAssert(!std::isnan(v0.x));
213 			SPAssert(!std::isnan(v0.y));
214 			SPAssert(!std::isnan(v0.z));
215 			SPAssert(!std::isnan(v1.x));
216 			SPAssert(!std::isnan(v1.y));
217 			SPAssert(!std::isnan(v1.z));
218 			SPAssert(!std::isnan(length));
219 
220 			v1 = v0 + v1 * length;
221 
222 			Vector3 f, g;
223 			IntVector3 a, c, d, p, i;
224 			long cnt = 0;
225 
226 			a = v0.Floor();
227 			c = v1.Floor();
228 
229 			if (c.x < a.x) {
230 				d.x = -1;
231 				f.x = v0.x - a.x;
232 				g.x = (v0.x - v1.x) * 1024;
233 				cnt += a.x - c.x;
234 			} else if (c.x != a.x) {
235 				d.x = 1;
236 				f.x = a.x + 1 - v0.x;
237 				g.x = (v1.x - v0.x) * 1024;
238 				cnt += c.x - a.x;
239 			} else {
240 				d.x = 0;
241 				f.x = g.x = 0;
242 			}
243 			if (c.y < a.y) {
244 				d.y = -1;
245 				f.y = v0.y - a.y;
246 				g.y = (v0.y - v1.y) * 1024;
247 				cnt += a.y - c.y;
248 			} else if (c.y != a.y) {
249 				d.y = 1;
250 				f.y = a.y + 1 - v0.y;
251 				g.y = (v1.y - v0.y) * 1024;
252 				cnt += c.y - a.y;
253 			} else {
254 				d.y = 0;
255 				f.y = g.y = 0;
256 			}
257 			if (c.z < a.z) {
258 				d.z = -1;
259 				f.z = v0.z - a.z;
260 				g.z = (v0.z - v1.z) * 1024;
261 				cnt += a.z - c.z;
262 			} else if (c.z != a.z) {
263 				d.z = 1;
264 				f.z = a.z + 1 - v0.z;
265 				g.z = (v1.z - v0.z) * 1024;
266 				cnt += c.z - a.z;
267 			} else {
268 				d.z = 0;
269 				f.z = g.z = 0;
270 			}
271 
272 			Vector3 pp =
273 			  MakeVector3(f.x * g.z - f.z * g.x, f.y * g.z - f.z * g.y, f.y * g.x - f.x * g.y);
274 			p = pp.Floor();
275 			i = g.Floor();
276 
277 			if (cnt > (long)length)
278 				cnt = (long)length;
279 
280 #if 1
281 			// faster version
282 			uint64_t lastSolidMap = solidMap[a.x & (DefaultWidth - 1)][a.y & (DefaultHeight - 1)];
283 			if (a.z < 0 && d.z < 0) {
284 				return false;
285 			} else if (a.z < 0) {
286 				while (cnt > 0 && a.z < 0) {
287 					if (((p.x | p.y) >= 0) && (a.z != c.z)) {
288 						a.z += d.z;
289 						p.x -= i.x;
290 						p.y -= i.y;
291 					} else if ((p.z >= 0) && (a.x != c.x)) {
292 						a.x += d.x;
293 						p.x += i.z;
294 						p.z -= i.y;
295 					} else {
296 						a.y += d.y;
297 						p.y += i.z;
298 						p.z += i.x;
299 					}
300 					cnt--;
301 				}
302 			} else if (a.z >= 64) {
303 				vOut = a;
304 				return true;
305 			}
306 			while (cnt > 0) {
307 				if (((p.x | p.y) >= 0) && (a.z != c.z)) {
308 					a.z += d.z;
309 					p.x -= i.x;
310 					p.y -= i.y;
311 					if (a.z < 0 && d.z < 0) {
312 						return false;
313 					} else if (a.z >= 64) {
314 						vOut = a;
315 						return true;
316 					}
317 				} else if ((p.z >= 0) && (a.x != c.x)) {
318 					a.x += d.x;
319 					p.x += i.z;
320 					p.z -= i.y;
321 					lastSolidMap = solidMap[a.x & (DefaultWidth - 1)][a.y & (DefaultHeight - 1)];
322 				} else {
323 					a.y += d.y;
324 					p.y += i.z;
325 					p.z += i.x;
326 					lastSolidMap = solidMap[a.x & (DefaultWidth - 1)][a.y & (DefaultHeight - 1)];
327 				}
328 
329 				if ((lastSolidMap >> (uint64_t)a.z) & 1ULL) {
330 					vOut = a;
331 					return true;
332 				}
333 				cnt--;
334 			}
335 #else
336 			while (cnt > 0) {
337 				if (((p.x | p.y) >= 0) && (a.z != c.z)) {
338 					a.z += d.z;
339 					p.x -= i.x;
340 					p.y -= i.y;
341 				} else if ((p.z >= 0) && (a.x != c.x)) {
342 					a.x += d.x;
343 					p.x += i.z;
344 					p.z -= i.y;
345 				} else {
346 					a.y += d.y;
347 					p.y += i.z;
348 					p.z += i.x;
349 				}
350 
351 				if (IsSolidWrapped(a.x, a.y, a.z)) {
352 					vOut = a;
353 					return true;
354 				}
355 				cnt--;
356 			}
357 #endif
358 			return false;
359 		}
360 
CastRay2(spades::Vector3 v0,spades::Vector3 dir,int maxSteps)361 		GameMap::RayCastResult GameMap::CastRay2(spades::Vector3 v0, spades::Vector3 dir,
362 		                                         int maxSteps) {
363 			SPADES_MARK_FUNCTION_DEBUG();
364 			GameMap::RayCastResult result;
365 
366 			SPAssert(!std::isnan(v0.x));
367 			SPAssert(!std::isnan(v0.y));
368 			SPAssert(!std::isnan(v0.z));
369 			SPAssert(!std::isnan(dir.x));
370 			SPAssert(!std::isnan(dir.y));
371 			SPAssert(!std::isnan(dir.z));
372 
373 			dir = dir.Normalize();
374 
375 			spades::IntVector3 iv = v0.Floor();
376 			spades::Vector3 fv;
377 			if (IsSolidWrapped(iv.x, iv.y, iv.z)) {
378 				result.hit = true;
379 				result.startSolid = true;
380 				result.hitPos = v0;
381 				result.hitBlock = iv;
382 				result.normal = IntVector3::Make(0, 0, 0);
383 				return result;
384 			}
385 
386 			if (dir.x > 0.f) {
387 				fv.x = (float)(iv.x + 1) - v0.x;
388 			} else {
389 				fv.x = v0.x - (float)iv.x;
390 			}
391 			if (dir.y > 0.f) {
392 				fv.y = (float)(iv.y + 1) - v0.y;
393 			} else {
394 				fv.y = v0.y - (float)iv.y;
395 			}
396 			if (dir.z > 0.f) {
397 				fv.z = (float)(iv.z + 1) - v0.z;
398 			} else {
399 				fv.z = v0.z - (float)iv.z;
400 			}
401 
402 			float invX = dir.x;
403 			float invY = dir.y;
404 			float invZ = dir.z;
405 
406 			if (invX != 0.f)
407 				invX = 1.f / fabsf(invX);
408 			if (invY != 0.f)
409 				invY = 1.f / fabsf(invY);
410 			if (invZ != 0.f)
411 				invZ = 1.f / fabsf(invZ);
412 
413 			for (int i = 0; i < maxSteps; i++) {
414 				IntVector3 nextBlock;
415 				int hasNextBlock = 0;
416 				float nextBlockTime = 0.f;
417 
418 				if (invX != 0.f) {
419 					nextBlock = iv;
420 					if (dir.x > 0.f)
421 						nextBlock.x++;
422 					else
423 						nextBlock.x--;
424 					nextBlockTime = fv.x * invX;
425 					hasNextBlock = 1;
426 				}
427 				if (invY != 0.f) {
428 					float t = fv.y * invY;
429 					if (!hasNextBlock || t < nextBlockTime) {
430 						nextBlock = iv;
431 						if (dir.y > 0.f)
432 							nextBlock.y++;
433 						else
434 							nextBlock.y--;
435 						nextBlockTime = t;
436 						hasNextBlock = 2;
437 					}
438 				}
439 				if (invZ != 0.f) {
440 					float t = fv.z * invZ;
441 					if (!hasNextBlock || t < nextBlockTime) {
442 						nextBlock = iv;
443 						if (dir.z > 0.f)
444 							nextBlock.z++;
445 						else
446 							nextBlock.z--;
447 						nextBlockTime = t;
448 						hasNextBlock = 3;
449 					}
450 				}
451 				SPAssert(hasNextBlock != 0);  // must hit a plane
452 				SPAssert(hasNextBlock == 1 || // x-plane
453 				         hasNextBlock == 2 || // y-plane
454 				         hasNextBlock == 3);  // z-plane
455 
456 				if (hasNextBlock == 1) {
457 					fv.x = 1.f;
458 				} else {
459 					fv.x -= fabsf(dir.x) * nextBlockTime;
460 				}
461 				if (hasNextBlock == 2) {
462 					fv.y = 1.f;
463 				} else {
464 					fv.y -= fabsf(dir.y) * nextBlockTime;
465 				}
466 				if (hasNextBlock == 3) {
467 					fv.z = 1.f;
468 				} else {
469 					fv.z -= fabsf(dir.z) * nextBlockTime;
470 				}
471 
472 				result.hitBlock = nextBlock;
473 				result.normal = iv - nextBlock;
474 
475 				if (IsSolidWrapped(nextBlock.x, nextBlock.y, nextBlock.z)) {
476 					// hit.
477 					Vector3 hitPos;
478 					if (dir.x > 0.f) {
479 						hitPos.x = (float)(nextBlock.x + 1) - fv.x;
480 					} else {
481 						hitPos.x = (float)nextBlock.x + fv.x;
482 					}
483 					if (dir.y > 0.f) {
484 						hitPos.y = (float)(nextBlock.y + 1) - fv.y;
485 					} else {
486 						hitPos.y = (float)nextBlock.y + fv.y;
487 					}
488 					if (dir.z > 0.f) {
489 						hitPos.z = (float)(nextBlock.z + 1) - fv.z;
490 					} else {
491 						hitPos.z = (float)nextBlock.z + fv.z;
492 					}
493 
494 					result.hit = true;
495 					result.startSolid = false;
496 					result.hitPos = hitPos;
497 					return result;
498 				} else {
499 					iv = nextBlock;
500 				}
501 			}
502 
503 			result.hit = false;
504 			result.startSolid = false;
505 			result.hitPos = v0;
506 			return result;
507 		}
508 
swapColor(uint32_t col)509 		static uint32_t swapColor(uint32_t col) {
510 			union {
511 				uint8_t bytes[4];
512 				uint32_t c;
513 			} u;
514 			u.c = col;
515 			std::swap(u.bytes[0], u.bytes[2]);
516 			return (u.c & 0xffffff) | (100UL * 0x1000000);
517 		}
518 
Load(spades::IStream * stream)519 		GameMap *GameMap::Load(spades::IStream *stream) {
520 			SPADES_MARK_FUNCTION();
521 
522 			std::string bytes = stream->ReadAllBytes();
523 			size_t len = bytes.size();
524 			size_t pos = 0;
525 
526 			Handle<GameMap> map{new GameMap(), false};
527 
528 				for (int y = 0; y < 512; y++) {
529 					for (int x = 0; x < 512; x++) {
530 						map->solidMap[x][y] = 0xffffffffffffffffULL;
531 
532 						if (pos + 2 >= len) {
533 							SPRaise("File truncated");
534 						}
535 
536 						int z = 0;
537 						for (;;) {
538 							int i;
539 							uint32_t *color;
540 							int number_4byte_chunks = bytes[pos];
541 							int top_color_start = bytes[pos + 1];
542 							int top_color_end = bytes[pos + 2];
543 							int bottom_color_start;
544 							int bottom_color_end;
545 							int len_top;
546 							int len_bottom;
547 
548 							for (i = z; i < top_color_start; i++)
549 								map->Set(x, y, i, false, 0, true);
550 
551 							if (pos + 4 + top_color_end - top_color_start + 3 >= len) {
552 								SPRaise("File truncated");
553 							}
554 
555 							color = (uint32_t *)(bytes.data() + pos + 4);
556 							for (z = top_color_start; z <= top_color_end; z++)
557 								map->Set(x, y, z, true, swapColor(*(color++)), true);
558 
559 							if (top_color_end == 62) {
560 								map->Set(x, y, 63, true, map->GetColor(x, y, 62), true);
561 							}
562 
563 							len_bottom = top_color_end - top_color_start + 1;
564 
565 							if (number_4byte_chunks == 0) {
566 								pos += 4 * (len_bottom + 1);
567 								break;
568 							}
569 
570 							len_top = (number_4byte_chunks - 1) - len_bottom;
571 
572 							pos += (int)bytes[pos] * 4;
573 
574 							if (pos + 3 >= len) {
575 								SPRaise("File truncated");
576 							}
577 
578 							bottom_color_end = bytes[pos + 3];
579 							bottom_color_start = bottom_color_end - len_top;
580 
581 							for (z = bottom_color_start; z < bottom_color_end; z++) {
582 								uint32_t col = swapColor(*(color++));
583 								map->Set(x, y, z, true, col, true);
584 							}
585 							if (bottom_color_end == 63) {
586 								map->Set(x, y, 63, true, map->GetColor(x, y, 62), true);
587 							}
588 						}
589 					}
590 				}
591 
592 			return map.Unmanage();
593 		}
594 	}
595 }
596