Является ли Хешинг подходящим решением? Я слишком усложняю это?

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

Который также работает нормально, но я чувствую, что есть простое er решение этой проблемы, или один с менее расточительными хеш-таблицами. Я чувствую, что это не так асимптотически гибко, как должно быть, или я слишком усложняю вещи. Что было бы лучшим методом?

Благодарим вас за внимание!

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

Позволить перечислений делать тяжелую для вас является естественным здесь. Они также обеспечивают готовый EnumSet, который является чрезвычайно эффективным.

Answer 2

Вы, безусловно, переоцениваете это. Он может быть разрешен, например, символами и с использованием массива char[4] для хранения (не более) 4 разных символов n, s, w и e.

Вы можете использовать String для сбора информации о дверях и каждый char бы одна двери (тогда вы могли бы иметь что-то вроде "nnse" означает, что есть 2 двери на северной стене, 1 юг двери и один восток двери).

Вы также можете использовать символы символов ArrayList и можете преобразовать их в массив, если хотите. Зависит от того, что вы хотите сделать с этим, но есть много способов добиться того, что вы пытаетесь сделать.

И помните, что

Преждевременная оптимизация является корнем всего зла

Answer 3

Ваше решение, вероятно, наиболее пространство эффективным, однако, вероятно, будет время неэффективна и, безусловно, не менее ясно написать.

Простой объектно-ориентированный подход состоит в том, чтобы иметь класс Room с либо в массиве, либо независимо по желанию;

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

} 

этажа Абсолютно важный вопрос: вы заботитесь о сохранении несколько килобайта на расход чистого кода и, вероятно, скорость исполнения? Вероятно, у вас голодная ситуация с памятью, иначе вы этого не сделаете.

Answer 4

Хорошо, основываясь на комментариях, я решил больше не усложнять ситуацию.Я буду использовать первое решение, в котором 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; 
} 

Я просто подумал, что это был хороший теоретический вопрос, это все. Спасибо за ответы!

Answer 5

Вы можете преобразовать это:

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

Answer 6

Я бы даже моделировать двери как перечисление, что позволяет для других типов дверей в будущем. Например:

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

Answer 7

Хорошо, я согласен на 100%, что Enums - это путь сюда. Единственное, что я хотел бы предложить, тем более, что это логика, применяемая к игре, и вам, вероятно, понадобится хранить информацию, которая определяет комнату где-то, заключается в использовании системы двоичных идентификаторов. Используя такую ​​систему, вы можете сохранить двоичное представление о том, какие двери доступны для комнаты. Эта система работает хорошо, когда вы имеете дело с пунктами, где вы можете иметь максимум один. В вашем случае в комнате может быть только 1 дверь для каждого направления. Если вы суммируете все двоичные значения для каждой двери в комнате, вы можете сохранить это значение, а затем вернуть это значение в соответствующие Enums.

Пример:

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

}