finscn/dynamic_battlefog.cpp

## 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)));
	}
}

## 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_
	#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)));
	}
	}
	#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_