単数チェック
荷物がひとつについての死に手チェックは、すべて同じ方法でできます。ゴールから引いてできる地図を作って利用するのです。

角)
 ■-
 日■
壁際)
 ■-日--■
 ■■■■■■
袋小路)
 -■■■■
 -■--■
 大日--■
 -■--■
 -■■■■

袋小路は人の位置が関係します。そのため、地図ひとつでは死かどうか判別できません。荷物に対して人の位置は4方向まであるので、地図を4つ作っておけば判別できます。
[PR]
# by sokoban | 2004-11-14 23:12 | アルゴリズム
凡例
キャラクタの意味を示しておきます。

荷物・・・・・・・日
ゴール・・・・・・十
番人(人)・・・・大
壁・・・・・・・・■
スペース・・・・・-
ゴールと荷物・・・田
番人と荷物・・・・木

以上は、基本キャラです。今後、説明用の専用キャラが出てきますが、それは後日。
[PR]
# by sokoban | 2004-11-14 00:40 | 解説
予備状態
押すと固定の死や袋小路などの死に手になってしまう。

固定の予備)
 ■-日-■
 ■■日■■
袋小路の予備)
 ■■■■
 ■---
 ■-日日
 ■■■-
 --■■
[PR]
# by sokoban | 2004-11-13 23:47 | 死に手パターン
袋小路
明治大論文で「袋小路」と名づけられた、「回復できない閉空間」。人の位置によっては死でなくなる。
閉空間を回復しようと押してみても、どうしても固定の死になってしまう。パターンはほぼ無限に存在する。

 -■■■■
 大日--■
 -■■■■

 ■■■
 日-日
 日日大

 大日日
 日-日
 日日-

 ■■■■■
 ■--日-
 ■--日-
 ■--日大
 ■■■■-
[PR]
# by sokoban | 2004-11-13 23:23 | 死に手パターン
壁が増えた死
荷物が不動になることによって、壁と同じになってしまう。つまり、迷路が変化したことによる死。
以下の例では、人の位置が関係する。

荷物に到達できなくなった)
 -■■■■■--
 ■-----■■
 ■十日---田田
 ■■■■■■-大
荷物をゴールに運べなくなった)
 -----■-
 ■■■■■田大
 -十日--田-
 ■■■■■--
[PR]
# by sokoban | 2004-11-13 22:35 | 死に手パターン
死に手の分類
死に手の例はまだまだありますが、ちょっと休憩。

種類をいくつか示しました。実は、このように単純に分類できるわけではありません。荷物がひとつか複数か、ゴールが関係するかしないか、人の位置が関係するかしないか・・・など、いろんな切り口があります。

荷物がひとつで成立する死に手は、チェックが簡単です。その荷物だけを押してみて、ゴールに到達できないことを確認するだけです。

荷物が複数で成立する死に手のチェックが困難なのです。いろんな工夫が必要になってきます。そのへんについては順次解説していきます。
[PR]
# by sokoban | 2004-11-13 21:43 | 解説
文献紹介
倉庫番の文献を見つけました。「情報処理」の田中哲朗氏による記事です。PDFが手に入ります。

http://www.ipsj.or.jp/07editj/promenade/4311.pdf

今年の「日経ソフトウェア」に、記事がありました。さくら美緒氏です。ネットでは読めませんが、プログラムがダウンロードできるようです。

http://software.nikkeibp.co.jp/software/download/down04c.html
2004年6月号

それぞれ、基本的な考え方がわかりやすく書いてあります。特にプログラムを書いてみようという方には、とても参考になると思います。
[PR]
# by sokoban | 2004-11-13 02:23 | 文献
ゴールから見た死
ゴールに対して、運び込める荷物がなくなった状態。ゴール複数の場合は、その数に見合う荷物がなくなった状態。

荷物の脱出による)
 -■■■-
 ■-十-■
 ■-大日■
 ■---■
 ■■■--
荷物の壁化による)
 -■■■■-
 ■十--田■
 ■■■-大-
[PR]
# by sokoban | 2004-11-13 01:44 | 死に手パターン
壁際の死
壁際の死。荷物の到達可能範囲に、数に見合うゴールが無い。

荷物1、ゴール0)
 ■-日-■
 -■■■-
荷物2、ゴール1)
 --■---■-
 ■-十日-日-■
 -■-■■■--
[PR]
# by sokoban | 2004-11-13 01:22 | 死に手パターン
固定の死
死に手のパターン。固定の死。

角)
 日■
 ■-
シチョウ)
 -■  ■日--
 日日  -日日-
 ■-  --日■
集四)
 日日
 日日
準集四)
 日日  日日
 日■  ■■
[PR]
# by sokoban | 2004-11-13 01:07 | 死に手パターン