Is Hashing a suitable solution? Am I over-complicating it?

Question

I write a 2D platformer game where I need rooms with (maximum 4) doors. I write it in Java, but the language is irrelevant.

Each room can have 4 doors, on the top, bottom and sides. I call them NORTH, SOUTH, EAST and WEST. When I'm building a room, I only give it an integer, where each bit in the integer is representing a door.

For example if I want a room with 3 doors (one on the North, one on the East, and on on the west) i give the room the number: 11(1011 in binary).

For this reason each door has an integer, identifying it.

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

If I generate a room, I give it the combination of these identifiers.

For example: the previously mentioned room would get the identifier

doorStock = NORTH | EAST | WEST;

I store these doors in a simple array:

Door doors[] = new Door[4];

My problem is: I need a function which can map the identifiers to the correct index in the array. I don't always need 4 doors.

What I did at first seems the simplest: the doors array would always have 4 elements, and the indices I would not use would simply remain nulls.

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

In order to be safe I needed to to determine if the door I'm requesting actually exists in the room.

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

So with this, the query function looked like this:

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

Which was working. BUT! This way the array could waste space with the unused elements. Plus the class Door could potentially be any size, increasing the memory waste.

Not to mention I could need more "slots" for doors( for example, If I try to implement this in 3D), so I decided to try and make the doors array's size depending on the identifier for the doors:

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

Which gave an IndexOutOfBounds error real quick. I wasn't surprised, because the doors array could be any size from 0 to 4, so I needed a new hashing method.

What I came up with are two hash tables, one for the array indices:

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

and one, which helps helps in the mapping of the previous table:

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

so my current mapping function looks like this:

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

Which also seems to work fine, but I feel there's a simpler solution to this problem, or one with less wasteful hash tables. I feel this isn't as asymptotically flexible as it should be, or I am over-complicating things. What would be a better method?

Thank you for your time!

Lemaster

A room without a Door is not a room so 0000 is an illegal value. – Mangum

"This way the array could waste space with the unused elements" - unless you've got millions of rooms it's not going to be worth worrying about. You array will store references to Door objects, not the objects themselves (i.e. pointer in C++ terms) so the size of the Door class is irrelevant for a no-door null. – Plumate

Why are you doing this this way, it has a feel of madness about it. Whats so wrong with 4 booleans? – Maidservant

In addition to Rups comment: you're attempting to optimise against the possibility of wasting space in the Door class, and it's led to this question. That may suggest that you're over-thinking this - premature optimisation, root of all evil, yadda yadda. – Neurovascular

@PeterRader: Not if you use teleportation :-) – Epigene

Thanks, this cleared a bit of worry in me, but the problem I think is still valid. I'm just curious if there's an optimal solution to this. – Amentia

I think a sensible solution for this would be: Room class, contains 4 booleans for doors as members. All stored in some sort of extendable collection (e.g. Room classes stored in an ArrayList<Room>) if you don't know in advance how many rooms you will have – Maidservant

So hashing may be a bit too overcomplicated huh? Coding late has it's wonders. – Amentia

Answer 1

Enums are your friend:

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

Letting enums do the heavy lifting for you is a natural here. They also provide a ready-made EnumSet that is extremely efficient.

Buxton

Far better than the accepted answer, because it's extensible. – Fey

The bottom line is, the implementation should be hidden behind a suitable interface, unless we are doing something ridiculously over-optimized, perhaps some real-time mobile game with 5-dimensional action shooting for millions of users... – Solanum

Answer 2

Your solution is probably the most space efficient, however is likely to be time inefficient and is definitely the least clear to write.

A simple object orientated approach would be to have a Room Class, with 4 booleans, either in an array or independently as you desire;

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


}

It is clear to anyone without reading the docs, or the methods what this does and this is always what you should aim for in the first instance.

This can then be used as follows

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

}

Or in a 2D array that follows your floor plan

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

}

The all important question is do you care about saving a few kilobyte at the expense of clear code and probably execusion speed? In a memory starved situation you probably do, otherwise you don't.

Maidservant

In this situation readability has priority over a few kilobytes. Thank you! – Amentia

Passing boolean arguments is far from readable, though. Might be better to pass an array of enum values like new Room({ NORTH, SOUTH }); or something. – Lexielexigraphy

@Lexielexigraphy Certainly true, that would be better. However I've often found enums to be an advanced topic and don't want to confused the 90% better by trying to get the last 10%. I included "Consider an ENUM for bonus points" in the code as a hint but thats as far as I really want to go – Maidservant

@Lexielexigraphy That said OldCurmudgeon's answer is a nice example of an enum based approach and I'm glad its here as a competing answer – Maidservant

Answer 3

You are definitely overengineering this. It could be resolved for example by chars and using a char[4] array to store (at most) 4 different characters n, s, w and e.

You can use String for gathering information about the doors and each char would be one door (then you could have something like "nnse" meaning that there are 2 doors on the north wall, 1 south door and one east door).

You could also use an ArrayList of Characters and could transform it to array if you want. Depends on what you want to do with this, but there are many ways to achieve what you are trying to do.

And remember that

Premature optimization is the root of all evil

Denude

This still feels like an over engineer, a nice object orientated solution would be the easiest to work with – Maidservant

Also, a premature optimization with juggling the char types... In such a situation, I'd use enums and EnumSets... – Formicary

@RichardTingle Not really if he wants a quick and simple solution. I simply pointed first solution which came to my mind. It still is not the greatest and most optimized solution, but: See the quote. And I have already said that there are many ways to achieve this. This is really simple thing and I personally think that instead of thinking for 2 hours about how would be the best way to do this, just do this easily and then check if it would cause any performance troubles. And I doubt it, if you use it (one of the solutions) normally (properly). – Denude

@ppeterka66 Yeah, Enums was my first thought also, but the gentelman here obviously wants to use as less memory as he can ;-) – Denude

Answer 4

Okay, based on the comments I decided not to complicate things further. I will use the first solution in which the doors array will have 4 elements, and the mapping function is:

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

I just thought it was a good theoretical question, is all. Thank you for the responses!

Lemaster

The door exists check seems redundant; if you simply return the corresponding element in the array you'll get null if there was no door! – Dragelin

Just let NORTH==0, EAST==1, SOUTH==2, WEST==3. (In this order, so you can add/subtract 1 modulo 4 to turn). Then you can simply return[doors[direction]]. In other places, where you need a power of two, just use bitmask & (1 << direction), or something like that. – Solanum

but that would cost some readability issues in my current constructor. Currently my constructor is like this: door = new Door(Door.NORTH | Door.SOUTH | Door.East), where Door.SOUTH(..etc..) are the constants for the directions of the doors I want in that particular room. – Amentia

Answer 5

Ok, I agree 100% that Enums is the way to go here. The only thing I would suggest, especially since this is logic being applied to a game and you likely will need to store the information that defines a room somewhere, is to use a system of binary ids. Using this sort of system, you can store a binary representation of what doors are available to a room. This system works well when you are dealing with items where you can only have a maximum of one. In your case, a room can only have 1 door for every direction. If you add up all the binary values for each door in a room, you can store that value and later turn that value back into the proper Enums.

Example:

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

}

Dialectics

Answer 6

You can convert this:

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

to this:

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

Accumulator

If we are talking about optimization, I'd say that while should be avoided. After all, you can pre-compute an array of discrete logarithms to write doors[reverse[index]]. – Solanum

Answer 7

I would even model the doors as an enumeration, allowing for other types of doors in the future. For example:

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

Dagny