时间戳

首页 > 解决方案 > 如何从 Java 中的字符串列表中为游戏的世界地图绘制平面图

java - 如何从 Java 中的字符串列表中为游戏的世界地图绘制平面图

问题描述

基本上，我有一款游戏，其中包含 116 个地区的大地图。每个地区都有一个名称、一些其他属性以及一个关联的 String[] 及其邻居的名称。并非每个区域都相互连接（我认为一个区域至少有 1 个连接，最多有 9 个连接）。

因此，像图一样绘制区域应该会产生平面图。我尝试使用 JUNG 库（如本网站和其他网站上的建议）这样做，但他们拥有的每个布局算法只会导致一个有很多交叉边的图形，这正是我想要避免的。在我的代码下方（Territory 类再次具有 name 属性和其邻居名称的 String[]。传递给该方法的地图以区域名称作为键）。

所以我的问题是：有没有一种布局算法可以用来从领土地图中绘制平面图？我应该使用的另一个库？我可以遵循的教程？提前谢谢各位！

public static void drawMap(Map<String, Territory> allTerritories) {
    // TODO Auto-generated constructor stub
    DirectedSparseGraph<String, String> g = new DirectedSparseGraph<>();

    Game game = new Game();
    int counter = 0;
    for (Territory t : allTerritories.values()) {
        g.addVertex(t.getName() + "(" + game.getID(t.getColor()) + ")");
        for (String s : t.getNeighbours()) {
            Territory neighbour = allTerritories.get(s);
            g.addEdge("Edge" + counter, t.getName() + "(" + game.getID(t.getColor()) + ")",
                    s + "(" + game.getID(neighbour.getColor()) + ")");
            counter++;
        }
    }

    Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize();
    int width = screenSize.width;
    int height = screenSize.height;
    // KKLayout does a sort of good job

    CircleLayout<String, String> layout = new CircleLayout<String, String>(g);
    VisualizationImageServer<String, String> vv = new VisualizationImageServer<String, String>(layout,
            new Dimension(width, height));

    Function<String, String> transformer = new Function<String, String>() {
        @Override
        public String apply(String arg0) {
            if (arg0.contains("-1")) {
                String noNumber = arg0.replace(arg0.substring(arg0.length() - 4), "");
                return noNumber;
            } else {
                String noNumber = arg0.replace(arg0.substring(arg0.length() - 3), "");
                return noNumber;
            }

        }
    };
    vv.getRenderContext().setVertexLabelTransformer((Function<? super String, String>) transformer);

    vv.getRenderer().setVertexRenderer(new MyRenderer());

    // The following code adds capability for mouse picking of
    // vertices/edges. Vertices can even be moved!

    JFrame frame = new JFrame();
    frame.getContentPane().add(vv);
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.pack();
    frame.setVisible(true);
}'

（使用 JUNG 库，我的进口清单：

import edu.uci.ics.jung.algorithms.layout.CircleLayout;
import edu.uci.ics.jung.algorithms.layout.ISOMLayout;
import edu.uci.ics.jung.algorithms.layout.Layout;
import edu.uci.ics.jung.graph.DirectedSparseGraph;
import edu.uci.ics.jung.visualization.RenderContext;
import edu.uci.ics.jung.visualization.VisualizationImageServer;
import edu.uci.ics.jung.visualization.renderers.Renderer;
import edu.uci.ics.jung.visualization.transform.shape.GraphicsDecorator;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Rectangle;
import java.awt.Shape;
import java.awt.Toolkit;
import java.awt.geom.Point2D;
import java.util.Map;

import javax.swing.JFrame;

game.getID() 方法是我在另一个类中编写的一种方法，用于将颜色（与区域相关，灰色、橙色、洋红色或蓝色）转换为整数。顶点也应该是我的代码实际完成的那种颜色！

我尝试使用以下布局：KKLayout、FRLayout、SpringLayout、ISOMLayout、CircleLayout。

标签： javagraphjungplanar-graph

解决方案

这里有两种情况：

  1. 您有 115 个地区的实际（地理）地图，或
  2. 您只知道它们之间的边界关系（也就是说，您所知道的就是哪些领土与其他领土接壤）。

在案例 1 中，您可以根据区域的位置进行布局：为每个区域选择一个点，创建一个具有该位置的节点。您可以使用 指定已知节点位置StaticLayout。WorldMapGraphDemo中有一个例子。

在情况 2 中，根据图形的生成方式，您实际上可能无法确定它是平面的；你还没有表明你是怎么知道的。如果您不确定，可以使用以下算法之一对其进行测试：https ://en.wikipedia.org/wiki/Planarity_testing

如果您发现图形确实是平面的，并且 JUNG 布局算法对您没有帮助，我没有任何直接的建议。避免图形布局中的边缘交叉通常是一个NP-hard 问题，并且这些算法都没有尝试直接解决它。

推荐阅读