9

我编写了一个 2D 平台游戏，我需要有（最多 4 个）门的房间。我用 Java 编写，但语言无关紧要。

每个房间可以有 4 扇门，分别位于顶部、底部和侧面。我称它们为NORTH,SOUTH和。当我建造一个房间时，我只给它一个整数，整数中的每一位代表一扇门。EASTWEST

例如，如果我想要一个有 3 扇门的房间（一扇在北，一扇在东，在西），我给房间编号：11（二进制 1011）。

出于这个原因，每扇门都有一个整数，用来识别它。

NORTH = 8;//1000
SOUTH = 4;//0100
EAST =  2;//0010
WEST =  1;//0001

如果我生成一个房间，我会给它这些标识符的组合。

例如：前面提到的房间将获得标识符

doorStock = NORTH | EAST | WEST;

我将这些门存储在一个简单的数组中：

Door doors[] = new Door[4];

我的问题是：我需要一个可以将标识符映射到数组中正确索引的函数。我并不总是需要 4 扇门。

起初我所做的似乎是最简单的：门数组总是有 4 个元素，而我不会使用的索引将保持为空。

public Door getDoor(int doorID){
    switch(doorID){
        case NORTH:{
            return doors[0];
        }
        case SOUTH:{
            return doors[1];
        }
        case EAST:{
            return doors[2];
        }
        case WEST:{
            return doors[3];
        }
    }
    return null;
}

为了安全起见，我需要确定我请求的门是否真的存在于房间中。

private boolean doorExists(int doorID){
    return (doorID & doorStock) != 0
}

因此，查询函数如下所示：

public Door getDoor(int doorID){
    switch(doorID){
        case NORTH:{
            if(doorExists(NORTH))return doors[0];
            else return null;
        }
        case SOUTH:{
            if(doorExists(NORTH))return doors[1];
            else return null;
        }
        case EAST:{
            if(doorExists(NORTH))return doors[2];
            else return null;
        }
        case WEST:{
            if(doorExists(NORTH))return doors[3];
            else return null;
        }
    }
    return null;
}

哪个有效。但！这样，数组可能会因未使用的元素而浪费空间。另外，该类Door可能是任何大小，从而增加了内存浪费。

更不用说我可能需要更多的门“插槽”（例如，如果我尝试在 3D 中实现它），所以我决定尝试根据门的标识符制作门数组的大小：

Door doors = new Door[Integer.bitCount(doorStock)];

这IndexOutOfBounds很快就给出了一个错误。我并不感到惊讶，因为门数组可以是从 0 到 4 的任意大小，所以我需要一种新的散列方法。

我想出的是两个哈希表，一个用于数组索引：

private final int[][] doorhash = {
    /* NORTH  SOUTH   EAST    WEST doorStock*/
    { -1,     -1,     -1,     -1} /*0000*/,
    { -1,     -1,     -1,      0} /*0001*/,
    { -1,     -1,      0,     -1} /*0010*/,
    { -1,     -1,      0,      1} /*0011*/,
    { -1,      0,     -1,     -1} /*0100*/,
    { -1,      0,     -1,      1} /*0101*/,
    { -1,      0,      1,     -1} /*0110*/,
    { -1,      0,      1,      2} /*0111*/,
    {  0,     -1,     -1,     -1} /*1000*/,
    {  0,     -1,     -1,      1} /*1001*/,
    {  0,     -1,      1,     -1} /*1010*/,
    {  0,     -1,      1,      2} /*1011*/,
    {  0,      1,     -1,     -1} /*1100*/,
    {  0,      1,     -1,      2} /*1101*/,
    {  0,      1,      2,     -1} /*1110*/,
    {  0,      1,      2,      3} /*1111*/
};

还有一个，它有助于映射上一个表：

private final int[] directionHash = {
    -1, /*0000*/
     3, /*0001 - WEST*/
     2, /*0010 - EAST*/
    -1, /*0011*/
     1, /*0100 - SOUTH*/
    -1, /*0101*/
    -1, /*0110*/
    -1, /*0111*/
     0, /*1000 - NORTH*/
};

所以我当前的映射函数如下所示：

public Door getDoor(int doorID){
    switch(doorID){
        case NORTH:{
            if(doorExists(NORTH))return doors[doorhash[doorStock][directionHash[NORTH]]];
            else return null;
        }
        case SOUTH:{
            if(doorExists(NORTH))return doors[doorhash[doorStock][directionHash[SOUTH]]];
            else return null;
        }
        case EAST:{
            if(doorExists(NORTH))return doors[doorhash[doorStock][directionHash[EAST]]];
            else return null;
        }
        case WEST:{
            if(doorExists(NORTH))return doors[doorhash[doorStock][directionHash[WEST]]];
            else return null;
        }
    }
    return null;
}

这似乎也可以正常工作，但我觉得有一个更简单的解决方案可以解决这个问题，或者使用较少浪费的哈希表。我觉得这不像它应该的那样渐近灵活，或者我把事情复杂化了。什么是更好的方法？

感谢您的时间！

4

7 回答 7

25

枚举是你的朋友：

// Each possible direction - with Up/Down added to show extendability.
public enum Dir {
  North,
  South,
  East,
  West,
  Up,
  Down;
}

class Room {
  // The doors.
  EnumSet doors = EnumSet.noneOf(Dir.class);

  // Many other possible constructors.
  public Room ( Dir ... doors) {
    this.doors.addAll(Arrays.asList(doors));
  }

  public boolean doorExists (Dir dir) {
    return doors.contains(dir);
  }
}

让枚举为您完成繁重的工作在这里是很自然的。EnumSet他们还提供了一个非常有效的现成的。

于 2013-10-08T09:54:06.847 回答
6

您的解决方案可能是最节省空间的，但可能是时间效率低下的，而且绝对是最不清晰的写法。

一个简单的面向对象的方法是有一个Room带有 4 的类booleans，可以在一个数组中，也可以根据你的需要独立；

public class Room {

    //Consider an ENUM for bonus points
    public static int NORTH=0;
    public static int SOUTH=1;
    public static int EAST=2;
    public static int WEST=3;   

    private boolean[] hasDoor=new boolean[4];

    public Room(boolean northDoor,boolean southDoor,boolean eastDoor,boolean westDoor) {
        setHasDoor(northDoor,NORTH);
        setHasDoor(southDoor,SOUTH);
        setHasDoor(eastDoor,EAST);
        setHasDoor(westDoor,WEST);
    }

    public final  void setHasDoor(boolean directionhasDoor, int direction){
        hasDoor[direction]=directionhasDoor;
    }
    public final boolean  getHasDoor(int direction){
        return hasDoor[direction];
    }


}

任何不阅读文档或方法的人都清楚它的作用，这始终是您首先应该瞄准的目标。

然后可以按如下方式使用

public static void main(String[] args){
    ArrayList<Room> rooms=new ArrayList<Room>();

    rooms.add(new Room(true,false,true,false));
    rooms.add(new Room(true,true,true,false));

    System.out.println("Room 0 has door on north side:"+rooms.get(0).getHasDoor(NORTH));

}

或者在遵循您的平面图的二维阵列中

public static void main(String[] args){
    Room[][] rooms=new  Room[10][10]; 

    rooms[0][0]=new Room(true,false,true,false);
    rooms[0][1]=new Room(true,false,true,false);
    //........
    //........
    //other rooms
    //........
    //........

    System.out.println("Room 0,0 has door on north side:"+rooms[0][0].getHasDoor(NORTH));

}

最重要的问题是你是否关心以清晰的代码和可能的执行速度为代价节省几千字节？在内存不足的情况下，您可能会这样做，否则您不会。

于 2013-10-08T09:38:46.813 回答
1

你肯定是过度设计了这个。例如，它可以通过 chars 和使用char[4]数组来存储（最多）4 个不同的字符n、s和.we

您可以String用于收集有关门的信息，每个门char都是一扇门（然后您可能会有类似的"nnse"意思，即北墙上有 2 扇门，1 扇南门和 1 扇东门）。

您也可以使用ArrayListof Characters 并且可以根据需要将其转换为数组。取决于你想用这个做什么，但是有很多方法可以实现你想要做的事情。

记住这一点

过早的优化是万恶之源

于 2013-10-08T09:26:51.460 回答
1

好的，根据评论，我决定不再使事情复杂化。我将使用第一个解决方案，其中doors数组将有 4 个元素，映射函数为：

public Door getDoor(int doorID){
    switch(doorID){
        case NORTH:{
            if(doorExists(NORTH))return doors[0];
            else return null;
        }
        case SOUTH:{
            if(doorExists(NORTH))return doors[1];
            else return null;
        }
        case EAST:{
            if(doorExists(NORTH))return doors[2];
            else return null;
        }
        case WEST:{
            if(doorExists(NORTH))return doors[3];
            else return null;
        }
    }
    return null;
}

我只是认为这是一个很好的理论问题，仅此而已。感谢您的回复！

于 2013-10-08T09:42:28.500 回答
1

好的，我 100% 同意 Enums 是这里的方法。我唯一建议的是使用二进制 id 系统，特别是因为这是应用于游戏的逻辑，并且您可能需要将定义房间的信息存储在某处。使用这种系统，您可以存储房间可用门的二进制表示。当您处理最多只能拥有一个的项目时，该系统运行良好。在您的情况下，一个房间的每个方向只能有一扇门。如果将房间中每扇门的所有二进制值相加，则可以存储该值，然后将该值转换回正确的枚举。

例子：

public enum Direction {

    NONE (0, 0),
    NORTH (1, 1),
    SOUTH (2, 2),
    EAST (3, 4),
    WEST (4, 8),
    NORTHEAST (5, 16),
    NORTHWEST (6, 32),
    SOUTHEAST (7, 64),
    SOUTHWEST (8, 128),
    UP (9, 256),
    DOWN (10, 512);

    private Integer id;
    private Integer binaryId;

    private Direction(Integer id, Integer binaryId) {
        this.id = id;
        this.binaryId = binaryId;
    }

    public Integer getId() {
        return id;
    }

    public Integer getBinaryId() {
        return binaryId;
    }

    public static List<Direction> getDirectionsByBinaryIdTotal(Integer binaryIdTotal) {
        List<Direction> directions = new ArrayList<Direction>();

        if (binaryIdTotal >= 512) {
            directions.add(Direction.DOWN);
            binaryIdTotal -= 512;
        }
        if (binaryIdTotal >= 256) {
            directions.add(Direction.UP);
            binaryIdTotal -= 256;
        }
        if (binaryIdTotal >= 128) {
            directions.add(Direction.SOUTHWEST);
            binaryIdTotal -= 128;
        }
        if (binaryIdTotal >= 64) {
            directions.add(Direction.SOUTHEAST);
            binaryIdTotal -= 64;
        }
        if (binaryIdTotal >= 32) {
            directions.add(Direction.NORTHWEST);
            binaryIdTotal -= 32;
        }
        if (binaryIdTotal >= 16) {
            directions.add(Direction.NORTHEAST);
            binaryIdTotal -= 16;
        }
        if (binaryIdTotal >= 8) {
            directions.add(Direction.WEST);
            binaryIdTotal -= 8;
        }
        if (binaryIdTotal >= 4) {
            directions.add(Direction.EAST);
            binaryIdTotal -= 4;
        }
        if (binaryIdTotal >= 2) {
            directions.add(Direction.SOUTH);
            binaryIdTotal -= 2;
        }
        if (binaryIdTotal >= 1) {
            directions.add(Direction.NORTH);
            binaryIdTotal -= 1;
        }

        return directions;
    }

}
于 2013-10-10T15:37:15.950 回答
0

我什至会将门建模为枚举，以便将来使用其他类型的门。例如：

public enum Door { TOP, BOTTOM, LEFT, RIGHT };

public class Room {
    private Set<Door> doors = new HashSet<Door>;
    public Room(Door... doors) {
        //Store doors.
        this.doors = doors;
    }

    public boolean hasDoor(Door door) {
        return this.doors.contains(door);
    }
}
于 2013-10-08T09:46:45.513 回答
0

你可以这样转换：

public Door getDoor(int doorID){
switch(doorID){
    case NORTH:{
        return doors[0];
    }
    case SOUTH:{
        return doors[1];
    }
    case EAST:{
        return doors[2];
    }
    case WEST:{
        return doors[3];
    }
}
return null;
}

对此：

public Door getDoor(int doorID){
    int index = 0;
    int id = doorID;
    while(id > 1){
        if(id & 1 == 1)
            return null;
        id = id >>> 1;
        index++;
    }
return doors[index];
}
于 2013-10-08T09:42:44.583 回答