- °³¿ä
- 2D ¶óÀÎ ¾Ë°í¸®Áò
- 3D ¶óÀÎ ¾Ë°í¸®Áò
- ¿ø ¾Ë°í¸®Áò
- ¸µÅ©
1 °³¿ä
¿ø·¡´Â 2D ±×·¡ÇÈ¿¡¼ »ç¿ëÇÏ´Â ¾Ë°í¸®ÁòÀÌÁö¸¸, PathFinding µî ¿©·¯ °¡Áö ¸ñÀûÀ¸·Î »ç¿ëÇÒ ¼ö ÀÖ´Ù.
2 2D ¶óÀÎ ¾Ë°í¸®Áò
struct POINT2
{
int x, z;
POINT2(int _x = 0, int _z = 0) : x(_x), z(_z) {}
};
void GetPointsInLine(
int x0, int y0, int x1, int y1, std::vector<POINT2>& line)
{
// ½ÃÀÛÁ¡.
int x = x0, y = y0;
// ¶óÀÎÀÇ ±â¿ï±â.
int dx = x1-x0, dy = y1-y0;
// ¶óÀÎÀÇ ±â¿ï±â¿¡ µû¶ó ¿É¼Â °áÁ¤.
int sx = (dx > 0 ? 1 : (dx < 0 ? -1 : 0));
int sy = (dy > 0 ? 1 : (dy < 0 ? -1 : 0));
// º¹¼¿ ¼±ÅÃÀ» À§ÇÑ ÆÄ¶ó¹ÌÅÍ °è»ê.
dx = abs(dx);
dy = abs(dy);
int ax = 2 * dx, ay = 2 * dy;
int decx, decy;
// °¡Àå ±ä ÃàÀ» ÆÇ´ÜÇÑ´Ù..
int maximum = dx, var = 0;
if (dy > maximum) { maximum = dy; var = 1; }
// ºê·¹¼¾ÇÜ.
if (var == 0)
{
for (decy=ay-dx; ; x += sx, decy += ay)
{
line.push_back(POINT2(x, y));
if (x == x1) break;
if (decy >= 0) { decy -= ax; y += sy; }
}
}
else
{
for (decx=ax-dy; ; y += sy, decx += ax)
{
line.push_back(POINT2(x, y));
if (y == y1) break;
if (decx >= 0) { decx -= ay; x += sx; }
}
}
}
3 3D ¶óÀÎ ¾Ë°í¸®Áò
3D ¶óÀÎ °°Àº °æ¿ì¿¡´Â ·»´õ¸µ¿ëÀ̶ó±âº¸´Ù´Â ¹º°¡ ´Ù¸¥ 󸮸¦ À§ÇÑ °ÍÀÌ´Ù. "Voxel Traversal"·Î °Ë»öÇØ º¸±â ¹Ù¶õ´Ù.
struct POINT3
{
int x, y, z;
POINT3(int _x = 0, int _y = 0, int _z = 0) : x(_x), y(_y), z(_z) {}
};
void GetPointsInLine(
int x0, int y0, int z0, int x1, int y1, int z1, std::vector<POINT3>& line)
{
// ½ÃÀÛÁ¡.
int x = x0, y = y0, z = z0;
// ¶óÀÎÀÇ ±â¿ï±â.
int dx = x1 - x0, dy = y1 - y0, dz = z1 - z0;
// ¶óÀÎÀÇ ±â¿ï±â¿¡ µû¶ó ¿É¼Â °áÁ¤.
int sx = dx > 0 ? 1 : (dx < 0 ? -1 : 0);
int sy = dy > 0 ? 1 : (dy < 0 ? -1 : 0);
int sz = dz > 0 ? 1 : (dz < 0 ? -1 : 0);
// º¹¼¿ ¼±ÅÃÀ» À§ÇÑ ÆÄ¶ó¹ÌÅÍ °è»ê.
dx = abs(dx);
dy = abs(dy);
dz = abs(dz);
int ax = 2 * dx, ay = 2 * dy, az = 2 * dz;
int decx, decy, decz;
// °¡Àå ±ä ÃàÀ» ÆÇ´ÜÇÑ´Ù.
int maximum = dx, var = 0;
if (dy > maximum) { maximum = dy; var = 1; }
if (dz > maximum) { maximum = dz; var = 2; }
// ºê·¹¼¾ÇÜ.
if (var == 0)
{
for (decy=ay-dx, decz=az-dx; ; x += sx, decy += ay, decz += az)
{
line.push_back(POINT3(x, y, z));
if (x == x1) break;
if (decy >= 0) { decy -= ax; y += sy; }
if (decz >= 0) { decz -= ax; z += sz; }
}
}
else if (var == 1)
{
for (decx=ax-dy, decz=az-dy; ; y += sy, decx += ax, decz += az)
{
line.push_back(POINT3(x, y, z));
if (y == y1) break;
if (decx >= 0) { decx -= ay; x += sx; }
if (decz >= 0) { decz -= ay; z += sz; }
}
}
else
{
for (decx=ax-dz, decy=ay-dz; ; z += sz, decx += ax, decy += ay)
{
line.push_back(POINT3(x, y, z));
if (z == z1) break;
if (decx >= 0) { decx -= az; x += sx; }
if (decy >= 0) { decy -= az; y += sy; }
}
}
}
4 ¿ø ¾Ë°í¸®Áò
struct POINT2
{
int x, z;
POINT2(int _x = 0, int _z = 0) : x(_x), z(_z) {}
};
void GetPointsInCircle(int cx, int cy, int radius, std::vector<POINT2>& circle)
{
if (radius <= 0) return;
int tx = 0;
int ty = radius;
int tp = 3 - 2 * radius;
do
{
circle.push_back(POINT2(cx + tx, cy + ty));
circle.push_back(POINT2(cx + ty, cy + tx));
circle.push_back(POINT2(cx + ty, cy - tx));
circle.push_back(POINT2(cx + tx, cy - ty));
circle.push_back(POINT2(cx - tx, cy - ty));
circle.push_back(POINT2(cx - ty, cy - tx));
circle.push_back(POINT2(cx - ty, cy + tx));
circle.push_back(POINT2(cx - tx, cy + ty));
tx++;
if (tp < 0)
{
tp += 4 * tx + 6;
}
else
{
ty--;
tp += 4 * (tx - ty) + 10;
}
}
while (tx <= ty);
}
5 ¸µÅ©
SeriousMoin v1 (koMoinMoin 1.0a4 Modified)