1. 首页
  2. 问答
  3. 简单群集算法2D。检测点的团块

简单群集算法2D。检测点的团块

2012-10-04 18 views
2

任何人都知道一个简单的算法来实现在C＃中检测2D游戏中的怪物群体。简单群集算法2D。检测点的团块

EX： 100范围周围的char有怪物。我想检测哪些怪物在彼此的范围2内，并且如果至少有5个怪物在一起，则在该位置使用效果区域技能。否则使用单目标技能。

指向实现的链接会很棒，最好是C＃。我只是迷失在阅读维基百科文章。

编辑： “你的问题是不完整的，你想要做什么？你想找到所有的团体？最大的团体？任何团体，如果有团体，没有其他？请更具体。 -gilad hoch

我想找到围绕主角的100个范围内的所有群组。如果至少有5个或更多的怪物在彼此的2个范围内，或者距离中心怪物10个范围内，则应该组成这些团体。

所以结果应该可能是一个新的组列表或潜在目标位置列表。

来源

2012-10-04 Vans S

+0

你的问题是不完整的。你想做什么**完全**？你想找到_all_组？ _biggest_组？如果有团体，是否有其他团体？请更具体。 –

回答

1

我最近实施的Efraty在this paper给出的算法，通过考虑解决这个问题的实现以给定点为中心的半径为2的圆的交点。简而言之，如果您按顺时针顺序排列两个圆相交的点，那么您可以执行类似于线扫的操作，以确定需要启动炸弹（或AoE法术）的点，以便点击最多敌人。实现是这样的：

#include <stdio.h> 
#include <cmath> 
#include <algorithm> 

using namespace std; 

#define INF 1e16 
#define eps 1e-8 
#define MAXN 210 
#define RADIUS 2 

struct point { 
    double x,y; 

    point() {} 
    point(double xx, double yy) : x(xx), y(yy) {} 

    point operator*(double ot) { 
     return point(x*ot, y*ot); 
    } 

    point operator+(point ot) { 
     return point(x+ot.x, y+ot.y); 
    } 

    point operator-(point ot) { 
     return point(x-ot.x, y-ot.y); 
    } 

    point operator/(double ot) { 
     return point(x/ot, y/ot); 
    } 
}; 

struct inter { 
    double x,y; 
    bool entry; 
    double comp; 

    bool operator< (inter ot) const { 
     return comp < ot.comp; 
    } 
}; 

double dist(point a, point b) { 
    double dx = a.x-b.x; 
    double dy = a.y-b.y; 
    return sqrt(dx*dx+dy*dy); 
} 

int N,K; 
point p[MAXN]; 
inter it[2*MAXN]; 


struct distst { 
    int id, dst; 
    bool operator<(distst ot) const {return dst<ot.dst;} 
}; 

distst dst[200][200]; 
point best_point; 

double calc_depth(double r, int i) { 
    int left_inter = 0; 

    point left = p[i]; 
    left.y -= r; 
    best_point = left; 

    int tam = 0; 

    for (int k = 0; k < N; k++) { 
     int j = dst[i][k].id; 
     if (i==j) continue; 

     double d = dist(p[i], p[j]); 

     if (d > 2*r + eps) break; 
     if (fabs(d)<eps) { 
      left_inter++; 
      continue; 
     } 

     bool is_left = dist(p[j], left) < r+eps; 
     if (is_left) { 
      left_inter++; 
     } 

     double a = (d*d)/(2*d); 

     point diff = p[j] - p[i]; 
     point p2 = p[i] + (diff * a)/d; 

     double h = sqrt(r*r - a*a); 

     it[tam].x = p2.x + h*(p[j].y - p[i].y)/d; 
     it[tam].y = p2.y - h*(p[j].x - p[i].x)/d; 

     it[tam+1].x = p2.x - h*(p[j].y - p[i].y)/d; 
     it[tam+1].y = p2.y + h*(p[j].x - p[i].x)/d; 

     it[tam].x -= p[i].x; 
     it[tam].y -= p[i].y; 
     it[tam+1].x -= p[i].x; 
     it[tam+1].y -= p[i].y; 

     it[tam].comp = atan2(it[tam].x, it[tam].y); 
     it[tam+1].comp = atan2(it[tam+1].x, it[tam+1].y); 

     if (it[tam] < it[tam+1]) { 
      it[tam].entry = true; 
      it[tam+1].entry = false; 
     } 
     else { 
      it[tam].entry = false; 
      it[tam+1].entry = true; 
     } 

     if (is_left) { 
      swap(it[tam].entry, it[tam+1].entry); 
     } 

     tam+=2; 
    } 

    int curr,best; 
    curr = best = left_inter; 

    sort(it,it+tam); 

    for (int j = 0; j < tam; j++) { 
     if (it[j].entry) curr++; 
     else curr--; 

     if (curr > best) { 
      best = curr; 
      best_point = point(it[j].x, it[j].y); 
     } 
    } 

    return best; 
} 

int main() { 
    scanf("%d", &N); 
    for (int i = 0; i < N; i++) { 
     scanf("%lf %lf", &p[i].x, &p[i].y); 
    } 

    for (int i = 0; i < N; i++) { 
     for (int j = 0; j < N; j++) { 
      dst[i][j].id = j; 
      dst[i][j].dst = dist(p[i],p[j]); 
     } 
     sort(dst[i],dst[i]+N); 
    } 

    int best = 0; 
    point target = p[0]; 
    for (int i = 0; i < N; i++) { 
     int depth = calc_depth(RADIUS, i); 
     if (depth > best) { 
      best = depth; 
      target = best_point; 
     } 
    } 

    printf("A bomb at (%lf, %lf) will hit %d target(s).\n", target.x, target.y, best+1); 
}

使用范例：

2 (number of points) 
0 0 
3 0 
A bomb at (1.500000, 1.322876) will hit 2 targets.

来源

2012-10-04 22:09:35 ffao

相关问题

 相关问题