Hashing是一个合适的解决方案吗？我过度复杂了吗？

Question

我写了一个2D平台游戏,我需要有(最多4个)门的房间.我用Java编写它,但语言无关紧要.

每个房间可以有4个门,在顶部,底部和侧面.我打电话给他们NORTH,SOUTH,EAST和WEST.当我正在建造一个房间时,我只给它一个整数,整数中的每个位代表一个门.

例如,如果我想要一个有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;
}

这也似乎工作正常,但我觉得有一个更简单的解决方案,或者一个浪费较少的哈希表.我觉得这不应该像它应该的那样渐渐灵活,或者我过于复杂.什么是更好的方法？

感谢您的时间!

Answer 1

枚举是你的朋友:

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

让enums为你做繁重的工作是很自然的.它们还提供EnumSet非常高效的现成品.

Answer 2

您的解决方案可能是最节省空间的,但可能是时间效率低下,绝对是最不清楚的.

一个简单的面向对象的方法是有一个RoomClass,有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));

}

或者在遵循平面图的2D阵列中

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

}

所有重要的问题是你是否关心以牺牲清晰代码和可能的速度为代价来节省几千字节？在你可能做的记忆匮乏的情况下,否则你不会.