Javaゲーム:A *アルゴリズム(文字の前のセルのみを検索)

1
dre 2021-01-08 11:17.

ゲームタイプ:ベースになっているグリッドタイルマップ

許可される方向:左、前進、右(方向を逆にするには、2つの左または2つの右を使用する必要があります)-左と右の両方が斜めに移動しますが、元の顔に応じて船の顔を変更します)

スロット:船のサイズに応じて、ユーザーが入る特定の船のスロットの数があり、船が1ターンあたりその数のスポットを移動できるようにします(つまり、3スロット== 1ターンあたり3移動)

例:

開始位置:2,2

スタートフェイス:北

配置された移動:左

最終結果:位置:1,3; 顔:西


問題:アルゴリズムはパスファインディングに8つのタイルすべてを使用します。ただし、正面にあるタイルのみを探す必要があります(船の表面によって異なります)

ノードクラス:

public class AStarNode {

    public Position position;
    public VesselFace face;
    public AStarNode parent;
    public double fCost, gCost, hCost;
    
    public AStarNode(Position position, VesselFace face, AStarNode parent, double gCost, double hCost) {
        this.position = position;
        this.face = face;
        this.parent = parent;
        this.gCost = gCost;
        this.hCost = hCost;
        this.fCost = this.gCost + this.hCost;
    }
  
}  

パスファインディングの計算:

    private Comparator<AStarNode> nodeSorter = new Comparator<AStarNode>() {

        @Override
        public int compare(AStarNode n0, AStarNode n1) {
            if(n1.fCost < n0.fCost) return 1;
            if(n1.fCost > n0.fCost) return -1;
            return 0;
        }
        
    };

    public List<AStarNode> findPath(Position start, Position goal){
        List<AStarNode> openList = new ArrayList<AStarNode>();
        List<AStarNode> closedList = new ArrayList<AStarNode>();
        AStarNode current = new AStarNode(start, null, 0, start.distance(goal));
        openList.add(current);
        while(openList.size() > 0) {
            Collections.sort(openList, nodeSorter);
            current = openList.get(0);
            if(current.position.equals(goal)) {
                List<AStarNode> path = new ArrayList<AStarNode>();
                while(current.parent != null) {
                    path.add(current);
                    current = current.parent;
                }
                openList.clear();
                closedList.clear();
                return path;
            }
            openList.remove(current);
            closedList.add(current);
            for(int i = 0; i < 9; i++) {
                if (i == 4)continue;
                int x = current.position.getX();
                int y = current.position.getY();
                int xi = (i % 3) - 1;
                int yi = (i / 3) - 1;
                int at = context.getMap().getTile(x + xi, y + yi);
                if(at == 1 || at == 2) continue; // ignore rocks
                Position a = new Position(x + xi, y + yi);
                double gCost = current.gCost + current.position.distance(a);
                double hCost = a.distance(goal);
                AStarNode node = new AStarNode(a, current, gCost, hCost);
                if(positionInList(closedList, a) && gCost >= node.gCost) continue;
                if(!positionInList(openList, a) || gCost < node.gCost) openList.add(node);
            }
        }
        closedList.clear();
        return null;
    }
    
    private boolean positionInList(List<AStarNode> list, Position position) {
        for(AStarNode n : list) {
            if(n.position.equals(position)) return true;
        }
        return false;
    }

実装:

@Override
    public void calculateRoute() {
        Position destination = new Position(3,3); // replace with cluster
        if(this.equals(destination)) {
            return;
        }based 
        path = context.getPlayerManager().findPath(this, destination);
        VesselFace face = getFace();
        if(path != null) {
            if(path.size() > 0) {
                int numberOfMoves = getVessel().has3Moves() ? 3 : 4;
                Position currentPosition = this.copy();
                for(int slot = 0; slot <= numberOfMoves; slot++) { //moves to enter
                    int positionIndex = (path.size() - 1) - (slot); //subtract slot to allow multiple moves
                    if(positionIndex < 0 || path.size() < slot) { // make sure it doesn't count too far
                        return;
                    }
                    Position pos = path.get(positionIndex).position;
                    Position left = MoveType.LEFT.getFinalPosition(currentPosition, face);
                    Position right = MoveType.RIGHT.getFinalPosition(currentPosition, face);
                    Position forward = MoveType.FORWARD.getFinalPosition(currentPosition, face);
                    if(left.equals(pos)) {
                        currentPosition.add(left.getX() - getX(), left.getY() - getY());
                        getMoves().setMove(slot, MoveType.LEFT);
                        switch(face) {
                            case NORTH:
                                face = VesselFace.WEST;
                                break;
                            case SOUTH:
                                face = VesselFace.EAST;
                                break;
                            case WEST:
                                face = VesselFace.SOUTH;
                                break;
                            case EAST:
                                face = VesselFace.NORTH;
                                break;
                        }
                    }else if(right.equals(pos)) {
                        currentPosition.add(right.getX() - getX(), right.getY() - getY());
                        getMoves().setMove(slot, MoveType.RIGHT);
                        switch(face) {
                            case NORTH:
                                face = VesselFace.EAST;
                                break;
                            case SOUTH:
                                face = VesselFace.WEST;
                                break;
                            case WEST:
                                face = VesselFace.NORTH;
                                break;
                            case EAST:
                                face = VesselFace.SOUTH;
                                break;
                        }
                    }else if(forward.equals(pos)){
                        currentPosition.add(forward.getX() - getX(), forward.getY() - getY());
                        getMoves().setMove(slot, MoveType.FORWARD);
                        switch(face) {
                            case NORTH:
                                face = VesselFace.NORTH;
                                break;
                            case SOUTH:
                                face = VesselFace.SOUTH;
                                break;
                            case WEST:
                                face = VesselFace.WEST;
                                break;
                            case EAST:
                                face = VesselFace.EAST;
                                break;
                        }
                    }
                }
            }
        }
    }

私はswitchステートメントとcurrentPosition.add()メソッドを使用して、特定のターンに3つの移動を配置したときに実行します。それはどこに行き着くべきかを知っています。おそらくベストプラクティスではありません。

特定のスロットに移動を追加するステートメント

getMoves().setMove(slot, MoveType.FORWARD);

船の表面に基づいて毎ターンチェックする必要があるタイル:

1 answers

0
amitp 2021-01-09 09:47.

これは部分的な試みに過ぎず、私が行ったコメントの詳細を示しています。

A *は、船の「状態」を含むノードのグラフを検索します。ほとんどのチュートリアル(私のものを含む、申し訳ありません)では、状態は位置のみです。しかし、あなたの場合、状態は位置と向きの両方だと思います。その前の3つの位置を計算するには、向きを知る必要があります。そして、移動後、位置と新しい向きの両方が得られます。

Node現在、ポジションがあります。positionとの両方を持つように変更しfacingます。for(int i = 0; i < 9; i++)ネイバーを見つけるためのループの大まかなバージョンを次に示します。9つのネイバーを通過する代わりに、4つの方向のそれぞれに正確に3つのネイバーがあります。(はい、8ではなく12があります!前に向いていた方向によって異なります)

    int x = current.position.getX();
    int y = current.position.getY();
    List<Node> neighbors = new ArrayList<Node>();
    switch (current.facing) {
        case NORTH:
            neighbors.add(new Node(new Position(x-1, y-1), WEST, …));
            neighbors.add(new Node(new Position(x, y-1), NORTH, …));
            neighbors.add(new Node(new Position(x+1, y-1), EAST, …));
            break;
        case EAST:
            neighbors.add(new Node(new Position(x+1, y-1), NORTH, …));
            neighbors.add(new Node(new Position(x+1, y), EAST, …));
            neighbors.add(new Node(new Position(x+1, y+1), SOUTH, …));
            break;
        case SOUTH:
            neighbors.add(new Node(new Position(x-1, y+1), WEST, …));
            neighbors.add(new Node(new Position(x, y+1), SOUTH, …));
            neighbors.add(new Node(new Position(x+1, y+1), EAST, …));
            break;
        case WEST:
            neighbors.add(new Node(new Position(x-1, y-1), NORTH, …));
            neighbors.add(new Node(new Position(x-1, y), WEST, …));
            neighbors.add(new Node(new Position(x-1, y+1), SOUTH, …));
            break;
    }

    /* for each of the nodes in the neighbors list, use the same
       logic you already have:
       1. check if it's a rock, and ignore if it is
       2. calculate g cost, store it in the node
       3. calculate h cost, store it in the node
       4. consider adding the node to openList
    */

Related questions

MORE COOL STUFF

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは、夫に会ったとき、典型的な交際のアドバイスに逆らいました。

マイケルシーンが非営利の俳優である理由

マイケルシーンが非営利の俳優である理由

マイケルシーンは非営利の俳優ですが、それは正確にはどういう意味ですか?

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

特徴的なスターのコリン・エッグレスフィールドは、RomaDrama Liveでのスリル満点のファンとの出会いについて料理しました!加えて、大会での彼のINSPIREプログラム。

「たどりつけば」をオンラインでストリーミングできない理由

「たどりつけば」をオンラインでストリーミングできない理由

ノーザンエクスポージャーが90年代の最も人気のある番組の1つになった理由を確認するには、Blu-rayまたはDVDプレーヤーをほこりで払う必要があります。

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖は、世界で2番目に大きいボイリング湖です。そこにたどり着くまでのトレッキングは大変で長いですが、努力する価値は十分にあります。

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

サロンからのヘアトリミングや個人的な寄付は、油流出を吸収して環境を保護するのに役立つマットとして再利用できます。

科学者は髪が灰色になる理由の別の可能な説明を見つけます

科学者は髪が灰色になる理由の別の可能な説明を見つけます

このネズミのグリズリした毛皮は、いつか人々が白斑と呼ばれるまれな状態を発症する理由を説明するのに役立つかもしれません。科学者たちは、白斑と呼ばれるまれな汚名を着せられた状態である無着色の皮膚の斑点に悩まされる人もいれば、髪が灰色になる理由を説明できる新たに発見されたメカニズムに遭遇したと考えています。

新しい若いテロリストコレクションの内部のこの外観で、神秘的で残忍な陰謀に飛び込む

新しい若いテロリストコレクションの内部のこの外観で、神秘的で残忍な陰謀に飛び込む

若いテロリストの野生のアンチヒーロー、セラに会いましょう。ほぼ3年前、Black Mask Studiosは、残忍で政治的な色合いのスリラーであるYoungTerroristsと波を起こしました。

Huluが周りを見回し、The Handmaid'sTaleを第3シーズンに更新します

Huluが周りを見回し、The Handmaid'sTaleを第3シーズンに更新します

ハンドメイドの物語のエリザベスモス昨夜、アイオワ上院は、胎児の心拍が検出された後、ほとんどの妊娠中絶を禁止する、いわゆる「心拍」法案を早急に追跡しました。妊娠。また、HuluはThe Handmaid'sTaleを第3シーズンに更新することを決定しました。

ラストコール:どのように風邪と戦うのですか?

ラストコール:どのように風邪と戦うのですか?

これは実際に機能しますか?病気になってから久しぶりですが(ジンクス!)、今朝目が覚めたとき、副鼻腔の奥にひどい痛みを感じ、病気になりそうです。風邪が嫌いです。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Rothschild's luggage got lost, but luckily she has an incredible closet to shop: Sister Paris Hilton's!

ケイト・ミドルトンはロンドンの水辺で一日を過ごし、さらにジェニファー・ロペス、ジュリアン・ハフなど

ケイト・ミドルトンはロンドンの水辺で一日を過ごし、さらにジェニファー・ロペス、ジュリアン・ハフなど

ケイト・ミドルトンはロンドンの水辺で 1 日を過ごし、ジェニファー・ロペス、ジュリアン・ハフなども。ハリウッドからニューヨークまで、そしてその間のあらゆる場所で、お気に入りのスターの活躍をご覧ください!

ウィスコンシン川でのナイフ攻撃で 17 歳の少年が刺されて死亡、他の 4 人が負傷したままになっている

ウィスコンシン川でのナイフ攻撃で 17 歳の少年が刺されて死亡、他の 4 人が負傷したままになっている

捜査官は、グループと容疑者が攻撃の前にお互いを知っていたかどうかを調べています

実際に変換するコンテンツ戦略を作成することを想像してみてください。それが可能だ。

実際に変換するコンテンツ戦略を作成することを想像してみてください。それが可能だ。

2021 年には、サービスを提供する顧客と顧客に伝えるストーリーについて知っていることをすべて再考することをお勧めします。あとずさりする。

マンモスロスは私の心を愛に開いた

マンモスロスは私の心を愛に開いた

フェリックス ザ キャットの 9 歳の誕生日の日に、大人になってからの最大の損失の 1 つである 2013 年のソフィーを思い出します。私はこのエッセイを書き、2013 年にこのプラットフォームで簡単に共有しました。

あなたがインターネットがあなたに望んでいる人になれないとき

あなたがインターネットがあなたに望んでいる人になれないとき

私は「列車事故」という言葉が嫌いです。人々は自分自身の道徳的羅針盤に安らぎを覚え、そうすることで自分自身が判断を下していることに気づきます。

DFINITY ブロックチェーンの分散型クラウド ビジョン

編集者注: アーカイブ目的で保存されている DFINITY ブログの古い資料を表示しています。

DFINITY ブロックチェーンの分散型クラウド ビジョン

この投稿では、DFINITY チームの分散型クラウドのビジョンと、それが従来のブロックチェーンやアマゾン ウェブ サービスなどの既存のクラウド プロバイダーとどのように関連しているかを探ります。大規模なネットワークによって適用される DFINITY テクノロジのデモンストレーションが 2017 年の秋に行われ、その後、非営利財団を支援するための主要な資金調達が行われ、「オープン クラウド」ネットワークは 2018 年の初夏に開始される予定です。 .

Language