9

(最大 4 つの) ドアのある部屋が必要な 2D プラットフォーマー ゲームを作成しています。Javaで書いていますが、言語は問いません。

各部屋には、上、下、側面の 4 つのドアがあります。私はそれらNORTHを 、SOUTH、EASTおよび と呼びますWEST。部屋を作るときは、整数のみを与えます。整数の各ビットはドアを表します。

たとえば、ドアが 3 つある部屋 (北に 1 つ、東に 1 つ、西に 1 つ) が必要な場合、部屋に 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 つの要素があり、使用しないインデックスは単純に null のままです。

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 までの任意のサイズにすることができたので、私は驚きませんでした。そのため、新しいハッシュ メソッドが必要でした。

私が思いついたのは、配列インデックス用の 2 つのハッシュ テーブルです。

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

1 つ目は、前のテーブルのマッピングに役立ちます。

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

あなたのソリューションはおそらく最もスペース効率が良いですが、時間効率が悪い可能性が高く、間違いなく最も書きにくいものです。

単純なオブジェクト指向のアプローチは、配列内または必要に応じて独立して、Room4 を使用して Class を持つことです。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));

}

最も重要な質問は、明確なコードとおそらく実行速度を犠牲にして、数キロバイトを節約することに関心があるかということです。メモリが不足している状況では、おそらく実行しますが、そうでない場合は実行しません。

于 2013-10-08T09:38:46.813 に答える
1

さて、コメントに基づいて、これ以上複雑にしないことにしました。配列に 4 つの要素が含まれる最初のソリューションを使用しますdoors。マッピング関数は次のとおりです。

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

わかりました、Enums がここに行く方法であることに 100% 同意します。特にこれはゲームに適用されるロジックであり、部屋を定義する情報をどこかに保存する必要がある可能性が高いため、私が提案する唯一のことは、バイナリ ID のシステムを使用することです。この種のシステムを使用すると、部屋で使用できるドアのバイナリ表現を保存できます。このシステムは、最大 1 つしか持てないアイテムを扱う場合にうまく機能します。あなたの場合、部屋にはすべての方向に1つのドアしかありません。部屋の各ドアのすべてのバイナリ値を合計すると、その値を保存し、後でその値を適切な Enum に戻すことができます。

例：

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 に答える
1

あなたは間違いなくこれをオーバーエンジニアリングしています。たとえば、chars と配列を使用して(最大で) 4 つの異なる文字、、およびchar[4]を格納することで解決できます。nswe

Stringドアに関する情報を収集するために使用でき、それぞれが 1 つのドアになります (北の壁に 2 つのドア、南のドアと東のドアが 1 つずつあるという意味charのようなものを持つことができます)。"nnse"

ArrayList文字の を使用して、必要に応じて配列に変換することもできます。これで何をしたいかによって異なりますが、やろうとしていることを達成する方法はたくさんあります。

そして、それを覚えておいてください

時期尚早の最適化は諸悪の根源

于 2013-10-08T09:26:51.460 に答える
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 に答える