华容道程序求解

华容道 游戏介绍：百度百科

github: lzhlyle/klotski

项目分期计划：

1. 实现对横刀立马布局的求解，导出步骤快照
2. 实现对标准华容道滑块（卒、五虎上将、曹操）任意布局的求解
3. 实现对任意自定义滑块、自定义棋盘的求解

技术路线：Spring Boot，JUnit

---

关键类与扩展思路

拆解问题域

阅读建议：新页面打开关键类图，比对下列问题域

• 滑块域 block：解决滑块形状问题
  • 抽象滑块 Block(Abstract) ，所有滑块父类。
  • 具体滑块：2x2大方块 Square（曹操），1x2水平条形块 Horizontal、2x1垂直条形块 Vertical（五虎上将），1x1小方块 Cube（卒）。
  • 扩展：任意形状滑块都可在此域扩展。如3x3, 2x3 等长方形块可直接扩展，如L字形、T字形等特殊块也可在Block下扩展（第三期支持）。3D立体的滑块也可从此扩展，穿透型滑块也可以，隔离出滑块域就为了独立关注滑块问题。
• 棋盘域 board：解决棋盘形状问题
  • 棋盘 Board，定义棋盘格数，棋盘形状，默认4x5方形，不包括开局摆放——这是攻略域中快照的任务——毕竟没有"游戏"，"摆放"将毫无意义。
  • 格子 Cell，定义每个格子，都占1个单位，尤其关注是否被占用着——空着的格子附近的滑块才可移动，尽快找到可移动的滑块，可使用原型模式创建。
  • 滑块位置 BlockPlace，定义滑块与格子此刻的关系。
  • 扩展：棋盘形状可更大（当然滑块也可更多），甚至十字形、大环形等特殊形状扩展（第三期支持）。双层棋盘、立方体棋盘、某边（或立方体的某面）有引力的棋盘、棋盘还可动态增加或减少格子等棋盘域自己的变化与能力，都可就此扩展。
• 移动域 move：解决行动力问题
  • 接口 IMovable 表示一种能力，抽象滑块都有此能力，故 Block implements IMovable
  • 移动方向 MoveDirection，只有上下左右四个方向。看到github上不少华容道项目的方向还有 左上、右下等拐弯方向定义——我想是因为华容道算步数的时候，1x1的卒一次性移动拐弯方向的两个格子时，算作一步的原因——但这其实是计步器中关于移动的规则（涉及计步域、规则域），假设卒移动一个格子就算一步，或者棋盘扩展后支持三个空格可移动时，就会有左上右等两个拐点的移动方式时，增加枚举就不灵活了，故本质上还是计步器与移动规则的职责。
  • 扩展：行动力可以有条件（某些滑块挨在一起则增加/减少行动力），立体棋盘可向纵轴z方向移动等等。
• 开局域 opening：// TODO
• 游戏域 game：
• 规则域 regulation：
• 计步域 pedometer：
• 攻略域 quide：
• 解题域 slover：
• ValueObject：
  • 位置坐标 Position，定义格子所在坐标，(x, y) 表示，棋盘左下角为(0, 0)——都位于第一象限，最大(4, 5)，可使用原型模式创建。
  • 快照 Snapshot，
  • 历时 Duration，

关键类图

持续更新中...

原文链接:https://www.cnblogs.com/lzhlyle/p/klotski.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有