弹弹堂游戏截图.gif
' ０９年，第一次接触到《弹弹堂》这款游戏，其独特的可破坏地形，让不少玩家都惊叹不已，你可以在此机制下，创造各种玩法，跟玩家摩擦出各种闹剧。当炮弹击中地形障碍，地形会被炸出个窟窿，这个窟窿并非贴图上不可见，而是真实的地形破坏，打穿之后，那一块障碍就彻底消失了。
' 在很早前我就揣测过这个功能的实现原理，无奈，没想出个所以然。最近，脑细胞突然沸腾了一下，把我的思绪拉回到这个问题上。
简单分析
爆炸前.png
爆炸后.png
' 上图标记的箭头则是地形区域，地形区域由一个多边形构成，而破坏地形就是修改这个多边形。因而，只要实现通过多边形Ａ去裁剪多边形Ｂ就可以了，多边形A是炮弹产生的爆炸范围，多边形B则是地形（虽然爆炸范围看起来是圆的，但其实完全可以用多边形模拟，从而降低算法复杂度以及算法开销）。
理解到这就可以写算法了。
// clip_shape.h
#pragma once
#include "../base.h"
#include "../math/vec4.h"
#include "../math/polygon.h"
class ClipShape {
public:
struct CrossPoint {
Vec4 mPoint; // 交点
size_t mLinkA; // 交点上游
size_t mLinkB; // 交点下游
CrossPoint(
const Vec4 & point = Vec4(),
const size_t linkA = 0,
const size_t linkB = 0)
: mPoint(point)
, mLinkA(linkA)
, mLinkB(linkB)
{ }
};
using Points = std::vector<Vec4>;
using ClipLine = std::vector<Vec4>;
using CrossResult = std::vector<CrossPoint>;
using ClipResult = std::pair<ClipShape, ClipShape>;
public:
ClipShape();
ClipShape(ClipShape && other);
ClipShape & operator=(ClipShape && other);
ClipShape(const ClipShape & other) = default;
ClipShape & operator=(const ClipShape & other) = default;
void Clear();
void Push(const Vec4 & point);
void Init(const Points & points);
const Points & GetPoints() const;
bool IsBeContains(const ClipLine & clipLine) const;
std::vector<ClipShape> Clip(ClipLine clipLine) const;
private:
bool Max(const CrossPoint & cp1, const CrossPoint & cp2) const;
CrossResult CheckCross(const Vec4 & a, const Vec4 & b) const;
CrossResult CheckCross(const ClipLine & clipLine) const;
bool CheckCross(const CrossResult & crossResult) const;
ClipShape ClipA(const CrossResult & crossResult) const;
ClipShape ClipB(const CrossResult & crossResult) const;
void FlipCross(CrossResult & result) const;
bool Roll(ClipLine & clipLine) const;
private:
Points _points;
};
// clip_shape.cpp
#include "clip_shape.h"
#include "../math/polygon.h"
ClipShape::ClipShape()
{ }
ClipShape::ClipShape(ClipShape && other)
{
*this = std::move(other);
}
ClipShape & ClipShape::operator=(ClipShape && other)
{
_points = std::move(other._points);
return *this;
}
void ClipShape::Clear()
{
_points.clear();
}
void ClipShape::Push(const Vec4 & point)
{
_points.push_back(point);
}
void ClipShape::Init(const Points & points)
{
std::copy(points.begin(), points.end(), std::back_inserter(_points));
}
const ClipShape::Points & ClipShape::GetPoints() const
{
return _points;
}
bool ClipShape::IsBeContains(const ClipLine & clipLine) const
{
auto fn = [&](const Vec4 & point)
{
return Polygon::IsContains(point, clipLine);
};
return std::all_of(_points.begin(), _points.end(), fn);
}
std::vector<ClipShape> ClipShape::Clip(ClipLine clipLine) const
{
std::vector<ClipShape> result;
if (Roll(clipLine))
{
auto crossResult = CheckCross(clipLine);
if (!crossResult.empty())
{
FlipCross(crossResult);
auto clipA = ClipA(crossResult);
if (!clipA.IsBeContains(clipLine))
{
auto ret1 = clipA.Clip(clipLine);
std::copy(
std::make_move_iterator(ret1.begin()),
std::make_move_iterator(ret1.end()),
std::back_inserter(result));
if (ret1.empty()) { result.push_back(clipA); }
}
auto clipB = ClipB(crossResult);
if (!clipB.IsBeContains(clipLine))
{
auto ret2 = clipB.Clip(clipLine);
std::copy(
std::make_move_iterator(ret2.begin()),
std::make_move_iterator(ret2.end()),
std::back_inserter(result));
if (ret2.empty()) { result.push_back(clipB); }
}
}
}
return std::move(result);
}
bool ClipShape::Max(const CrossPoint & cp1, const CrossPoint & cp2) const
{
assert(cp1.mLinkA != cp1.mLinkB);
assert(cp2.mLinkA != cp2.mLinkB);
assert(cp1.mPoint != cp2.mPoint);
assert(cp1.mLinkA == cp2.mLinkA && cp1.mLinkB == cp2.mLinkB ||
cp1.mLinkA != cp2.mLinkA && cp1.mLinkB != cp2.mLinkB);
return cp1.mLinkA != cp2.mLinkA && cp1.mLinkA < cp2.mLinkA ||
cp1.mLinkA == cp2.mLinkA &&
_points.at(cp1.mLinkA).Unlerp(_points.at(cp1.mLinkB), cp1.mPoint) <
_points.at(cp2.mLinkA).Unlerp(_points.at(cp2.mLinkB), cp2.mPoint);
}
ClipShape::CrossResult ClipShape::CheckCross(const Vec4 & a, const Vec4 & b) const
{
CrossResult result;
auto crossA = 0.0;
auto crossB = 0.0;
auto size = _points.size();
for (auto i = 0; i != size; ++i)
{
auto & p1 = _points.at(INDEX<0>(i, size));
auto & p2 = _points.at(INDEX<1>(i, size));
if (Polygon::IsCross(a, b, p1, p2, &crossA, &crossB))
{
result.emplace_back(
p1.Lerp(p2, crossB),
INDEX<0>(i, size),
INDEX<1>(i, size));
}
}
auto fn = [&](
const CrossResult::value_type & cross1,
const CrossResult::value_type & cross2)
{
return (cross1.mPoint - a).LengthSqrt()
< (cross2.mPoint - a).LengthSqrt();
};
std::sort(result.begin(), result.end(), fn);
return std::move(result);
}
ClipShape::CrossResult ClipShape::CheckCross(const ClipLine & clipLine) const
{
CrossResult result;
auto size = clipLine.size();
for (auto i = 0; i != size; ++i)
{
auto & a = clipLine.at(INDEX<0>(i, size));
auto & b = clipLine.at(INDEX<1>(i, size));
auto points = CheckCross(a, b);
if (!points.empty())
{
for (auto & point : points)
{
result.push_back(point);
if (result.size() > 1)
{
if (CheckCross(result)) { goto exit; }
result.erase(result.begin(), std::prev(result.end()));
}
}
if (result.size() == 1 && result.back().mPoint != b)
{ result.emplace_back(b); }
}
else if (!result.empty())
{
if (result.back().mPoint != a)
{ result.emplace_back(a); }
if (result.back().mPoint != b)
{ result.emplace_back(b); }
}
}
result.clear();
exit:
if (!result.empty() &&
result.front().mPoint == result.back().mPoint)
{ result.clear(); }
return std::move(result);
}
bool ClipShape::CheckCross(const CrossResult & crossResult) const
{
for (auto i = 0; i != crossResult.size() - 1; ++i)
{
auto & a = crossResult.at(i );
auto & b = crossResult.at(i + 1);
if (!Polygon::IsContains(a.mPoint, b.mPoint, _points))
{ return false; }
}
return true;
}
ClipShape ClipShape::ClipA(const CrossResult & crossResult) const
{
ClipShape result;
auto & front = crossResult.front();
auto & back = crossResult.back();
// points => clipLine
if (front.mPoint != _points.front())
{
result.Push(_points.front());
}
for (auto i = 1;
i != front.mLinkB &&
i != _points.size(); ++i)
{
result.Push(_points.at(i));
}
// append clipLine
if (result.GetPoints().empty() ||
result.GetPoints().back() != front.mPoint)
{
result.Push(front.mPoint);
}
for (auto i = 1; i != crossResult.size(); ++i)
{
result.Push(crossResult.at(i).mPoint);
}
// clipLine => points
if (back.mLinkB != 0)
{
auto i = _points.at(back.mLinkB) == result.GetPoints().back()
? back.mLinkB + 1
: back.mLinkB;
for (; i != _points.size(); ++i)
{ result.Push(_points.at(i)); }
}
return std::move(result);
}
ClipShape ClipShape::ClipB(const CrossResult & crossResult) const
{
ClipShape result;
auto & front = crossResult.front();
auto & back = crossResult.back();
for (auto
i = front.mLinkB;
i != back.mLinkB &&
i != _points.size(); ++i)
{
result.Push(_points.at(i));
}
for (auto it = crossResult.rbegin(); it != crossResult.rend(); ++it)
{
result.Push(it->mPoint);
}
return std::move(result);
}
void ClipShape::FlipCross(CrossResult & result) const
{
if (!Max(result.front(), result.back()))
{
std::reverse(result.begin(), result.end());
}
}
bool ClipShape::Roll(ClipLine & clipLine) const
{
if (Polygon::IsContains(clipLine.front(), _points))
{
auto fn = [&](const Vec4 & point)
{
return !Polygon::IsContains(point, _points);
};
auto it = std::find_if(clipLine.begin(), clipLine.end(), fn);
if (it == clipLine.end()) { return false; }
std::rotate(clipLine.begin(), it, clipLine.end());
}
return true;
}
算法效果.gif
即使在今天，我依然觉得这个机制可以创造很多玩法，当年《百战天虫》可就是靠这一特色大红大紫，而《弹弹堂》正是借鉴了《百战天虫》。
网友评论