2

任何人都知道用 C# 实现一个简单的算法来检测 2D 游戏中的怪物组。

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

一个实现的链接会很棒，最好是 C#。我只是迷失了阅读维基百科的文章。

编辑：“你的问题不完整。你到底想做什么？你想找到所有组吗？最大的组？任何组，如果有组，没有其他组？请更具体。” -吉拉德霍赫

我想找到主角周围 100 个单位范围内的所有组。如果至少有 5 个或更多的怪物都在彼此 2 范围内，或者可能在距离中心怪物 10 范围内，则应组成组。

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

4

2 回答 2

2

a very simple clustering algorithm is the k-mean algorithm. it is like

  • create random points
  • assign all points to the nearest point, and create groups
  • relocate the original points to the middle of the groups
  • do the last two steps several times.

an implementation you can find for example here, or just google for "kmean c#"

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 的圆的交点来解决这个问题。简单来说，如果你把两个圆相交的点按顺时针顺序排列，那么你可以做类似扫线的事情来找出需要发射炸弹（或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 回答