puyo のバックアップ(No.11)

ぷよぷよプロジェクト &dagger;

ぷよコードby吉岡 &dagger;

O-Camlのプリントを見直しながら、記述したコードを書いておきます。

下記はremove関数を実装するためのものです。

type color = RED | BLUE | GREEN | YELLOW;;
type puyo=COLOR of color|JAMA|DEL_COLOR;;

DEL_COLORを消す予定ぷよとしています。

let rec deletecheck' plist y =
match y with
0 -> DEL_COLOR::(List.tl plist)
| y ->(List.hd plist)::(deletecheck' (List.tl plist) (y-1));;

let rec deletecheck plist (x,y)=
match x with
0 -> (deletecheck' (List.hd plist) y)::List.tl plist
| x ->List.hd plist::(deletecheck (List.tl plist) (x-1,y));;

消すぷよリスト要素をDEL_COLORに置換する関数です。

リストの要素を消す既存関数はあるのでしょうか？

let rec delete plist=
match plist with
| [] -> plist
| plist -> (List.filter (fun l -> l != DEL_COLOR)(List.hd plist))::(delete(List.tl plist));;

消す予定ぷよを実際にリストから消去する関数。

let rec remove t v =
match v with
[] -> delete t
| v ->(remove (deletecheck t (List.hd v)) (List.tl v));;

let vanish t = 
let connected t = []
in List.flatten(List.filter (fun l -> List.length l >= 4) (connected t));;

連結を調べるconnected関数ができません・・・orz

let rec rensa i p j t =
match vanish t with
[] -> (p,j,t)
| v -> rensa (i+1) (p+40*i) (j+(j+1)*i) (remove t v);;

現状状態だとconnectedができても、ぷよが消える時にその上下左右にあるお邪魔ぷよを消せないことに気が付きました。

なるほど、「消す」という情報を一旦 DEL_COLOR に押し込めてからフィルターを通す戦略ですね. 関数型言語では list の威力を発揮させるために、一旦中間的な list を作る手法はよく用いられます. 吉岡君が OCaml に慣れてきているからこそ思い付いたのだと思います. すばらしい.

改良するとすると、

消すかどうかの 1 ビットの情報なので、option 型を利用できる.
List.mapi : (int -> 'a -> 'b) -> 'a list -> 'b list という「今リストの何番目の要素を参照しているのかを教えてくれる map 関数」を作れば、もっと簡単に実装できそう.

といった点でしょうか. 例えばこんな感じ.

let remove t v =
  let marked =
    mapi 
      (fun i l -> 
        mapi 
          (fun j x ->
            if List.mem (i, j) v then
              None
            else
              Some x) l) t
  in
  let take_some l = function
    None -> l
  | Some v -> v :: l
  in
  List.map (List.rev $ (List.fold_left take_some [])) marked

(小笠原)

そういえば、お邪魔ぷよを消す処理を追加しないといけませんね、気づきませんでしたとりあえず、connected を貼っておきます. graph の型は、Geom.t * GSet.t です. (小笠原)

module Geom = struct
  type t = int * int
  let compare a b =
    let c = 
      compare (fst a) (fst b)
    in
    if c = 0 then
      compare (snd a) (snd b)
    else
      c
end

module GSet = Set.Make(Geom)

(**
   take connections.
*)
let connected t =
 let rec take_connection g t c =
   if GSet.is_empty t then
     g, GSet.elements c
   else
     let loc =
	GSet.choose t
     in
     let t =
	GSet.remove loc t
     in
     let c =
	GSet.add loc c
     in
     let t =
	try
	  GSet.union t
	  @@ GSet.filter (fun elem -> not (GSet.mem elem c))
	  @@ List.assoc loc g
	with
	  Not_found -> t
     in
     take_connection (List.remove_assoc loc g) t c
 in
 let rec reduce_graph cs = function
     [] -> cs
   | ((loc, _) :: _) as g ->
	let traverse = 
	  GSet.add loc GSet.empty
	in
	let g', connect =
	  take_connection g traverse GSet.empty
	in
	reduce_graph (connect :: cs) g'
 in
 reduce_graph [] (make_graph t)

↑

作成の流れ &dagger;

モデル作成
UIの作成
対戦する敵のアルゴリズム作成
テスト&レビュー

こんなとこでしょうか? 1がおおよそ出来れば、2と3は同時並行できると思います。

↑

参考 &dagger;

http://www13.plala.or.jp/kymats/study/game_other/TOKOPUYO/tokopuyo.html

もっと他にもあると思う

↑

モデル &dagger;

type color = RED | BLUE | GREEN | YELLOW | SEE_THROUGH
type kind = NORMAL | JAMA
type puyo = { color : color; kind : kind }

こんな感じで。あとは空間とぷよの配置の定義すればおしまい。配置から消えるぷよを求める関数とか作っとくと便利かな。

追記よろしく

↑

空間とぷよ反応 &dagger;

type space = puyo list list
let react (p:ps) = ...

型spaceは空間を表す．

react : space -> option (int, space) を想定．結果がNONEの場合は反応なし/連鎖終了，SOME (pt,ps) の時は反応ありで得点と反応後の空間の対を返す．全体としてかなりでかい関数になると思われる．

あと画面のエフェクトを考えると，消えたぷよの位置のリストも返すようにすれば，消えたときのエフェクトも描きやすいだろうと思う．

ところでどうやって再帰で書くんだろう．

配列を使って破壊的なアルゴリズムを記述するなら，割に簡単にできそう (参考に挙げたページとか)．(プログラム全体で配列を管理する必要は無く，あくまでもぷよの連鎖判定に (チェック済み部分を覚えておく為に) 配列を使うということ)

純粋関数的にやるとどうなる？ Stateモナドを使うか，継続渡し形式でやるか…？

#ありがとうございます。すばらしいです。とってもいい感じだと思います。

ところで、上記の react 関数をエレガントに記述する為に、それ程難しくない、うまい方法があります。別にもったいつける訳ではないのですが、皆さん少し考えてみると楽しいと思います。ヒントは「連結」です。