0

我正在使用图形数据结构制作 Hunt the Wumpus 游戏。其中的每个顶点都是一个大小为 4 的数组，表示每个方向，北南东西。方向存储在枚举中。当一个顶点与另一个顶点连接时，它的邻接关系应该发生变化，以便它与另一个顶点连接（我仍然对此感到困惑——为什么我的顶点是一个大小为 4 的数组但只有一个方向）。

当我将一个顶点与另一个顶点连接并打印出邻居的数组列表时，我得到了一个奇怪的输出。当我打印未连接的顶点时，我得到邻居的 [null, null, null, null]；当我打印连接的顶点时，我得到 [null，null，null，[null，null，null，null]。我不知道邻居应该是什么——它们应该打印为代表方向枚举索引的整数还是方向？应该打印什么？

import java.util.ArrayList;
import java.util.Collection;

 enum Direction{
    EAST,
    WEST,
    NORTH,
    SOUTH
}
public class Vertex extends Agent implements Comparable<Vertex>{
    private Vertex[] connections;
    private Direction dir;
    private int cost;
    private boolean marked;


    public Vertex(double x0, double y0){
        super( x0,  y0);
        connections = new Vertex[4];
        this.dir = dir;
        this.cost = cost;
        this.marked = marked;
    }

    public Direction opposite(Direction dir) {
    //that returns the compass opposite of a direction (i.e. South for North...)
        if(dir == Direction.EAST){
            dir = Direction.WEST;
        }
        else if(dir == Direction.WEST){
            dir = Direction.EAST;
        }
        else if(dir == Direction.NORTH){
            dir = Direction.SOUTH;
        }
        else dir = Direction.NORTH;

        return dir;
    }
    void connect(Vertex other, Direction dir){
    //modify the object's adjacency list/map so that it connects with the other Vertex. This is a uni-directional link.
        connections[dir.ordinal()] = other;

        }

    Vertex getNeighbor(Direction dir){
    //returns the Vertex in the specified direction or null.
        return this.connections[dir.ordinal()];
        }

    Collection getNeighbors(){
    //returns a Collection, which could be an ArrayList, of all of the object's neighbors.
        ArrayList<Vertex> neighborList = new ArrayList<Vertex>();
            for (Direction dir: Direction.values()){
                neighborList.add(this.getNeighbor(dir));
            }

            return neighborList;
        }

    public int getCost(){
        return this.cost;
    }

    public int setCost(int c){
        return this.cost = c;
    }

    public boolean getMarked(){
        return this.marked;
    }

    public boolean setMarked(boolean m){
        return this.marked = m;
    }

    public int compareTo(Vertex other){
        return (this.cost - other.cost);
    }

    /*
    * returns a string containing the number of neighbors, the cost, and the marked flag
    */
    public String toString(){
        String s = "";
        s += this.getNeighbors() + "\n" ;
        s += "cost: " + this.cost + "\n";
        s += "marked: " + this.marked;
        return s;

    }

    public static void main (String args[]){
        Vertex newE = new Vertex(0.5, 0.5);
        Vertex newerE = new Vertex(0.123, 1.56);
        newE.connect(newerE, Direction.SOUTH);
        newE.setCost(1);
        newE.setMarked(true);
        System.out.println(newE.toString());
    }

}
4

1 回答 1

0

好吧，当您得到输出 [null, null, null, [null, null, null, null]] 时，您就知道有一个对您连接的节点的引用。所以第二个阵列由第一个阵列连接，但反之则不然。因为你的代码没有连接第二个节点，但第一个节点是连接的。我认为你不应该打印节点列表，这会导致问题。

在一种情况下，节点连接在一起，因此您将父节点连接到子节点，将子节点连接到父节点。当您现在将其打印出来时，您将获得递归执行。

[null，null，null，child[父[[null，null，null，child[...]]]，null，null，null]]

这将导致异常。您可以为此使用标识符，例如 ID。所以你只需打印出连接对象的 ID，或者可能是一个位置 ->

[1,null,null,2]

[(x,y),(x,y),(x,y),(x,y)]

只需使用一些东西来识别节点，之后您就可以轻松查看节点是否存在或为空。

所以另一点是，你知道你有 4 个点要连接，所以为什么不使用：

private Node north;
private Node south;
private Node west;
private Node east;

以后这会更容易，并且您不必再使用此枚举。而且您还可以删除 Vertex 类中的方向，顺便说一下，这也会混淆 Vertex 是一个点，而点没有方向:)

或者，您只需为此使用 2x2 网格，例如：

private Node[][]

您可以通过您知道在哪里访问邻居的位置来指定网格的大小。例如坐标 [1,1] 由 [0,1],[1,0],[2,1],[1,2] 连接。您还可以轻松打印出整个网格。

等距网格示例

您可以将此计算放入算法中，以检查邻居。因此，您不必在每个节点类中保存节点。例如，您可以通过访问此对象获得的渲染位置（如果您想渲染它）：

node[1][2].getX();

我还建议你看看 Tree-Structures :)

于 2018-12-11T10:08:39.423 回答