在坐标系中放置20个元素的最佳方式，相邻元素是唯一的

Question

这个问题是关于libGDX的，但我认为它实际上更多地与Java/算法有关。

我的游戏的一部分包括将预定义的30个元素列表中的20个元素放在屏幕上（实际上是一个坐标系）的20个部分预定义的地方。我所说的部分预定义是指它们是为每个屏幕预定义的，但可能有几十个屏幕，所以它们可以像随机一样被很好地处理。元素将随机选择，但彼此靠近的元素必须是唯一的。我所说的"近"是指在某个任意定义的距离X的范围内。实际上，每个地方都有大约3个"近邻居"。

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

1. 计算所有位置之间的距离。如果a和B之间的给定距离小于X，则在地图中放置两个条目——一个（a，B）和一个（B，a）
2. 现在开始用元素填充这些地方
3. 对于每个地方，使用点1的地图创建一个包含所有邻居的列表（我们称之为N-list）
4. 为每个地方创建一个临时列表，其中包含所有可能的（30）个元素（我们称之为E-list）
5. 从电子列表中获取随机元素
6. 遍历N列表。对于列表中的每个位置，获取当前所在的元素（如果有的话）。为此，需要一个（位置、元素）映射，因此它将随着算法的进展而填充
7. 如果找到的元素等于当前随机元素，则将该元素从E列表中移除，将该位置从N列表中移除并返回到点5
8. 继续操作，直到所有位置都填满为止

步骤1实际上是一个单独的算法，可能可以调整，例如，如果我们计算a->B距离，我们不需要计算B->a，但需要一个额外的地图来存储计算信息，等等。

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

附言：也许我使用的术语可以更好地选择，但我不是母语人士，也不知道英语数学术语：-）

Answer 1

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

首先，创建一个位置地图，其中键是位置位置（或位置本身），值是位于近距离内的位置的父对象列表。是的，它将有多个父母，而不是孩子，事实上是一样的，但正如我们将看到的，父母更适合这里。

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);
    }
}

现在我们有了所有有父母的地方的地图。接下来我们要做的是：如果这个地方没有父母，它可以自由选择任何随机元素。如果它确实有父元素，它会检查父元素拥有哪些元素，并减少可用的元素集。在集合被缩减之后，可以从中选择任何随机元素

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);
}