将 20 个元素放入坐标系中且相邻元素唯一的最佳方法

Question

这个问题是关于 libGDX，但我认为它实际上更 Java/algorithm 相关。

我的部分游戏包括将 30 个预定义元素列表中的 20 个元素放置在屏幕（实际上是一个坐标系）的 20 个部分预定义的位置。部分预定义的意思是它们是为每个屏幕预定义的，但是可以有几十个屏幕，所以它们可以被视为随机的。元素会随机选取，但距离相近的元素必须是唯一的。我所说的接近是指在某个任意定义的距离 X 的范围内。实际上每个地方将有大约 3 'close neightbours'.

目前我能想到的最好的方法如下：

计算所有地点之间的距离。如果 A 和 B 之间的给定距离小于 X，则在地图中放置两个条目 - 一个 (A,B) 和一个 (B,A)
现在开始用元素填充这些地方
使用第 1 点的地图（我们称之为 N 列表）为每个地点创建一个包含所有邻居的列表
为每个地方创建一个包含所有可能的 (30) 个元素的临时列表（我们称之为 E-list）
从E-list中获取一个随机元素
遍历 N 列表。对于列表中的每个位置，获取当前存在的元素（如果有的话）。为此需要一个（地点，元素）地图，因此它将随着算法的进行而被填充。
如果找到的元素等于当前的随机元素，从E-list中移除这个元素，从N-list中移除这个地方，然后回到第5点
继续进行直到所有位置都填满

第 1 步实际上是一个单独的算法，可能可以进行调整，例如。如果我们计算了 A->B 的距离，我们就不需要计算 B->A，但是那需要一个额外的映射来存储计算信息等。

我想知道您对这种方式的看法，以及您是否有更好的想法。预先感谢您的回答。

P.S。也许我使用的术语可以更好地选择，但我不是母语人士，我不知道英语数学术语:-)

Answer 1

好的，我想我理解了你的解决方案，这就是我最初的想法。但我认为它可以通过消除额外的对和映射来稍微优化（或者可能不:)

首先，创建一个位置地图，其中键是位置位置（或位置本身），值是位置 parents 落入近距离范围内的列表。是的，它将有多个 parents，而不是 children，它实际上是相同的，但 parents 在这里更合适，我们将看到。

ArrayList<Place> place_list; // your list of places here
ArrayList<Element> element_list; // your list of elements here
HashMap<Place,ArrayList<Place>> parent_map = new HashMap<Place,ArrayList<Place>>;
ArrayList<Place> a;

for (int i = 0; i < place_list.size() - 1; i++) {
    Place place1 = place_list.get(i);
    for (int j = i + 1; j < place_list.size(); j++) {
        Place place2 = place_list.get(j);
        int dist = getDistance(place1, place2);
        if (dist > DISTANCE_THRESHOLD) continue;
        // if this place is within range,
        // add parent place to its list and put/update it to the map
        a = parent_map.get(place2);
        if (a == null) a = new ArrayList<Place>();
        a.add(place1);
        parent_map.put(place2, a);
    }
}

现在我们有了包含 parents 所有地点的地图。接下来我们进行如下操作：如果place没有parents，它可以自由选择任意一个随机元素。如果确实有 parents，它会检查 parents 拥有哪些元素并减少可用的元素集。集合缩减后，可以从中任意选择一个元素。

HashMap<Place,Element> used_place_map = new HashMap<Place,Element>(); // key is place, value is assigned element
ArrayList<Element> tmp_element_list;

for (i = 0; i < place_list.size(); i++) {
    Place place = place_list.get(i);
    a = parent_map.get(place);
    if (a == null) { // this place has no parents, use elements freely
        tmp_element_list = element_list;
    } else { // if it has parents, they have already registered their elements in used_place_map
        tmp_element_list = new ArrayList<Element>();
        // create list of available elements, lame
        for (j = 0; j < element_list.size(); j++) tmp_element_list.add(element_list.get(j));
        // now reduce it, very lame, sorry
        for (Place pl : a) {
            Element used_element = used_place_map.get(pl);
            for (j = 0; j < tmp_element_list.size(); j++) {
                if (used_element.equals(tmp_element_list.get(j)) {
                    tmp_element_list.remove(j);
                    break;
                }
            }
        }
    }

    // finally, get the random index on (probably reduced) array
    int element_id = Random.nextInt(tmp_element_list.size());
    Element element = element_list.get(element_id);
    // store our choice as future parent
    used_place_map.put(place, element);
}

将 20 个元素放入坐标系中且相邻元素唯一的最佳方法

Best way to put 20 elements in a coordinate system with neighbouring elements unique

java

algorithm

libgdx