Skip to content

Instantly share code, notes, and snippets.

@kaikai2

kaikai2/dynamic_battlefog.cpp

Last active December 17, 2015 23:29
Show Gist options
  • Save kaikai2/5690071 to your computer and use it in GitHub Desktop.
Save kaikai2/5690071 to your computer and use it in GitHub Desktop.
Download ZIP
在一个平面格子地图中，求从一个点为视点中心，指定半径范围可见区域的多边形。 按角度排序所有潜在可见边的两个端点，端点按扫描方向分为开始端点和结束端点。 从一个最近的端点开始扫描， 每当遇到一个开始端点就把它所属的可见边加入当前扫描集中，并判断这个端点与当前可见边相比是否更近（远的被挡住直接无视）更近的话添加一个射线与当前边的交点然后切换当前边。 每当遇到一个结束端点，就从当前扫描集中去掉这个端点所属的边，然后找当前射线与所有当前扫描集的交点中最近的作为新的当前边。同时添加结束端点以及射线与新的扫描边的交点到结果多边形。 扫描过程最多执行2圈，直到新添加的多边形点已经在结果多边形（闭合）为止。 如果需要一个指定的夹角，那么扫描开始和结束的角度射线作为起止条件即可。
Raw
dynamic_battlefog.cpp
#include "dynamic_battlefog.h"
#include <cmath>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
using std::max;
using std::min;
CDynamicBattleFog::CDynamicBattleFog()
{
}
cLine cRectangle::side( Side eSide ) const
{
switch(eSide)
{
case Side_Left:
return left();
case Side_Top:
return top();
case Side_Right:
return right();
case Side_Bottom:
return bottom();
case NumSide:
break;
}
assert(0);
return cLine();
}
cPoint cRectangle::getCornor( Side eSide ) const
{
switch(eSide)
{
case Side_Left:
return _leftTop;
case Side_Top:
return cPoint(_rightBottom._x, _leftTop._y);
case Side_Right:
return _rightBottom;
case Side_Bottom:
return cPoint(_leftTop._x, _rightBottom._y);
case NumSide:
break;
}
assert(0);
return cPoint();
}
inline int dotProduct(const cPoint &v0, const cPoint &v1)
{
return v0._x * v1._x + v0._y * v1._y;
}
inline int crossProduct(const cPoint &v0, const cPoint &v1)
{
return v0._x * v1._y - v0._y * v1._x;
}
inline bool inside(const cPoint &v, const cRectangle &r)
{
return r._leftTop._x < v._x && v._x < r._rightBottom._x &&
r._leftTop._y < v._y && v._y < r._rightBottom._y;
}
bool crossPoint(const cLine &line1, const cLine &line2, cPoint &p)
{
cPoint v0 = line2._a - line1._a;
cPoint v1 = line1._b - line1._a;
cPoint v2 = line2._b - line1._a;
int cp0 = crossProduct(v0, v1);
int cp1 = crossProduct(v1, v2);
if (cp0 && cp1 && ((cp0 ^ cp1) & INT_MIN) != 0)
return false;
cPoint n0 = line1._a - line2._a;
cPoint n1 = line2._b - line2._a;
cPoint n2 = line1._b - line2._a;
int cp2 = crossProduct(n0, n1);
int cp3 = crossProduct(n1, n2);
if (cp2 && cp3 && ((cp2 ^ cp3) & INT_MIN) != 0)
return false;
int cp4 = crossProduct(v1, n1);
double t = cp4 ? fabs((double)cp0 / cp4) : 0;
p = cPoint(line2._a._x + n1._x * t, line2._a._y + n1._y * t);
return true;
}
inline int distance_Manhatan(const cPoint &a, const cPoint &b)
{
cPoint c = a - b;
return abs(c._x) + abs(c._y);
}
inline int distance(const cPoint &a, const cPoint &b)
{
cPoint c = a - b;
return (int)sqrtf(dotProduct(c, c));
}
inline bool crossPoint(const cRadial &radial, const cLine &line, cPoint &p)
{
cPoint v0 = line._a - radial._o;
cPoint v2 = line._b - radial._o;
int m = 1;
{
int mx = 1;
if (radial._d._x != 0)
{
int dx = max(abs(v0._x), abs(v2._x));
mx = abs((dx + abs(radial._d._x) -1) / radial._d._x);
}
int my = 1;
if (radial._d._y != 0)
{
int dy = max(abs(v0._y), abs(v2._y));
my = abs((dy + abs(radial._d._y) -1) / radial._d._y);
}
m = max(mx, my);
}
cPoint r2(radial._o._x + radial._d._x * m, radial._o._y + radial._d._y * m);
return crossPoint(cLine(radial._o, r2), line, p);
}
inline bool crossPoint(const cRadial &radial, const cRectangle &rectangle, cPoint &p, int &side)
{
int nSide;
int minDistance = INT_MAX;
for (nSide = cRectangle::BeginSide; nSide < cRectangle::NumSide; nSide++)
{
cPoint curCrossPoint;
if (crossPoint(radial, rectangle.side((cRectangle::Side)nSide), curCrossPoint))
{
int nDistance = distance_Manhatan(radial._o, curCrossPoint);
if (nDistance < minDistance)
{
minDistance = nDistance;
p = curCrossPoint;
side = nSide;
}
}
}
return minDistance != INT_MAX;
}
struct Knode
{
cPoint d;
size_t index;
bool begin;
int quadrant() const
{
if (d._y > 0)
{
if (d._x > 0)
return 1;
return 2;
}
else
{
if (d._x > 0)
return 4;
return 3;
}
}
};
bool operator < (const Knode &k1, const Knode &k2)
{
// order by x+,y- > x-,y- > x-,y+ > x+,y+
const int quadrant1 = k1.quadrant();
const int quadrant2 = k2.quadrant();
if (quadrant1 == quadrant2)
{
const int xp = crossProduct(k1.d, k2.d);
if (xp == 0)
{
int dp1 = dotProduct(k1.d, k1.d);
int dp2 = dotProduct(k2.d, k2.d);
if (dp1 == dp2)
{
if ((int)k1.begin == (int)k2.begin)
{
return k1.index > k2.index;
}
return (int)k1.begin > (int)k2.begin;
}
return dp1 < dp2;
}
return xp > 0;
}
return quadrant1 < quadrant2;
}
inline bool SameLine(const cPoint &a, const cPoint &b, const cPoint &c)
{
//if (abs(crossProduct(b-a, c-a)) < 10)
// return true;
//return false;
if ((a._x == b._x && b._x == c._x) ||
(a._y == b._y && b._y == c._y))
return true;
return false;
}
struct Gen
{
const cPoint _center;
const std::vector<cLine> &_vecLines;
std::set<Knode> _setK;
std::vector<cPoint> _vecBorders;
bool _done;
Gen(const std::vector<cLine> &vecLines, const cPoint &center) : _center(center), _vecLines(vecLines), _done(false)
{
}
void gen_setK()
{
for (size_t i = 0; i < _vecLines.size(); ++i)
{
const cLine &line = _vecLines[i];
Knode na;
na.d = line._a; // normalized position, relative to center
na.index = i;
na.begin = false;
Knode nb;
nb.d = line._b; // ditto
nb.index = i;
nb.begin = false;
if (crossProduct(na.d, nb.d) > 0)
{
na.begin = true;
}
else
{
nb.begin = true;
}
_setK.insert(na);
_setK.insert(nb);
}
}
size_t walkIn(const Knode &n, const std::vector<size_t> &curIndex, size_t nIndexOfLastBorderLine)
{
if (curIndex.empty())
{
addBorder(n.d);
nIndexOfLastBorderLine = n.index;
return nIndexOfLastBorderLine;
}
cRadial radial(cPoint(0, 0), n.d);
size_t best = n.index;
cPoint bestEndPoint = n.d;
int minDistance = dotProduct(n.d, n.d);
for (size_t i = 0; i < curIndex.size(); ++i)
{
cPoint p;
if (crossPoint(radial, _vecLines[curIndex[i]], p))
{
int distance = dotProduct(p, p);
if (distance < minDistance)
{
minDistance = distance;
best = curIndex[i];
bestEndPoint = p;
}
}
}
// add border line
if (nIndexOfLastBorderLine == best) // 还是同一条线段，直接继续
{
addBorder(bestEndPoint);//
//_vecBorders.push_back(bestEndPoint);
}
else
{
if (best == n.index) // 变得更近
{
cPoint p;
if (nIndexOfLastBorderLine != static_cast<size_t>(~0) &&
crossPoint(radial, _vecLines[nIndexOfLastBorderLine], p))
{
addBorder(p);
}
addBorder(bestEndPoint);
}
//else // 离得更远了
//{
// //assert(0);
//}
nIndexOfLastBorderLine = best;
}
return nIndexOfLastBorderLine;
}
void addBorder(const cPoint &p)
{
if (_done)
return;
if (!_vecBorders.empty())
{
if (p == _vecBorders.back())
return;
if (p == _vecBorders[0])
{
_done = true;
}
if (_vecBorders.size() >= 2)
{
if (SameLine(_vecBorders[_vecBorders.size() - 2], _vecBorders.back(), p))
{
_vecBorders.back() = p;
while(_vecBorders.size() >= 2 && _vecBorders.back() == _vecBorders[_vecBorders.size() - 2])
{
_vecBorders.pop_back();
}
return;
}
}
}
_vecBorders.push_back(p);
}
size_t walkOut(const Knode &n, const std::vector<size_t> &curIndex, size_t nIndexOfLastBorderLine)
{
if (n.index == nIndexOfLastBorderLine) // 当前最近的一段结束了，立即找一个次近的接上
{
cRadial radial(cPoint(0, 0), n.d);
size_t best = n.index;
cPoint bestEndPoint = n.d;
int minDistance = INT_MAX;
for (size_t i = 0; i < curIndex.size(); ++i)
{
cPoint p;
if (crossPoint(radial, _vecLines[curIndex[i]], p))
{
int distance = dotProduct(p, p);
if (distance < minDistance)
{
minDistance = distance;
best = curIndex[i];
bestEndPoint = p;
}
}
}
addBorder(n.d);
if (best != n.index)
{
addBorder(bestEndPoint);
nIndexOfLastBorderLine = best;
}
}
return nIndexOfLastBorderLine;
}
void walkThrough()
{
std::vector<size_t> curIndex;
size_t nIndexOfLastBorderLine = -1;
_vecBorders.clear();
_done = false;
#if DEBUG_BATTLEFOG
std::vector<Knode> vecAllK;
for (std::set<Knode>::iterator it = _setK.begin(); it != _setK.end(); ++it)
{
const Knode &n = *it;
vecAllK.push_back(n);
}
#endif
cPoint beginPoint = _setK.begin()->d;
cRadial radial(cPoint(), beginPoint);
int minDistance = dotProduct(beginPoint, beginPoint);
for (size_t i = 0; i < _vecLines.size(); i++)
{
cPoint p;
if (i != _setK.begin()->index && crossPoint(radial, _vecLines[i], p))
{
curIndex.push_back(i);
int distance = dotProduct(p, p);
if (distance < minDistance)
{
minDistance = distance;
nIndexOfLastBorderLine = i;
beginPoint = p;
}
}
}
if (nIndexOfLastBorderLine != size_t(-1))
{
addBorder(beginPoint);
}
for (int c = 0; c < 2; c++)
{
for (std::set<Knode>::iterator it = _setK.begin(); !_done && it != _setK.end(); ++it)
{
const Knode &n = *it;
if (n.begin)
{
nIndexOfLastBorderLine = walkIn(n, curIndex, nIndexOfLastBorderLine);
curIndex.push_back(n.index);
}
else
{
// remove current index
for (size_t i = 0; i < curIndex.size(); ++i)
{
if (curIndex[i] == n.index)
{
curIndex[i] = curIndex.back();
curIndex.pop_back();
nIndexOfLastBorderLine = walkOut(n, curIndex, nIndexOfLastBorderLine);
break;
}
}
}
}
}
}
void outPoly(std::vector<cPoint> &vecPolygons) const
{
vecPolygons.reserve(_vecBorders.size());
for (size_t i = 1; i < _vecBorders.size(); ++i)
{
vecPolygons.push_back(_center + _vecBorders[i]);
// cPolygon p;
// p.add(_center).add(_center + _vecBorders[i - 1]).add(_center + _vecBorders[i]);
// vecPolygons.push_back(p);
}
}
};
void CDynamicBattleFog::Calc2(const IMap &m, int xCenter, int yCenter, int sightRadius, std::vector<cPoint> &vecPolygon) const
{
const int xBlock = m.blockX(xCenter);
const int yBlock = m.blockY(yCenter);
const int left = m.clampWidth(m.blockX(xCenter - sightRadius));
const int right = m.clampWidth(m.blockX(xCenter + sightRadius));
const int top = m.clampHeight(m.blockY(yCenter - sightRadius));
const int bottom = m.clampHeight(m.blockY(yCenter + sightRadius));
std::vector<cLine> vecLines = generateBlockBoundaries(left, right, top, bottom, m, xBlock, yBlock);
cPoint center(xCenter, yCenter);
// normalize
for (size_t i = 0; i < vecLines.size(); ++i)
{
cLine &line = vecLines[i];
line._a = line._a - center;
line._b = line._b - center;
}
for (size_t i = 0; i < vecLines.size();)
{
cLine &line = vecLines[i];
if ((line._a._x == 0 && line._b._x == 0) ||
(line._a._y == 0 && line._b._y == 0))
{
line = vecLines.back();
vecLines.pop_back();
}
else
{
++i;
}
}
static const float pi = acos(-1.f);
const int segs = (int)(2 * pi * sightRadius / 50);
const float coef = 2.0f * (float) pi / segs;
cPoint circleLast;
size_t boundaryCount = vecLines.size();
for(int i = 0; i <= segs; i++)
{
float rads = i*coef;
float j = sightRadius * cosf(rads);
float k = sightRadius * sinf(rads);
cPoint p(j, k);
if (i)
{
cLine line(circleLast, p);
vecLines.push_back(line);
for (size_t j = 0; j < boundaryCount; j++)
{
cPoint xP;
cLine &xLine = vecLines[j];
if (crossPoint(line, xLine, xP))
{
int dpa = dotProduct(xLine._a - xP, cPoint() - xP);
int dpb = dotProduct(xLine._b - xP, cPoint() - xP);
if (dpa > 0 && dpb < 0)
xLine._b = xP;
else if (dpb > 0 && dpa < 0)
xLine._a = xP;
else if (dpa <= 0 && dpb <= 0)
{
xLine = vecLines[--boundaryCount];
vecLines[boundaryCount] = vecLines.back();
vecLines.pop_back();
--j;
}
}
}
}
circleLast = p;
}
/*
for (size_t i = 0; i < vecLines.size(); i++)
{
cPolygon p;
cLine &xLine = vecLines[i];
p.add(center).add(center + xLine._a).add(center + xLine._b);
p._flag = i < boundaryCount ? 1 : 2;
vecPolygons.push_back(p);
}*/
Gen gen(vecLines, center);
gen.gen_setK();
gen.walkThrough();
gen.outPoly(vecPolygon);
}
void CDynamicBattleFog::Calc(const IMap &m, int xCenter, int yCenter, int xSight, int ySight, std::vector<cPolygon> &vecPolygons) const
{
const int xBlock = m.blockX(xCenter);
const int yBlock = m.blockY(yCenter);
const int left = m.clampWidth(m.blockX(xCenter - xSight));
const int right = m.clampWidth(m.blockX(xCenter + xSight));
const int top = m.clampHeight(m.blockY(yCenter - ySight));
const int bottom = m.clampHeight(m.blockY(yCenter + ySight));
std::vector<cLine> vecLines = generateBlockBoundaries(left, right, top, bottom, m, xBlock, yBlock);
const cPoint leftTop(xCenter - xSight, yCenter - ySight);// = m.getCornor(IMap::BC_LeftTop, left, top);
const cPoint rightBottom(xCenter + xSight, yCenter + ySight);// = m.getCornor(IMap::BC_RightBottom, right, bottom);
const cRectangle objectRectangle(leftTop, rightBottom);
const cPoint center(xCenter, yCenter);
for (size_t i = 0; i < vecLines.size(); i++)
{
cPolygon p;
cLine l = vecLines[i];
cPoint p1, p2;
int side1 = -1, side2 = -1;
if (!inside(l._a, objectRectangle) &&
crossPoint(cRadial(l._a, l._b - l._a), objectRectangle, p2, side2))
{
l._a = p2;
}
else
{
p.add(l._a);
}
if (!inside(l._b, objectRectangle) &&
crossPoint(cRadial(l._b, l._a - l._b), objectRectangle, p1, side1))
{
l._b = p1;
}
else
{
p.add(l._b);
}
if (crossPoint(cRadial(center, l._b - center), objectRectangle, p1, side1) &&
crossPoint(cRadial(center, l._a - center), objectRectangle, p2, side2))
{
if (side1 > side2)
std::swap(side1, side2);
p.add(p1);
if (side1 == side2)
{
// same side, no need to add internal corner points
}
else if (side1 + 1 == side2)
{
// neighbor sides, add the common corner of the two sides
p.add(objectRectangle.getCornor((cRectangle::Side)side1));
}
else if (side1 + 3 == side2)
{
// neighbor sides, add the common corner of the two sides, just another kind
p.add(objectRectangle.getCornor((cRectangle::Side)side2));
}
else
{
// opposite sides, check center to find out which two corners need to be added
cRectangle::Side eSide1 = cRectangle::Side_Top, eSide2 = cRectangle::Side_Top;
if (side1 == cRectangle::Side_Left) // implicit include Side_Right
{
if (yCenter > p1._y)
{
eSide1 = cRectangle::Side_Top;
eSide2 = cRectangle::Side_Left;
}
else
{
eSide1 = cRectangle::Side_Right;
eSide2 = cRectangle::Side_Bottom;
}
}
else
{
if (xCenter > p1._x)
{
eSide1 = cRectangle::Side_Bottom;
eSide2 = cRectangle::Side_Left;
}
else
{
eSide1 = cRectangle::Side_Right;
eSide2 = cRectangle::Side_Top;
}
}
p.add(objectRectangle.getCornor(eSide1))
.add(objectRectangle.getCornor(eSide2));
}
p.add(p2);
vecPolygons.push_back(p);
}
}
}
void CDynamicBattleFog::GenerateViewRangePatches( const IMapView &view, const cRectangle &objectRectangle, std::vector<cPolygon> &vecPolygons) const
{
const cRectangle viewRectangle(cPoint(view.left(), view.top()), cPoint(view.right(), view.bottom()));
cQuad q;
// add left
q._p0 = cPoint(viewRectangle._leftTop._x, viewRectangle._leftTop._y);
q._p1 = cPoint(min(viewRectangle._rightBottom._x, objectRectangle._leftTop._x), q._p0._y);
q._p2 = cPoint(q._p1._x, viewRectangle._rightBottom._y);
q._p3 = cPoint(q._p0._x, q._p2._y);
if (q._p0._x < q._p1._x && q._p1._y < q._p2._y)
vecPolygons.push_back(cPolygon(q));
// add top
q._p0 = cPoint(max(objectRectangle._leftTop._x, viewRectangle._leftTop._x), viewRectangle._leftTop._y);
q._p1 = cPoint(min(objectRectangle._rightBottom._x, viewRectangle._rightBottom._x), q._p0._y);
q._p2 = cPoint(q._p1._x, min(objectRectangle._leftTop._y, viewRectangle._rightBottom._y));
q._p3 = cPoint(q._p0._x, q._p2._y);
if (q._p0._x < q._p1._x && q._p1._y < q._p2._y)
vecPolygons.push_back(cPolygon(q));
// add right
q._p0 = cPoint(max(viewRectangle._leftTop._x, objectRectangle._rightBottom._x), viewRectangle._leftTop._y);
q._p1 = cPoint(viewRectangle._rightBottom._x, q._p0._y);
q._p2 = cPoint(q._p1._x, viewRectangle._rightBottom._y);
q._p3 = cPoint(q._p0._x, q._p2._y);
if (q._p0._x < q._p1._x && q._p1._y < q._p2._y)
vecPolygons.push_back(cPolygon(q));
// add bottom
q._p0 = cPoint(max(objectRectangle._leftTop._x, viewRectangle._leftTop._x), max(objectRectangle._rightBottom._y, viewRectangle._leftTop._y));
q._p1 = cPoint(min(objectRectangle._rightBottom._x, viewRectangle._rightBottom._x), q._p0._y);
q._p2 = cPoint(q._p1._x, viewRectangle._rightBottom._y);
q._p3 = cPoint(q._p0._x, q._p2._y);
if (q._p0._x < q._p1._x && q._p1._y < q._p2._y)
vecPolygons.push_back(cPolygon(q));
}
std::vector<cLine> CDynamicBattleFog::generateBlockBoundaries( int left, int right, int top, int bottom, const IMap & m, int xCenter, int yCenter ) const
{
std::vector<cLine> vecLines;
// generate by right boundaries of blocks
generateVerticalBoundaries(left, xCenter - 1, top, bottom, m, vecLines, IMap::BC_RightTop, IMap::BC_RightBottom, 1);
// generate by left boundaries of blocks
generateVerticalBoundaries(xCenter + 1, right, top, bottom, m, vecLines, IMap::BC_LeftTop, IMap::BC_LeftBottom, -1);
// generate by bottom boundaries of blocks
generateHorizontalBoundaries(left, right, top, yCenter - 1, m, vecLines, IMap::BC_LeftBottom, IMap::BC_RightBottom , 1);
// generate by top boundaries of blocks
generateHorizontalBoundaries(left, right, yCenter + 1, bottom, m, vecLines, IMap::BC_LeftTop, IMap::BC_RightTop, -1);
return vecLines;
}
void CDynamicBattleFog::generateVerticalBoundaries( int left, int right, int top, int bottom, const IMap &m, std::vector<cLine> &vecLines, IMap::BlockCornor eBlockCornorBegin, IMap::BlockCornor eBlockCornorEnd, int dx ) const
{
for (int x = left; x <= right; x++)
{
bool bBlock = false;
int lastY = -1;
for (int y = top; y <= bottom; y++)
{
if (bBlock)
{
if (!m.isBlock(x, y) || m.isBlock(x + dx, y))
{
vecLines.push_back(cLine(m.getCornor(eBlockCornorBegin, x, lastY), m.getCornor(eBlockCornorEnd, x, y - 1)));
bBlock = false;
}
}
else
{
if (m.isBlock(x, y) && !m.isBlock(x + dx, y))
{
bBlock = true;
lastY = y;
}
}
}
if (bBlock)
vecLines.push_back(cLine(m.getCornor(eBlockCornorBegin, x, lastY), m.getCornor(eBlockCornorEnd, x, bottom)));
}
}
void CDynamicBattleFog::generateHorizontalBoundaries( int left, int right, int top, int bottom, const IMap &m, std::vector<cLine> &vecLines, IMap::BlockCornor eBlockCornorBegin, IMap::BlockCornor eBlockCornorEnd, int dy ) const
{
for (int y = top; y <= bottom; y++)
{
bool bBlock = false;
int lastX = -1;
for (int x = left; x <= right; x++)
{
if (bBlock)
{
if (!m.isBlock(x, y) || m.isBlock(x, y + dy))
{
vecLines.push_back(cLine(m.getCornor(eBlockCornorBegin, lastX, y), m.getCornor(eBlockCornorEnd, x - 1, y)));
bBlock = false;
}
}
else
{
if (m.isBlock(x, y) && !m.isBlock(x, y + dy))
{
bBlock = true;
lastX = x;
}
}
}
if (bBlock)
vecLines.push_back(cLine(m.getCornor(eBlockCornorBegin, lastX, y), m.getCornor(eBlockCornorEnd, right, y)));
}
}
Raw
dynamic_battlefog.h
#ifndef _Dynamic_BattleFog_H_
#define _Dynamic_BattleFog_H_
#include <cmath>
#include <vector>
class cPoint
{
public:
cPoint():_x(0), _y(0){}
cPoint(int x, int y):_x(x), _y(y){}
cPoint operator - (const cPoint &o) const
{
cPoint a(_x - o._x, _y - o._y);
return a;
}
cPoint operator + (const cPoint &o) const
{
cPoint a(_x + o._x, _y + o._y);
return a;
}
cPoint nomalize(int length) const
{
if (_x == 0 && _y == 0)
return *this;
float len = sqrtf(float(_x * _x + _y * _y));
cPoint a(_x * length / len, _y * length / len);
return a;
}
int _x, _y;
};
inline bool operator == (const cPoint &a, const cPoint &b)
{
return a._x == b._x && a._y == b._y;
}
class cLine
{
public:
cLine():_a(),_b(){}
cLine(const cPoint &a, const cPoint &b):_a(a), _b(b){}
cPoint _a, _b;
};
inline bool operator == (const cLine &a, const cLine &b)
{
return a._a == b._a && a._b == b._b || a._a == b._b && a._b == b._a;
}
class cRadial
{
public:
cRadial():_o(),_d(){}
cRadial(const cPoint &o, const cPoint &d):_o(o), _d(d){}
cPoint _o, _d;
};
class cRectangle
{
public:
enum Side
{
BeginSide,
Side_Left = BeginSide,
Side_Top,
Side_Right,
Side_Bottom,
NumSide,
};
cRectangle():_leftTop(),_rightBottom(){}
cRectangle(const cPoint &leftTop, const cPoint &rightBottom):_leftTop(leftTop), _rightBottom(rightBottom){}
cPoint getCornor(Side eSide) const;
cLine side(Side eSide) const;
cLine left() const
{
cLine l(_leftTop, cPoint(_leftTop._x, _rightBottom._y));
return l;
}
cLine right() const
{
cLine l(cPoint(_rightBottom._x, _leftTop._y), _rightBottom);
return l;
}
cLine top() const
{
cLine l(_leftTop, cPoint(_rightBottom._x, _leftTop._y));
return l;
}
cLine bottom() const
{
cLine l(cPoint(_leftTop._x, _rightBottom._y), _rightBottom);
return l;
}
cPoint _leftTop, _rightBottom;
};
class cCircle
{
public:
cCircle():_center(),_radius(0){}
cCircle(const cPoint &center, int radius):_center(center), _radius(radius){}
bool inSide(const cPoint &p) const
{
cPoint d(p - _center);
return _radius * _radius > d._x * d._x + d._y * d._y;
}
cPoint _center;
int _radius;
};
class cQuad
{
public:
cQuad():_p0(), _p1(), _p2(), _p3(){}
cQuad(const cPoint &p0, const cPoint &p1, const cPoint &p2, const cPoint &p3):_p0(p0), _p1(p1), _p2(p2), _p3(p3){}
cPoint _p0, _p1, _p2, _p3;
};
class cPolygon
{
public:
cPolygon():_nPoint(0),_flag(0){}
cPolygon(const cQuad &q):_nPoint(0),_flag(0)
{
add(q._p0).add(q._p1).add(q._p2).add(q._p3);
}
cPolygon& add(const cPoint &p)
{
if (_nPoint < (int)(sizeof(_p) / sizeof(_p[0])))
_p[_nPoint++] = p;
return *this;
}
cPolygon& clear()
{
_nPoint = 0;
_flag = 0;
return *this;
}
cPoint _p[16];
int _nPoint;
int _flag;
};
class IMap
{
public:
enum BlockCornor
{
BC_LeftBottom,
BC_LeftTop,
BC_RightBottom,
BC_RightTop,
};
virtual ~IMap() = 0;
virtual bool isBlock(int x, int y) const = 0;
virtual int blockX(int xPos) const = 0;
virtual int blockY(int yPos) const = 0;
virtual int clampWidth(int x) const = 0;
virtual int clampHeight(int y) const = 0;
virtual cPoint getCornor(BlockCornor eBlockCornor, int x, int y) const = 0;
};
inline IMap::~IMap()
{
}
class IMapView
{
public:
virtual ~IMapView() = 0;
virtual int left() const = 0;
virtual int right() const = 0;
virtual int top() const = 0;
virtual int bottom() const = 0;
};
inline IMapView::~IMapView()
{
}
template<typename T>
T clamp(T a, T low, T high)
{
if (a < low)
return low;
if (high < a)
return high;
return a;
}
class CDynamicBattleFog
{
public:
CDynamicBattleFog();
void Calc(const IMap &map, int xCenter, int yCenter, int xSight, int ySight, std::vector<cPolygon> &vecPolygons) const;
void GenerateViewRangePatches( const IMapView &view, const cRectangle &objectRectangle, std::vector<cPolygon> &vecPolygons) const;
void Calc2(const IMap &map, int xCenter, int yCenter, int sightRadius, std::vector<cPoint> &vecPolygon) const;
private:
std::vector<cLine> generateBlockBoundaries( int left, int right, int top, int bottom, const IMap & m, int xCenter, int yCenter ) const;
void generateVerticalBoundaries( int left, int right, int top, int bottom, const IMap &m, std::vector<cLine> &vecLines, IMap::BlockCornor eBlockCornorBegin, IMap::BlockCornor eBlockCornorEnd, int dx ) const;
void generateHorizontalBoundaries( int left, int right, int top, int bottom, const IMap &m, std::vector<cLine> &vecLines, IMap::BlockCornor eBlockCornorBegin, IMap::BlockCornor eBlockCornorEnd, int dy ) const;
};
#endif//_Dynamic_BattleFog_H_
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment