群破坏 [英] Swarm Destruction

问题描述

嗯，这听起来听起来像是一个怪异的算法讨论，虽然只是我不介意看到抽象的实现，但这只是理论上的讨论.在这里.

在2D游戏中，您在2D空间中有一个玩家和敌人.玩家已进行远程攻击，因为PlayerRange和敌人都有自己的射程，但可以说他们的EnemyRange射程相同.我感兴趣的是如何将一团敌人分成几团，然后圈出他们以致死亡.这是我的解决方案:

首先，获取敌人之间的距离，将其视为组中彼此之间的最小-最大范围，然后将敌人云分成子云.完成此操作后，为每个子组创建凸包，并确定最接近的子组播放器.如果玩家在其中任何一个内，请找到凸包的最近线，并按照法线的方向跟随，直到玩家位于该子组之外.

在外面时，使用PlayerRange构造扩展的凸包，并逐点跟踪直到凸包不再(即仅剩2个敌人).一旦这样，就可以使用简单的球体作为围绕它们的路径，直到它们被破坏为止.

现在，所有这些都假定子组和凸包的计算是在每帧的基础上进行的，因为敌人确实会自行移动并且可能会从一个子组合并到另一个子组.这就提出了一个关于下一个要点的问题.我认为解决此问题的一个好方法是选择围绕凸包的下一个逆时针或顺时针点，然后朝它前进.

您如何看待，这是做环游死亡"的好方法还是还有其他方法?

Well, this might sound as a weird algorithm discussion, it''s a theoretical one, although I wouldn''t mind seeing the abstract implementation. Here it is.

In a 2D game, you have a player and enemies in 2D space. A player has ranged attack as PlayerRange and enemies have their own range(s), but let''s say they all have the same range of EnemyRange. What I''m interested in is how to separate a cloud of enemies into groups and circle them to death. here is my solution:

First, acquire range between enemies that will be considered as min-max range to be between each other in a group, and separate cloud of enemies into sub-clouds. Once this is done, create convex hull for each of sub-groups and determine closest sub-group player is to. If player is inside any of those, find closest line of the convex hull and follow in direction of normal to it until player is outside the sub-group.

While outside, construct expanded convex hull using PlayerRange and follow it from point to point until convex hull is no more (i.e. has only 2 enemies left). Once it is so, use simple sphere as path to follow around them until they are destroyed.

Now, all this assumes that sub-group and convex hull calculations are done on a per-frame basis, because enemies do move on their own and may merge from one sub-group to another. This raises a question as to which next point to go to. I think a good solution for this would be to choose next counter- or clockwise point around convex hull and go towards it.

What do you think, is this a good way of doing "circling to death" or are there others?

推荐答案

您的问题不是很清楚，但您似乎希望通过某种方式将敌人分组为云团以包围它们.

一种方法是聚类分析.首先列出所有敌人并列出他们之间的距离.将两个最近的敌人分组.聚类成为带有质心(平均X和Y坐标)的新敌人".继续对敌人进行分组，直到最接近的敌人超过某个阈值为止.剩下的敌人群就是你的密云.

如果要分组的敌人很多，则可以使用KD树( http://en.wikipedia.org/wiki/Kd-树 [

Your question isn''t very clear, but it appears you want some way to group enemies into clouds to surround them.

One approach is Cluster Analysis. Start with a list of all enemies and a table of the distances among them. Group the two closest enemies into a cluster. The cluster becomes a new "enemy" with a centroid (average X and Y coordinates). Continue grouping enemies until the closest are above some threshold. The clusters of enemies remaining are your compact clouds.

If you have many enemies to group, a KD-tree (http://en.wikipedia.org/wiki/Kd-tree[^]) is efficient for finding nearest neighbors.

这篇关于群破坏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！