求解器
YASS
流程图
flowchart TD
A[开始] --> B[初始化应用程序]
B --> C[解析命令行参数]
C --> D[加载级别文件]
D --> E[处理每个级别]
E --> F[初始化游戏状态]
F --> G{是否启用求解器?}
G -->|是| H[运行求解器搜索]
G -->|否| I{是否启用优化器?}
H --> J[找到解决方案?]
J -->|是| K[优化解决方案]
J -->|否| L[记录未解决]
I -->|是| K
K --> M[输出结果]
M --> N[处理下一个级别]
N --> O[所有级别处理完毕?]
O -->|否| E
O -->|是| P[生成统计报告]
P --> Q[结束]
subgraph "主要组件"
R[Game: 游戏状态管理]
S[Solver: 搜索算法]
T[Optimizer: 优化算法]
U[Positions: 转置表和队列]
V[DeadlockSets: 死锁检测]
W[Reader: 文件读取]
X[LogFile: 日志记录]
end
F --> R
H --> S
K --> T
S --> U
S --> V
D --> W
E --> X
模块关系图
graph TD
A[主程序] --> B[Game 模块]
A --> C[Solver 模块]
A --> D[Optimizer 模块]
A --> E[Positions 模块]
A --> F[DeadlockSets 模块]
A --> G[Reader 模块]
A --> H[LogFile 模块]
A --> I[GraphFile 模块]
B --> J[板子状态]
B --> K[盒子位置]
B --> L[玩家位置]
B --> M[历史记录]
C --> N[搜索限制]
C --> O[搜索方法]
C --> P[打包顺序]
D --> Q[优化方法]
D --> R[邻域设置]
E --> S[转置表]
E --> T[开放队列]
E --> U[统计信息]
F --> V[死锁集]
F --> W[容量管理]
G --> X[文件解析]
G --> Y[级别加载]
H --> Z[日志写入]
I --> AA[图形文件]
subgraph "数据流"
BB[输入文件] --> G
G --> B
B --> C
C --> E
E --> D
D --> H
H --> CC[输出文件]
end
类图
classDiagram
class Game {
+Board: TBoard
+BoxPos: TBoxSquares
+PlayerPos: Int
+History: THistory
+DeadlockSets: TDeadlockSets
+SimpleLowerBound: Int
+HashValue: THashValue
+Title: String
+OriginalSolution: String
}
class Solver {
+Enabled: Boolean
+SearchLimits: TSearchLimits
+SearchMethod: TSearchMethod
+PackingOrder: TPackingOrder
+PushCount: Int64
+MoveCount: Int64
+TimeMS: TTimeMS
+SokobanStatus: TSokobanStatus
}
class Optimizer {
+Enabled: Boolean
+Optimization: TOptimization
+MethodEnabled: TOptimizationMethodEnabled
+VicinitySettings: TVicinitySettings
+GameMetrics: TOptimizerGameMetrics
+TimeMS: TTimeMS
+Result: TPluginResult
}
class Positions {
+Capacity: UInt
+Count: UInt
+Positions: PPositionVector
+HashBuckets: PPositionPointersVector
+OpenPositions: TOpenPositions
+BestPosition: PPosition
+StartPosition: PPosition
+Statistics: TSearchStatistics
}
class DeadlockSets {
+Count: Int
+Capacity: TDeadlockSetCapacities
+Flags: array of TDeadlockSetFlagsSet
+CenterSquare: array of Int16
+FloorCount: array of Int16
+HashKey: array of THashValue
+TimeMS: TTimeMS
+TestedCandidatesCount: Int
}
class Reader {
+InputFile: TextFile
+InputFileName: String
+CurrentTextLine: String
+LevelCount: UInt
+FirstLevelNo: UInt
+LastLevelNo: UInt
}
class LogFile {
+Enabled: Boolean
+FileName: String
+TextFile: TextFile
}
Game --> Solver : 使用
Game --> Optimizer : 使用
Solver --> Positions : 使用
Solver --> DeadlockSets : 使用
Optimizer --> Positions : 使用
Reader --> Game : 加载数据
LogFile --> Game : 记录日志
时序图
sequenceDiagram
participant User
participant Main
participant Reader
participant Game
participant Solver
participant Optimizer
participant Positions
participant DeadlockSets
User->>Main: 启动程序
Main->>Reader: 加载级别文件
Reader-->>Main: 返回级别数据
Main->>Game: 初始化游戏状态
Game-->>Main: 游戏就绪
Main->>Solver: 启用求解器?
Solver-->>Main: 是
Main->>Solver: 运行搜索
Solver->>Positions: 初始化转置表
Positions-->>Solver: 转置表就绪
Solver->>DeadlockSets: 检查死锁
DeadlockSets-->>Solver: 死锁信息
Solver-->>Main: 解决方案
Main->>Optimizer: 优化解决方案
Optimizer->>Positions: 使用转置表
Positions-->>Optimizer: 优化结果
Optimizer-->>Main: 优化完成
Main->>User: 输出结果
搜索算法流程图
flowchart TD
A[开始搜索] --> B[初始化开放队列和转置表]
B --> C[将起始位置加入开放队列]
C --> D{队列为空?}
D -->|是| E[无解决方案]
D -->|否| F[从队列中移除最佳位置]
F --> G[扩展位置: 生成后继]
G --> H{找到目标?}
H -->|是| I[记录解决方案]
H -->|否| J[将后继加入队列]
J --> D
I --> K[优化解决方案]
K --> L[结束]
subgraph "搜索算法细节"
M[前向搜索: 从起始到目标]
N[后向搜索: 从目标到起始]
O[周边搜索: 优化局部路径]
P[全局搜索: 全面优化]
Q[盒子排列搜索: 排列盒子]
end
G --> M
G --> N
K --> O
K --> P
K --> Q
Festival
主要类图
classDiagram
class Board {
+int height
+int width
+char data[MAX_SIZE][MAX_SIZE]
+void copy_board()
+void show_board()
}
class Position {
+UINT_8* board
+move* moves
+score_element* scores
+position* father
+int depth
+score_element position_score
+int pull_mode
+int search_mode
+void set_first_position()
+void expand_position()
}
class Tree {
+expansion_data* root
+expansion_data* best
+int pull_mode
+int search_mode
+void reset_tree()
+void expand_tree()
}
class Helper {
+oop_data* oop
+imagine_data* imagine
+request_data* request
+int perimeter_found
+void init_helper_extra_fields()
}
class ExpansionData {
+position* node
+expansion_data* father
+int son_index
+int deadlocked
+score_element score
}
class Move {
+int from_y, from_x
+int to_y, to_x
+int box_y, box_x
+int direction
}
Board --> Position : contains
Position --> Tree : part of
Tree --> ExpansionData : manages
Helper --> Tree : assists
Position --> Move : has possible
搜索流程图
flowchart TD
A[main] --> B[process_args]
B --> C[allocate_resources]
C --> D[solve_level_set]
D --> E[load_level_from_file]
E --> F[solve_with_time_control]
F --> G{solve_with_alg}
G --> H{FESS}
G --> I{Girl RL}
G --> J{Dragonfly Greedy}
H --> K[init_scored_distance]
K --> L[reset_tree]
L --> M[expand_tree_loop]
M --> N{time_exceeded?}
N -->|No| O[pick_candidate]
O --> P[expand_node]
P --> Q{node_solved?}
Q -->|Yes| R[store_solution]
Q -->|No| S[update_best]
S --> M
N -->|Yes| T[return]
I --> U[greedy_iterations]
J --> V[manhattan_distance_search]
模块依赖图
graph TD
sokoban_solver.cpp --> engine.cpp
sokoban_solver.cpp --> girl.cpp
sokoban_solver.cpp --> dragonfly.cpp
sokoban_solver.cpp --> packing_search.cpp
engine.cpp --> tree.cpp
engine.cpp --> positions.cpp
engine.cpp --> moves.cpp
engine.cpp --> deadlock.cpp
engine.cpp --> advanced_deadlock.cpp
engine.cpp --> cycle_deadlock.cpp
engine.cpp --> stuck.cpp
tree.cpp --> board.cpp
positions.cpp --> board.cpp
moves.cpp --> board.cpp
deadlock.cpp --> board.cpp
board.cpp --> global.cpp
board.cpp --> util.cpp
helper.cpp --> imagine.cpp
helper.cpp --> oop.cpp
helper.cpp --> request.cpp
packing_search.cpp --> bfs.cpp
packing_search.cpp --> \graph.cpp
packing_search.cpp --> perimeter.cpp
packing_search.cpp --> park_order.cpp
packing_search.cpp --> hf_search.cpp
io.cpp --> board.cpp
debug.cpp --> tree.cpp
debug.cpp --> helper.cpp
死锁检测模块图
graph TD
deadlock.cpp --> deadlock_utils.cpp
advanced_deadlock.cpp --> deadlock.cpp
cycle_deadlock.cpp --> deadlock.cpp
xy_deadlock.cpp --> deadlock.cpp
k_dist_deadlock.cpp --> deadlock.cpp
rooms_deadlock.cpp --> rooms.cpp
corral_deadlock.cpp --> corral.cpp
mpdb2.cpp --> board.cpp
stuck.cpp --> tree.cpp
stuck.cpp --> board.cpp
启发式和评分模块图
graph TD
score.cpp --> board.cpp
heuristics.cpp --> score.cpp
greedy.cpp --> heuristics.cpp
girl.cpp --> greedy.cpp
imagine.cpp --> park_order.cpp
imagine.cpp --> packing_search.cpp
imagine.cpp --> hf_search.cpp
distance.cpp --> board.cpp
match_distance.cpp --> distance.cpp
max_dist.cpp --> distance.cpp
hotspot.cpp --> board.cpp
holes.cpp --> board.cpp
perimeter.cpp --> board.cpp
envelope.cpp --> board.cpp
overlap.cpp --> board.cpp
biconnect.cpp --> \graph.cpp
\graph.cpp --> board.cpp
数据结构关系图
graph TD
Board --> Positions
Positions --> Tree
Tree --> ExpansionData
ExpansionData --> Position
Position --> Moves
Position --> Scores
Helper --> OOP
Helper --> Imagine
Helper --> Request
Imagine --> ParkOrder
ParkOrder --> Rooms
Rooms --> Graph
Graph --> Biconnect