Undo処理の実装 - Githubissues

mikarru commented 6 years ago

実装がほぼ完了しました。

Undo処理の大まかな実装方針
- Tile配置やMeeple配置によって起こったことを記録しておいて、undo時にはそれを取り消す処理を行う
- 記録すること
  - 配置したTile
  - Meepleを配置したSegment
  - 新規生成されたRegion
  - マージされたRegion
  - 完成したRegion
その他
- undo処理を可能にするため、Regionの構造を大きく変えた
  - マージという処理に関して木構造を形作るようにした
    - 理由：マージに伴うRegion中のSegmentの移し替えをなくすことができ、マージの取り消し処理を行いやすくなる
- 例のインクルードの問題は、クラスの宣言があれば済む箇所はインクルードをしないことによって回避した(これが良い方法なのかは不明)
- Boardの実装が大きく変わってしまったので、棋譜読み込みの実装はこちらの実装に合わせます。
  - このPRがマージされた後にPR出します。(一応、前のBoardを元にした実装はscore-sheetというブランチにある)

残作業

テストの追加
バグ修正(あれば)
リファクタリング
コメント追加

sash2104 commented 6 years ago

ちゃんとしたレビューは週末にするけど、パッと見て気になった一点だけ。 undo (redo) の処理は、Commandパターンを使うと実装が多少簡潔になるイメージがある。参考 : http://gameprogrammingpatterns.com/command.html

俵君の実装でいうと、

基底クラスとしてEventクラスを作る
- Eventクラスは、undo()をメンバ関数にもつ
PlacementEventクラスとかの他のxxxEventクラスは、Eventクラスを継承して個々のundoを実装する
xxxEventが起こるたびに、Eventのstackもしくは配列にxxxEventクラスを積んでいって、undoしたいときは順にxxxEventのundo()を実行していく

みたいな。

実装コストはかかりそうだし、実際にCommandパターンでundoを実装すべきかは微妙だけど。 redoも必要、とか、undoの処理がもっと複雑になりそう、とかだったら検討の価値はあると思う。

mikarru commented 6 years ago

ありがとう。 Commandパターンは知らなかったから勉強してみる。Commandパターンを使うかどうかはその後考えてみるわ。

redo処理は少なくともBoardの中にはいらないような気がするな。 redo処理が必要だったら、Boardの外でタイルの置き方を覚えといて、それをもう一回置くような実装の方がBoardの実装がスッキリすると思う。

sash2104 commented 6 years ago

region同士を結合する処理、union-findってアルゴリズムが使えるかも？ https://www.slideshare.net/chokudai/union-find-49066733 カルカソンヌで使えるかちょっと自信はないけど、知らなかったら参考にしてください。

sash2104 commented 6 years ago

主にロジックで気になった部分にコメントしました。 (効率化できそうな部分はいくつかあるけど、それは別の機会にまとめて対応した方がいい気がしたのであまりこめんとしてない)

mikarru commented 6 years ago

region同士を結合する処理、union-findってアルゴリズムが使えるかも？

テスト追加とか終わったら使えるか見てみるわ。ありがとう。 (作業遅れててすまない。)

mikarru commented 6 years ago

これまでの主な修正点

Regionのfirst_child_メンバを削除
SegmentIteratorを返すところでstd::moveを使うように修正
segment_countのカウント処理を修正

mikarru commented 6 years ago

寝落ちしてました。

UnionFind勉強してみたけど、Regionをグループ分けしたいって意味では、今の実装で一番単純なUnionFindになってるっていえると思う。資料に書かれている経路圧縮とかランクといった効率化は、Regionではmergeをundoできる必要があるので難しそう。(資料18Pの補足で「Union-Find 木はグループをまとめることはできても，分割することはできない」ってあるね。)

sash2104 commented 6 years ago

確かに。undoのことを考えると効率化は難しそうだし、今の実装の方がよさそうだね。

mikarru commented 6 years ago

mergeRegionの中の条件にregion->isMerged()が含まれてると、本来mergeすべきときにmergeしないことがある気がしてて、
. 0 .
. * .
. a A
で

0とaがadjacent_regions

aとAも同じregion

Aがaのparent みたいな場合、*とaはmergeされないような気がする？

よく考えたら上の場合も大丈夫やった。(上手くいきそうにないテストケース作ってみたけど、なんか上手いくのでずっと考えてた。)

Segment*から隣接するRegionを求める処理は、まずは隣接するSegmentを求めて、そっからSegment.getRegion()で隣接しているRegionをもとめるんやけど、Regionaに含まれていたSegment sは、RegionaがRegionAにマージされたときに、s.getRegion()がRegionAを指すように変更されてるから、隣接するRegionとして得られるのはRegionaではなくてRegionAになる。

mikarru commented 6 years ago

主な変更点

TilePositionMapのテスト追加とバグ修正
Boardのテスト追加とバグ修正
マージされたRegion(=RootでないRegion)は他のRegionをマージできない制約を追加
Board.endTurn()、Board.endGame()追加
リファクタリング

残りの作業

コメント追加
Commandパターンの検討

mikarru commented 6 years ago

コード自体はマージしても機能的に問題ないと思うのでWIPを外します。

sash2104 commented 6 years ago

Segment*から隣接するRegionを求める処理は、まずは隣接するSegmentを求めて、そっからSegment.getRegion()で隣接しているRegionをもとめるんやけど、Regionaに含まれていたSegment sは、RegionaがRegionAにマージされたときに、s.getRegion()がRegionAを指すように変更されてるから、隣接するRegionとして得られるのはRegionaではなくてRegionAになる。

なるほど。mergeRegionの中でs->setRegion(this)してるからうまくいくのか。これって親の親がいる場合でもうまくいく？例えば、

. . . 
. * .
. a b c

で

aがadjacent_regions
a, b, cが同じregion、bがaの親でcがbの親

みたいな場合

mikarru commented 6 years ago

その場合でも上手くいく。 b(aをマージ済み)をcにmergeするときに、aとbに含まれる全てのSegmentに対してs.setRegion(c)が呼び出されるから。 mergeRegionメンバ関数みてもらえばわかると思うけど、s.setRegionするsはb.segments_ではなくて、b.segmentBegin()で得られるイテレータでイテレートするSegment全部になってる。そして、それはaとbに含まれる全てのSegment

sash2104 commented 6 years ago

ありがとう。理解しました。一旦この段階でマージしてもいいかなと思ってるんだけど、残りの作業にかいてあるコメント追加とCommandパターンの検討はすぐにやる予定？

mikarru commented 6 years ago

一々イテレートしてるから、処理的に見直す必要はあるかもしれんね。見直すとしたら、mergeRegionのときにsegment->setRegion(this)を呼び出さないようにして、代わりにsegment->getRootRegionみたいなメンバ関数を作って、それでsegmentが所属しているRegionを得るようにする、みたいな感じかな。この場合だとsegment->getRootRegionのときに木をたどる必要が出てくるので、どちらの方が早いかはユースケースによるよね。

mikarru commented 6 years ago

コメント追加はそんな時間かからないから、それ終わったらマージしてもらってもいい？(今日の19時までには終わらせる。) (Commandパターンはもう少し時間がかかるので別PRに回します。)

sash2104 commented 6 years ago

ありがとう。高速化は、一通り実装終わった後にまとめて検討したいねー。

コメント追加はそんな時間かからないから、それ終わったらマージしてもらってもいい？

了解です。マージは急がないから19時までじゃなくても大丈夫だよ

mikarru commented 6 years ago

ちょっとだけどコメント追加しました。問題なければマージして下さい ><

sash2104 commented 6 years ago

コメント追加ありがとうございます。問題なさそうなのでマージします。

sash2104 / carcassonne

Undo処理の実装 #10