2

2Dゲームでモンスターグループを検出するためにC＃で実装する簡単なアルゴリズムを誰もが知っています。

例：モンスターがいるチャーの周りの100の範囲。どのモンスターがお互いの範囲2内にあるかを検出したいのですが、少なくとも5つ一緒にいる場合は、その場所で効果範囲スキルを使用します。それ以外の場合は、単一ターゲットスキルを使用します。

実装へのリンクは素晴らしいでしょう、できればC＃です。ウィキペディアの記事を読んで迷子になりました。

編集：「あなたの質問は不完全です。あなたは正確に何をしたいですか？すべてのグループを見つけたいですか？最大のグループですか？グループがある場合は他のグループはありませんか？もっと具体的にしてください。」-gilad hoch

主人公の周りの100単位の範囲内のすべてのグループを見つけたいです。グループは、少なくとも5つ以上のモンスターがすべて互いに2の範囲内にある場合、または中央のモンスターから10の範囲内にある場合に形成する必要があります。

したがって、結果はおそらく新しいグループのリストまたは潜在的なターゲットの場所のリストになるはずです。

4

2 に答える 2

2

非常に単純なクラスタリングアルゴリズムはk-meanアルゴリズムです。のようなものです

  • ランダムなポイントを作成する
  • すべてのポイントを最も近いポイントに割り当て、グループを作成します
  • 元のポイントをグループの中央に再配置します
  • 最後の2つの手順を数回実行します。

たとえば、ここで見つけることができる実装、または単に「kmeanc＃」をグーグルで検索する

http://kunuk.wordpress.com/2011/09/20/markerclusterer-with-c-example-and-html-canvas-part-3/

于 2012-10-04T21:54:46.183 に答える
1

私は最近、Efratyによってこの論文で与えられたアルゴリズムを実装しました。これは、与えられた各点を中心とする半径2の円の交点を考慮することによって問題を解決します。簡単に言うと、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-04T22:09:35.300 に答える