OpenClonk
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros
C4FoWBeam.cpp
Go to the documentation of this file.
1 /*
2  * OpenClonk, http://www.openclonk.org
3  *
4  * Copyright (c) 2014-2016, The OpenClonk Team and contributors
5  *
6  * Distributed under the terms of the ISC license; see accompanying file
7  * "COPYING" for details.
8  *
9  * "Clonk" is a registered trademark of Matthes Bender, used with permission.
10  * See accompanying file "TRADEMARK" for details.
11  *
12  * To redistribute this file separately, substitute the full license texts
13  * for the above references.
14  */
15 
16 #include "C4Include.h"
18 
19 #ifndef USE_CONSOLE
21 
22 // Maximum error allowed while merging beams.
23 const int32_t C4FoWMergeThreshold = 10; // (in landscape pixels * 2)
24 
25 // A = 1/2 | a x b |
26 static inline int32_t getDoubleTriangleSurface(int32_t x1, int32_t y1, int32_t x2, int32_t y2, int32_t x3, int32_t y3)
27 {
28  int32_t ax = x2 - x1, ay = y2 - y1;
29  int32_t bx = x3 - x1, by = y3 - y1;
30  // We don't bother to actually halve so we can stay with integers.
31  // Doesn't matter as long as we keep in mind the threshold needs to
32  // be doubled.
33  return abs(ax * by - ay * bx);
34 }
35 
37  return FormatString("%d:%d@%d:%d%s",
38  getLeftX(1000),
39  getRightX(1000),
40  getLeftEndY(),
41  getRightEndY(),
42  fDirty ? "*" : "");
43 }
44 
45 bool C4FoWBeam::MergeRight(int32_t x, int32_t y)
46 {
47  // Note: Right-merging is the most common and most important optimization.
48  // This procedure will probably be *hammered* as a result. Worth inlining?
49 
50  assert(!isDirty()); assert(isRight(x, y));
51 
52  // Calculate error. Note that simply summing up errors is not correct,
53  // strictly speaking (as new and old error surfaces might overlap). Still,
54  // this is quite elaborate already, no need to make it even more
55  int32_t iErr = getDoubleTriangleSurface(
56  getLeftEndX(), iLeftEndY,
57  getRightEndX(), iRightEndY,
58  x, y);
59  if (iError + iErr > C4FoWMergeThreshold)
60  return false;
61 
62  // Move right endpoint.
63  iRightX = x;
64  iRightY = y;
65  iRightEndY = y;
66  iError += iErr;
67  return true;
68 }
69 
70 bool C4FoWBeam::MergeLeft(int32_t x, int32_t y)
71 {
72  assert(!isDirty()); assert(isLeft(x, y));
73 
74  // Calculate error.
75  float iErr = getDoubleTriangleSurface(
76  getLeftEndX(), iLeftEndY,
77  getRightEndX(), iRightEndY,
78  x, y);
79  if (iError + iErr > C4FoWMergeThreshold)
80  return false;
81 
82  // Move left endpoint.
83  iLeftX = x;
84  iLeftY = y;
85  iLeftEndY = y;
86  iError += iErr;
87  return true;
88 }
89 
90 bool C4FoWBeam::EliminateRight(int32_t x, int32_t y)
91 {
92  // Called on the beams left of the one getting eliminated
93  C4FoWBeam *pElim = pNext, *pMerge = pNext->pNext;
94  assert(!!pElim); assert(!!pMerge);
95  assert(!isDirty()); assert(!pMerge->isDirty());
96 
97  // Calc errors, add those accumulated on both merged beams
98  int32_t iErr = getDoubleTriangleSurface(
100  pMerge->getRightEndX(), pMerge->getRightEndY(),
101  x, y);
102  iErr += pMerge->iError;
103  if (iError + iErr > C4FoWMergeThreshold)
104  return false;
105 
106  // Do elimination
107  iRightX = pMerge->iRightX;
108  iRightY = pMerge->iRightY;
109  iRightEndY = pMerge->iRightEndY;
110  pNext = pMerge->pNext;
111  iError += iErr;
112  delete pElim;
113  delete pMerge;
114  return true;
115 }
116 
117 C4FoWBeam *C4FoWBeam::Split(int32_t x, int32_t y)
118 {
119  // Make sure to never create negative-surface beams
120  assert(isDirty()); assert(isInside(x, y));
121 
122  // Allocate a new beam. Ugh, expensive.
123  C4FoWBeam *pBeam = new C4FoWBeam(x, y, iRightX, iRightY);
124  pBeam->Dirty(iLeftEndY);
125 
126  // Move to make space
127  iRightX = x;
128  iRightY = y;
129 
130  // Relink
131  pBeam->pNext = pNext;
132  pNext = pBeam;
133  return pBeam;
134 }
135 
137 {
138  // As a rule, dirty beams following each other should
139  // always be merged, so splits can be reverted once
140  // the landscape changes.
141  C4FoWBeam *pWith = pNext;
142  assert(isDirty()); assert(!!pWith); assert(pWith->isDirty());
143 
144  // Figure out how far the new dirty beams reaches. Note that
145  // we might lose information about the landscape here.
146  Dirty(std::min(getLeftEndY(), pWith->getLeftEndY()));
147 
148  // Set right
149  iRightX = pWith->iRightX;
150  iRightY = pWith->iRightY;
151 
152  // Relink & delete
153  pNext = pWith->getNext();
154  delete pWith;
155 }
156 
157 void C4FoWBeam::Clean(int32_t y)
158 {
159  // Search hit something, this beam is now clean.
160  iLeftEndY = y;
161  iRightEndY = y;
162  fDirty = false;
163 }
164 
165 void C4FoWBeam::Dirty(int32_t y)
166 {
167  // Got invalidated, beam is dirty until updated
168  iLeftEndY = y;
169  iRightEndY = y;
170  fDirty = true;
171 }
172 
173 void C4FoWBeam::Prune(int32_t y)
174 {
175  // Check which sides we need to prune
176  bool fLeft = (iLeftEndY >= y),
177  fRight = (iRightEndY >= y);
178  // If both sides got pruned, we are clean
179  // (can't possibly extend this beam further)
180  if (fLeft && fRight)
181  Clean(y);
182  else if (fLeft)
183  iLeftEndY = y;
184  if (fRight)
185  iRightEndY = y;
186 }
187 
189 {
190  pComp->Value(mkNamingAdapt(iLeftX, "iLeftX"));
191  pComp->Value(mkNamingAdapt(iLeftY, "iLeftY"));
192  pComp->Value(mkNamingAdapt(iRightX, "iRightX"));
193  pComp->Value(mkNamingAdapt(iRightY, "iRightY"));
194  pComp->Value(mkNamingAdapt(iLeftEndY, "iLeftEndY"));
195  pComp->Value(mkNamingAdapt(iRightEndY, "iRightEndY"));
196  pComp->Value(mkNamingAdapt(iError, "iError"));
197  pComp->Value(mkNamingAdapt(fDirty, "fDirty"));
198 }
199 
200 #endif
bool isRight(int32_t x, int32_t y) const
Definition: C4FoWBeam.h:83
bool EliminateRight(int32_t x, int32_t y)
Definition: C4FoWBeam.cpp:90
int32_t getLeftEndY() const
Definition: C4FoWBeam.h:68
int32_t getLeftX(int32_t y) const
Definition: C4FoWBeam.h:63
StdNamingAdapt< T > mkNamingAdapt(T &&rValue, const char *szName)
Definition: StdAdaptors.h:92
void Dirty(int32_t y)
Definition: C4FoWBeam.cpp:165
const int32_t C4FoWMergeThreshold
Definition: C4FoWBeam.cpp:23
void MergeDirty()
Definition: C4FoWBeam.cpp:136
int32_t getRightX(int32_t y) const
Definition: C4FoWBeam.h:64
int32_t getRightEndY() const
Definition: C4FoWBeam.h:71
int32_t getRightEndX() const
Definition: C4FoWBeam.h:72
bool isDirty() const
Definition: C4FoWBeam.h:57
void Value(const T &rStruct)
Definition: StdCompiler.h:161
void Prune(int32_t y)
Definition: C4FoWBeam.cpp:173
void Clean(int32_t y)
Definition: C4FoWBeam.cpp:157
bool isLeft(int32_t x, int32_t y) const
Definition: C4FoWBeam.h:78
StdStrBuf getDesc() const
Definition: C4FoWBeam.cpp:36
C4FoWBeam * getNext() const
Definition: C4FoWBeam.h:59
int32_t getLeftEndX() const
Definition: C4FoWBeam.h:69
C4FoWBeam(int32_t iLeftX, int32_t iLeftY, int32_t iRightX, int32_t iRightY)
Definition: C4FoWBeam.h:40
bool MergeLeft(int32_t x, int32_t y)
Definition: C4FoWBeam.cpp:70
bool MergeRight(int32_t x, int32_t y)
Definition: C4FoWBeam.cpp:45
C4FoWBeam * Split(int32_t x, int32_t y)
Definition: C4FoWBeam.cpp:117
bool isInside(int32_t x, int32_t y) const
Definition: C4FoWBeam.h:88
void CompileFunc(StdCompiler *pComp)
Definition: C4FoWBeam.cpp:188
StdStrBuf FormatString(const char *szFmt,...)
Definition: StdBuf.cpp:270