幅優先探索:パスが見つかりません、2D配列の境界への最短パス

2
SwiftHobby 2020-10-16 05:48.

「Circlethedot」ゲームをプログラミングしてみます。基本的なゲームのアイデアは、青い点を逃げる前に囲む必要があるというものです。障害物(オレンジ色のドット)が配置されるたびに、青いドット(「プレーヤー」)が1ステップ移動します。彼が国境に来るまで青い点を丸で囲んでいない場合、あなたは負けてゲームが再開します。

そのため、プレーヤーボタンから境界線までの最短パスを見つけるために、UIButtonの2D配列に対して幅優先探索を実行する必要があります。

問題:

多くの場合、境界線へのパスが見つかりません(コンソールに「パスが見つかりません!」と表示されて再起動します)。たとえ青い点が境界線に到達する可能性がある場合でも、ドットがオレンジ色の点で囲まれていません。また、最短経路をたどらず、ドットがループすることがあります。ダウン、アップ、ダウン、...それは勝つことをかなり簡単にします。

私のプロジェクト:

私のプロジェクト(全部で300行のコード)をここからダウンロードできれば最高です。次に、これらのパターンで問題をテストできます:(ラベルの付いたボタン/ドットの所定の順序をクリックしてください)

  1. 可能なパスは見つかりませんが、多くあります:(1,2)->(0,3)->(1,4)

  2. 可能なパスは見つかりませんが、次のパスがあります:(2,2)->(1,3)->(2,4)->(2,5)->(3,5)->(4,4) ->(3,3)

  3. ループアップ/ダウン/アップ/...:(3,4)->(2,3)->(2,2)->(1,1)->(1,0)->(3,4 )->(3,5)->(4,6)->(4,7)->(5,8)

重要:これらの問題を確認する方法は無限にあります。3つのパターンは問題をすばやく見つけるためだけのものであり、問​​題が発生するまで何度も再生する必要はありません。またpossibleNeighbours.shuffle()、パターンがランダム化されるため、94行目()のコメントを外す必要があります。

プロジェクト全体をダウンロードしたくない場合は、幅優先探索メソッドを確認できます。このメソッドは、青い点が移動する必要のある次のx座標とy座標を返します。

    func findDirection()->String{
    var blockedArr:  [[Bool]] = [[false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false]] // Can do it like this as its always 9X9
    
    for btnline in btnArr{ //Block all dots which are already occupied
        for btn in btnline{
            if(btn.backgroundColor != defaultColor){
                blockedArr[getX(btn: btn)][getY(btn: btn)] = true
            }
        }
    }
    
    let otheryQueue = otherQueue<Pair>()
    let pair = Pair()
    var possibleNeighbours = findPossibleNeighbours(btn: btnArr[playerX][playerY], blockedArr: blockedArr) //returns array of all possible neighbours of given dot
    print(String(possibleNeighbours.description) + " possibeNeighs beginning" )
   //possibleNeighbours.shuffle() //IMPORTANT: Uncomment this to make it more random
    
    for neighbour in possibleNeighbours{
        if(isOnBorder(point: neighbour)){
            print("Blue dot is on border")
            return neighbour
        }
        pair.setPair(firstValue: neighbour, secondValue: neighbour)
        otheryQueue.enqueue(key: pair)
        blockedArr[getXFromString(string: neighbour)][getYFromString(string: neighbour)] = true
    }
    
    // Start the search
    while(!otheryQueue.isEmpty){
        let pointPair = otheryQueue.dequeue()
        let button = btnArr[getXFromString(string: (pointPair?.getFirst())!)][getYFromString(string: (pointPair?.getFirst())!)]
        possibleNeighbours = findPossibleNeighbours(btn: button, blockedArr: blockedArr)
        for neighbour in possibleNeighbours{
            if isOnBorder(point: neighbour){
                return (pointPair?.getSecond())!
            }
            pair.setPair(firstValue: neighbour, secondValue: (pointPair?.getSecond())!)
            otheryQueue.enqueue(key: pair)
            blockedArr[getXFromString(string: neighbour)][getYFromString(string: neighbour)] = true
        }
    }
    print("No path found!")
    return "-1 -1" //return (-1, -1) position if NO PATH FOUND
}

これは、(1,2)、(0,3)、青い点などの意味を理解するのに役立つ、ゲームビューのスクリーンショットです。

ご不明な点がございましたらお問い合わせください。

助けてくれてありがとう!

SwiftHobby

1 answers

1
DonMag 2020-10-16 11:20.

findDirection()func内に次のコードブロックがあります。

    let otheryQueue = otherQueue<Pair>()
    let pair = Pair()
    var possibleNeighbours = findPossibleNeighbours(btn: btnArr[playerX][playerY], blockedArr: blockedArr) //returns array of all possible neighbours of given dot
    print(String(possibleNeighbours.description) + " possibeNeighs beginning" )
   //possibleNeighbours.shuffle() //IMPORTANT: Uncomment this to make it more random
    
    for neighbour in possibleNeighbours{
        if(isOnBorder(point: neighbour)){
            print("Blue dot is on border")
            return neighbour
        }
        pair.setPair(firstValue: neighbour, secondValue: neighbour)
        otheryQueue.enqueue(key: pair)
        blockedArr[getXFromString(string: neighbour)][getYFromString(string: neighbour)] = true
    }

    // Start the search
    while(!otheryQueue.isEmpty){
       ...

デバッグするために、「検索の開始」の直前にこれを追加しました。

    var p = otheryQueue.first
    while p != nil {
        print("first", p?.data.first, "second", p?.data.second)
        p = p?.next
    }
    
    // Start the search
    while(!otheryQueue.isEmpty){
       ...

などの灰色の点をタップすること0 0から始めると、コンソールに表示される出力は次のとおりです。

Button 0 0 tapped
["4 3", "5 4", "4 5", "3 5", "3 4", "3 3"] possibeNeighs beginning
first Optional("3 3") second Optional("3 3")
first Optional("3 3") second Optional("3 3")
first Optional("3 3") second Optional("3 3")
first Optional("3 3") second Optional("3 3")
first Optional("3 3") second Optional("3 3")
first Optional("3 3") second Optional("3 3")

(最初にタップ3 3すると、出力はすべて「3 4」になります)。

コードではpair、オブジェクトを1つだけ作成し、ループを通過するたびにその値を変更しています。

必要になるたびに新しい pairオブジェクトを作成することをお勧めし.enqueueます。

    for neighbour in possibleNeighbours{
        if(isOnBorder(point: neighbour)){
            print("Blue dot is on border")
            return neighbour
        }
        
        // add this line
        let pair = Pair()
        
        pair.setPair(firstValue: neighbour, secondValue: neighbour)
        otheryQueue.enqueue(key: pair)
        blockedArr[getXFromString(string: neighbour)][getYFromString(string: neighbour)] = true
    }

これで、最初にタップしたときのコンソール出力0 0は次のようになります。

Button 0 0 tapped
["4 3", "5 4", "4 5", "3 5", "3 4", "3 3"] possibeNeighs beginning
first Optional("4 3") second Optional("4 3")
first Optional("5 4") second Optional("5 4")
first Optional("4 5") second Optional("4 5")
first Optional("3 5") second Optional("3 5")
first Optional("3 4") second Optional("3 4")
first Optional("3 3") second Optional("3 3")

次のブロック(検索ブロック)でも同じことをしたいと思うでしょう。

    // Start the search
    while(!otheryQueue.isEmpty){
        let pointPair = otheryQueue.dequeue()
        let button = btnArr[getXFromString(string: (pointPair?.getFirst())!)][getYFromString(string: (pointPair?.getFirst())!)]
        possibleNeighbours = findPossibleNeighbours(btn: button, blockedArr: blockedArr)
        for neighbour in possibleNeighbours{
            if isOnBorder(point: neighbour){
                return (pointPair?.getSecond())!
            }
            
            // add this line
            let pair = Pair()
            
            pair.setPair(firstValue: neighbour, secondValue: (pointPair?.getSecond())!)
            otheryQueue.enqueue(key: pair)
            blockedArr[getXFromString(string: neighbour)][getYFromString(string: neighbour)] = true
        }
    }

Related questions

MORE COOL STUFF

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire が息子の Shelby Blackstock と共有しているクリスマスの伝統について学びましょう。

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルとマライア・キャリーが自然な髪の上でどのように結合したかについて、メーガンの「アーキタイプ」ポッドキャストのエピソードで学びましょう.

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子が家族、特にチャールズ王とウィリアム王子との関係について望んでいると主張したある情報源を発見してください。

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドが、母親のナオミ・ジャッドが亡くなってから初めての感謝祭のお祝いを主催しているときに、彼女が今では家長であることをどのように認識したかを学びましょう.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

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

作家のアンバー・ラフィンとジェニー・ヘーゲルが上司のセス・マイヤーズを引き継ぐのを見る

作家のアンバー・ラフィンとジェニー・ヘーゲルが上司のセス・マイヤーズを引き継ぐのを見る

深夜のアンバー・ラフィンとジェニー・ヘーゲルが繰り返し「ジョーク・セス・カント・テル」で戻ってきました。これらのジョークの多くは観客をがっかりさせますが、最初から最後まで素晴らしいです。ルフィンとヘーゲルは黒人女性として自己紹介します。とゲイの女性、それぞれ、したがって、セスマイヤーズが10フィートのポールで触れることができない主題について賢明にクラックすることができます。

ジョンウィック:第3章は2019年5月に劇場への道を容赦なく殺します

ジョンウィック:第3章は2019年5月に劇場への道を容赦なく殺します

(写真:ライオンズゲート)この「キアヌ・リーブスはダッパースーツを着て人々を殺害する」というモチーフ全体が手元にあることをはっきりと知っているライオンズゲートは、スタイリッシュで復讐に燃えるジョン・ウィックのフランチャイズで3回目のリリース日を設定しました。犬をベースにした復讐のためのババ・ヤガの果てしない十字軍を支えるバットシット神話をより深く掘り下げることを約束する3番目のジョン・ウィック映画は、2019年5月17日に設定されました。これまでのところ、それはその日に上陸した唯一の映画です。

このパイロットは、This IsUsの残りの部分に高い基準を設定します

このパイロットは、This IsUsの残りの部分に高い基準を設定します

写真:NBCパイロットは良すぎるのでしょうか?ありそうもないようですが、This IsUsのファンの場合はそうかもしれません。クレイジー、バカ、ラブライターのダン・フォーゲルマンからの待望の新シリーズは、ツイストエンディングを中心に展開しています。シリーズを適切に設定しますが、非常に巧妙に行われているため、改善の余地はあまりありません。

ああ、GIFがついにFacebookで機能する

ああ、GIFがついにFacebookで機能する

ここにいくつかのニュースがあります:あなたは今FacebookにGIFを埋め込むことができます。まあ、技術的には、GIFへのリンクを投稿することができ、Facebookは、他のほとんどすべてのソーシャルネットワークが何年も行ってきたようにアニメーションを作成します。

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

ロシアのフィギュアスケーター、カミラ・バリエバが関与したドーピング事件が整理されているため、チームは2022年北京冬季オリンピックで獲得したメダルを待っています。

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

何千人ものAmazonの買い物客がMulberry Silk Pillowcaseを推奨しており、現在販売中. シルクの枕カバーにはいくつかの色があり、髪を柔らかく肌を透明に保ちます。Amazonで最大46%オフになっている間にシルクの枕カバーを購入してください

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

ラファイエット警察署は、「不審な男性が女性に近づいた」という複数の苦情を受けて、12 月にパデュー大学の教授の捜査を開始しました。

コンセプト ドリフト: AI にとって世界の変化は速すぎる

コンセプト ドリフト: AI にとって世界の変化は速すぎる

私たちの周りの世界と同じように、言語は常に変化しています。以前の時代では、言語の変化は数年または数十年にわたって発生していましたが、現在では数日または数時間で変化する可能性があります。

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

犯罪擁護派のオークランドが暴力犯罪者のロミオ・ロレンゾ・パーハムを釈放

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

認知症を患っている 91 歳のアジア人女性が最近、47 番街のアウター サンセット地区でロメオ ロレンゾ パーハムに襲われました。伝えられるところによると、被害者はサンフランシスコの通りを歩いていたところ、容疑者に近づき、攻撃を受け、暴行を受けました。

Precios accesibles, nuestro aprendizaje desde la perspectiva iOS

Precios accesibles, nuestro aprendizaje desde la perspectiva iOS

Cómo mejoramos la accesibilidad de nuestro componente de precio, y cómo nos marcó el camino hacia nuevos saberes para nuestro sistema de diseño. Por Ana Calderon y Laura Sarmiento Leer esta historia en inglés.

ℝ

“And a river went out of Eden to water the garden, and from thence it was parted and became into four heads” Genesis 2:10. ? The heart is located in the middle of the thoracic cavity, pointing eastward.

Language