1. 首頁
  2. 問答
  3. 簡單羣集算法2D。檢測點的團塊

簡單羣集算法2D。檢測點的團塊

2012-10-04 16 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

相關問題

 相關問題