Search

Computer House Random
Computer House Random
  • Randomについて
  • ブログ
  • Project
  • 作品紹介
  • 部員紹介

最短手数を見つけた(8パズル)

8パズルを頑張って作ってる途中

n_itsuki
2021/04/27

ランダムでは、例年5月にある友好祭で一人一作品を作り提出するという伝統があるらしいです。 この記事では、友好祭に提出する作品として現在絶賛制作中の「8パズル」の進捗報告をかいていきます。

8パズルとは

記事の一番上の画像のように、ランダムに配置された状態から、1から8の数字が順に並べられた状態に出来るだけ少ない移動で目標状態を目指すやつです。

何を作りたいのか

Python/Unityで

  1. 最短手数とステップを求める
  2. 盤面を生成する
  3. プレイヤーがマスを動かせるようにする
  4. 数字が揃ったら終了する
  5. ヒントボタンが押されたら盤面を一つ、最短手数に基づいて変える(もしできたら)
  6. 文字だけじゃなくて、プレイヤーが好きな画像を設定できる(もしできたら)

ゲームを作りたい

できたこと1 最短手数とステップを求める

最短手数を求めるのに幅優先探索がいいということは聞いていたので、頑張って実装してみました。

(幅優先探索は、出発点に近い点から順に探索するアルゴリズムです。詳しいことは、Qiitaに載ってます)

実装する際に詰まったことは、実行時間の遅さです。8パズルは最長手が31手なのですが、15手ですら2秒位かかり、現実的なプログラムではありませんでした。これは、探したら双方向探索なる方法があるらしく、それで解決しました。

(双方向探索は、初期状態と目標状態の2つから同時に探索を始め、同じ状態になったら終了するアルゴリズムです。) 参考ししたサイト

できたこと2 盤面を生成する

盤面を生成することは簡単だったのですが、それが解けるかどううかを判断するのが大変でした。Pythonだと配列の比較が簡単だったのですが、C#だと上手くいきませんでした。対応策として、SequenceEqual()を使い配列を比較しました。(Unityのコードは基本的にC#で書かないといけないのですが苦手なので、最初は好きな言語であるPythonで書きました)

できたこと3 マスを動かす

ここから、C#(Unity)で作ることに飽きてきたので、Pygameに方針転換しました。 マスのリストを更新し忘れたり、画面外にマスが動いたり、想定している場所に動かなかったりと大変でした。 最終的には、下のように書けました。

                if event.key == K_RIGHT:
                    dest = (x - 1) + y * 3
                    if not dest in adjacent[space]:
                        continue
                    num_rect[start_lst[space] - 1].move_ip(-100, 0)
                    num_rect[start_lst[dest] - 1].move_ip(100, 0)
                    start_lst[dest], start_lst[space] = start_lst[space], start_lst[dest]
                    space = dest

できたこと4 ヒントを表示する

最短経路は

class State:
    def __init__( self, board, space, prev, way, trial ):
        self.board = board
        self.space = space
        self.prev = prev
        self.way = way
        self.trial = trial

こんなクラスに保存してあるので、prevを遡って得た盤面を表示することにしました。

できなかったこと5 マスを任意の画像にする

どうすればいいかわからない。そもそも、どうやって画像を取得すればいいのだろうか?

さいごに

途中まで書いたC#のコードがもったいないので、Unityでも作るかもしれません。 (追記:デザイン性は皆無ですが、作れました。C#めんどくさい) 読み返してみると、「最短手数の求め方」についてあんまり書いてないので、タイトル詐欺かも

新入生向けブログリレー2021

2021年度オンライン部活動説明
雑談 趣味 アルゴリズム ゲーム制作 PYTHON 記事を共有
Avatar
n_itsuki

緑になりたい

Computer House Random はパソコンによる創作活動を行っている大阪府立大学の部活動です

Avatar
n_itsuki

緑になりたい

雑談 趣味 アルゴリズム ゲーム制作 PYTHON 記事を共有

News

ICPC2020参加記

ICPC
pngn
2021/05/08

コンピュータハウスランダムってどんな部活?

【1日目】5分でわかるランダムのこと
NEGI
最終更新 2020/04/18

はじめまして、らんだむちゃんです!

自己紹介と最初の動画
らんだむちゃん
最終更新 2020/03/19

作品紹介

【18日目】難波駅構内をblenderで再現してみた

途中経過
うっかり侍
2021/08/31

【17日目】ウィルダネスアドベンチャー(?)

いつかリベンジする
クマイザサ
最終更新 2021/08/30

【16日目】CHICKEN NIGHTS

正直、すまんかった
Marcus
最終更新 2021/08/29

Tag Cloud

作品紹介 (48) 新歓ブログリレー2021 (46) 新歓ブログリレー2020 (37) 競技プログラミング (34) 新歓ブログリレー2022 (33) 雑談 (32) ゲーム (30) ゲーム制作 (24) 競プロ勉強会 (22) 作品展示リレー2021夏 (19)

最新の投稿

【38日目】OneDriveでファイルを管理して授業や部活で活用しよう!

オム大、クラウド1TBくれるってよ
Kwang
最終更新 2022/04/29

【37日目】受けループやらメタビートやらのすゝめ

(ゲームにおいては)人の嫌がることをするのが最も楽しい
クマイザサ
2022/04/28

【36日目】マイクラのMODパックで遊ぼう

MODパックの導入は難しそうって思ってない?
neuron
2022/04/27

【35日目】大阪公立大学 中百舌鳥図書館利用のススメ

かなり長め
Rikky
2022/04/26
READ MORE

関連記事


内田真礼はいいぞ

推しの声優さんを紹介します。

Avatar

Quizletのすゝめ

単語帳の紹介

Avatar

【20日目】おすすめPodcast3選

Spotifyの犬「ワンワン」

Avatar

【8日目】ClariSのすゝめ

4月6日に新アルバム発売

Avatar

【17日目】ウィルダネスアドベンチャー(?)

いつかリベンジする

Avatar

【14日目】もぐらたたき

製作途中のゲームの紹介です

Avatar

Random
Randomについて
ライセンス
Privacy Policy
お問い合わせ
部員専用サイト
Project
新入生向けブログリレー2022
作品展示リレー2021夏
競プロ勉強会
Web
らんだむちゃん
ブログ
作品紹介
LT会
グラフィック
DTM
タグ一覧
Copyright © 2020 Computer House Random
引用
コピー ダウンロード