羊了个羊是一款爆火的益智消除游戏，核心机制是将多层堆叠的图案卡牌逐层暴露，玩家每次选择三张相同图案的卡牌放入下方槽位，凑齐三张即可消除。当槽位填满（通常7张）且无法消除时游戏结束。本文用Java实现其核心算法引擎。
游戏机制建模
游戏的核心数据结构是一个多层堆叠的卡牌系统，每张卡牌位于特定层，被上层的卡牌覆盖时不可点击。
public class SheepGameEngine {
// 卡牌图案类型
enum Pattern {
CARROT, CORN, GRASS, BRUSH, GLOVE, SCISSORS,
BELL, FIRE, MILK, WOOL, HAY, FORK, BUCKET, PITCHFORK
}
static class Card {
Pattern pattern;
int layer; // 所在层数（0为最底层）
int x, y; // 网格坐标
boolean isRemoved; // 是否已被消除
Card(Pattern p, int layer, int x, int y) {
this.pattern = p;
this.layer = layer;
this.x = x;
this.y = y;
}
}
// 游戏配置
static final int SLOT_CAPACITY = 7; // 槽位容量
static final int MATCH_COUNT = 3; // 消除所需相同卡牌数
static final int BOARD_WIDTH = 8;
static final int BOARD_HEIGHT = 10;
static final int MAX_LAYERS = 5;
private final List<Card> allCards;
private final List<Card> slot; // 下方槽位（用List模拟栈）
private final boolean[][][] occupied; // 三维占用标记 [layer][y][x]
public SheepGameEngine() {
this.allCards = new ArrayList<>();
this.slot = new ArrayList<>();
this.occupied = new boolean[MAX_LAYERS][BOARD_HEIGHT][BOARD_WIDTH];
}
}
卡牌堆叠与覆盖检测
每张卡牌可能被同层或上层的其他卡牌部分覆盖。我们使用网格离散化方法检测覆盖关系。
public class SheepGameEngine {
/**
* 生成随机但可解的关卡布局
* 规则：总卡牌数必须是3的倍数，每种图案出现次数也是3的倍数
*/
public void generateLevel(int totalCards) {
if (totalCards % 3 != 0) {
throw new IllegalArgumentException("卡牌总数必须是3的倍数");
}
allCards.clear();
slot.clear();
// 确定每种图案的数量（每种至少3张，且为3的倍数）
int patternCount = Pattern.values().length;
int cardsPerPattern = totalCards / patternCount;
if (cardsPerPattern % 3 != 0) {
cardsPerPattern = (cardsPerPattern / 3) * 3;
}
List<Pattern> deck = new ArrayList<>();
for (Pattern p : Pattern.values()) {
for (int i = 0; i < cardsPerPattern; i++) {
deck.add(p);
}
}
Collections.shuffle(deck);
// 分层放置卡牌
int cardIndex = 0;
Random rand = new Random();
for (int layer = 0; layer < MAX_LAYERS && cardIndex < deck.size(); layer++) {
// 每层卡牌数量递减，形成金字塔结构
int cardsInLayer = Math.min(
deck.size() - cardIndex,
(MAX_LAYERS - layer) * 6 + 4
);
for (int i = 0; i < cardsInLayer; i++) {
// 随机位置，确保不与同层卡牌完全重叠
int x, y;
int attempts = 0;
do {
x = rand.nextInt(BOARD_WIDTH - 1);
y = rand.nextInt(BOARD_HEIGHT - 1);
attempts++;
} while (isOccupied(layer, x, y) && attempts < 50);
if (attempts >= 50) continue;
Card card = new Card(deck.get(cardIndex++), layer, x, y);
allCards.add(card);
markOccupied(layer, x, y);
}
}
// 确保有解性验证（简化版）
if (!hasValidSolution()) {
generateLevel(totalCards); // 重新生成
}
}
/**
* 检查网格位置是否被占用
* 每张卡牌占据2×2的网格区域
*/
private boolean isOccupied(int layer, int x, int y) {
for (int dy = 0; dy < 2; dy++) {
for (int dx = 0; dx < 2; dx++) {
if (y + dy >= BOARD_HEIGHT || x + dx >= BOARD_WIDTH) return true;
if (occupied[layer][y + dy][x + dx]) return true;
}
}
return false;
}
private void markOccupied(int layer, int x, int y) {
for (int dy = 0; dy < 2; dy++) {
for (int dx = 0; dx < 2; dx++) {
if (y + dy < BOARD_HEIGHT && x + dx < BOARD_WIDTH) {
occupied[layer][y + dy][x + dx] = true;
}
}
}
}
}
DFS可消除对检测
判断一张卡牌是否可以被点击，需要检查它是否被上层的任何卡牌覆盖。然后使用DFS搜索当前状态下所有可能的消除序列。
public class SheepGameEngine {
/**
* 检查卡牌是否被上层覆盖
*/
public boolean isCovered(Card card) {
if (card.isRemoved) return false;
// 检查更高层的卡牌是否与其位置重叠
for (Card other : allCards) {
if (other.isRemoved || other.layer <= card.layer) continue;
// 2×2卡牌区域的碰撞检测
if (Math.abs(other.x - card.x) < 2 && Math.abs(other.y - card.y) < 2) {
return true;
}
}
return false;
}
/**
* 获取当前所有可点击的卡牌
*/
public List<Card> getClickableCards() {
return allCards.stream()
.filter(c -> !c.isRemoved && !isCovered(c))
.collect(Collectors.toList());
}
/**
* 使用DFS搜索是否存在可行的消除路径
* @return 是否存在从当前状态到清空所有卡牌的路径
*/
public boolean hasValidSolution() {
return dfsSolve(new ArrayList<>(slot), new HashSet<>(allCards));
}
/**
* DFS求解：尝试所有可能的点击序列
* 使用剪枝策略减少搜索空间
*/
private boolean dfsSolve(List<Card> currentSlot, Set<Card> remaining) {
// 终止条件：所有卡牌消除
if (remaining.isEmpty()) return true;
// 剪枝：槽位已满且无法消除
if (currentSlot.size() >= SLOT_CAPACITY && !canEliminate(currentSlot)) {
return false;
}
// 获取可点击的卡牌
List<Card> clickable = remaining.stream()
.filter(c -> !isCovered(c))
.collect(Collectors.toList());
if (clickable.isEmpty()) return false;
// 按图案分组，优先选择能形成消除的卡牌
Map<Pattern, List<Card>> grouped = new HashMap<>();
for (Card c : clickable) {
grouped.computeIfAbsent(c.pattern, k -> new ArrayList<>()).add(c);
}
// 优先尝试：1) 放入槽位能立即消除的 2) 槽位中已有同图案的
List<Card> priorityOrder = new ArrayList<>();
for (Card c : clickable) {
long sameInSlot = currentSlot.stream().filter(s -> s.pattern == c.pattern).count();
if (sameInSlot >= 2) {
priorityOrder.add(0, c); // 能立即消除，最高优先级
} else if (sameInSlot >= 1) {
priorityOrder.add(c); // 有助于后续消除
} else {
priorityOrder.add(c);
}
}
// 遍历尝试
for (Card card : priorityOrder) {
// 模拟点击
currentSlot.add(card);
remaining.remove(card);
// 检查是否可以消除
boolean eliminated = false;
if (canEliminate(currentSlot)) {
eliminatePattern(currentSlot, card.pattern);
eliminated = true;
}
// 递归
if (currentSlot.size() < SLOT_CAPACITY && dfsSolve(currentSlot, remaining)) {
return true;
}
// 回溯
if (eliminated) {
// 恢复被消除的卡牌（简化处理：这里需要更精细的回溯）
restoreEliminated(card.pattern);
}
currentSlot.remove(currentSlot.size() - 1);
remaining.add(card);
}
return false;
}
/**
* 检查槽位中是否有可消除的三张相同图案
*/
private boolean canEliminate(List<Card> currentSlot) {
Map<Pattern, Long> count = currentSlot.stream()
.collect(Collectors.groupingBy(c -> c.pattern, Collectors.counting()));
return count.values().stream().anyMatch(c -> c >= 3);
}
/**
* 消除槽位中指定图案的三张卡牌
*/
private void eliminatePattern(List<Card> currentSlot, Pattern pattern) {
currentSlot.removeIf(c -> c.pattern == pattern);
}
private void restoreEliminated(Pattern pattern) {
// 在实际实现中需要维护消除历史栈
}
}
最优决策搜索
为了构建AI玩家，需要评估每次点击的长期价值，而不仅仅是短期收益。我们使用带启发函数的搜索策略。
public class SheepGameEngine {
/**
* 评估状态的优劣
* 考虑因素：槽位占用率、可点击卡牌数、图案分布均衡性
*/
private int evaluateState(List<Card> currentSlot, Set<Card> remaining) {
int score = 0;
// 1. 槽位空闲空间奖励
score += (SLOT_CAPACITY - currentSlot.size()) * 10;
// 2. 可点击卡牌数量奖励
List<Card> clickable = remaining.stream()
.filter(c -> !isCovered(c))
.collect(Collectors.toList());
score += clickable.size() * 5;
// 3. 槽位中图案多样性惩罚（同类聚集不利）
Map<Pattern, Long> slotCount = currentSlot.stream()
.collect(Collectors.groupingBy(c -> c.pattern, Collectors.counting()));
for (long count : slotCount.values()) {
if (count == 2) score -= 15; // 两张相同较危险
if (count >= 3) score += 50; // 可以消除很好
}
// 4. 剩余卡牌中各图案数量的均衡性
Map<Pattern, Long> remainCount = remaining.stream()
.collect(Collectors.groupingBy(c -> c.pattern, Collectors.counting()));
for (long count : remainCount.values()) {
if (count % 3 != 0) score -= 5; // 不能被3整除的图案难以处理
}
return score;
}
/**
* 使用启发式搜索找到最优的下一步
* 搜索深度为3，评估每种选择后的状态价值
*/
public Card findBestMove() {
List<Card> clickable = getClickableCards();
if (clickable.isEmpty()) return null;
Card bestCard = null;
int bestValue = Integer.MIN_VALUE;
for (Card card : clickable) {
int value = minimaxEvaluate(card, 3, Integer.MIN_VALUE, Integer.MAX_VALUE, true);
if (value > bestValue) {
bestValue = value;
bestCard = card;
}
}
return bestCard;
}
/**
* 带Alpha-Beta剪枝的极小极大评估
*/
private int minimaxEvaluate(Card move, int depth, int alpha, int beta, boolean isMax) {
if (depth == 0 || allCards.stream().allMatch(c -> c.isRemoved)) {
return evaluateState(slot, new HashSet<>(allCards));
}
// 模拟执行move
slot.add(move);
move.isRemoved = true;
boolean eliminated = false;
if (canEliminate(slot)) {
eliminatePattern(slot, move.pattern);
eliminated = true;
}
int value;
if (isMax) {
value = Integer.MIN_VALUE;
List<Card> nextClickable = getClickableCards();
for (Card next : nextClickable) {
value = Math.max(value, minimaxEvaluate(next, depth - 1, alpha, beta, false));
alpha = Math.max(alpha, value);
if (beta <= alpha) break;
}
if (nextClickable.isEmpty()) {
value = evaluateState(slot, new HashSet<>(allCards));
}
} else {
value = Integer.MAX_VALUE;
List<Card> nextClickable = getClickableCards();
for (Card next : nextClickable) {
value = Math.min(value, minimaxEvaluate(next, depth - 1, alpha, beta, true));
beta = Math.min(beta, value);
if (beta <= alpha) break;
}
if (nextClickable.isEmpty()) {
value = evaluateState(slot, new HashSet<>(allCards));
}
}
// 回溯
if (eliminated) {
// 恢复被消除的卡牌
// 简化处理：实际需维护精确状态
}
move.isRemoved = false;
slot.remove(move);
return value;
}
/**
* 执行玩家点击
*/
public boolean clickCard(Card card) {
if (card.isRemoved || isCovered(card)) return false;
if (slot.size() >= SLOT_CAPACITY) return false;
slot.add(card);
card.isRemoved = true;
// 检查消除
Map<Pattern, Long> count = slot.stream()
.collect(Collectors.groupingBy(c -> c.pattern, Collectors.counting()));
for (Map.Entry<Pattern, Long> entry : count.entrySet()) {
if (entry.getValue() >= 3) {
final Pattern p = entry.getKey();
slot.removeIf(c -> c.pattern == p);
System.out.println("消除了图案: " + p);
}
}
return true;
}
/**
* 检查游戏是否结束
*/
public boolean isGameOver() {
if (slot.size() >= SLOT_CAPACITY) {
// 槽位已满且无法消除
Map<Pattern, Long> count = slot.stream()
.collect(Collectors.groupingBy(c -> c.pattern, Collectors.counting()));
return count.values().stream().noneMatch(c -> c >= 3);
}
return false;
}
/**
* 检查是否获胜
*/
public boolean isWin() {
return allCards.stream().allMatch(c -> c.isRemoved);
}
}
运行演示
public class SheepGameDemo {
public static void main(String[] args) {
SheepGameEngine engine = new SheepGameEngine();
// 生成关卡：45张卡牌（15种图案 × 3张）
engine.generateLevel(45);
System.out.println("=== 羊了个羊AI演示 ===");
int moves = 0;
while (!engine.isGameOver() && !engine.isWin()) {
SheepGameEngine.Card best = engine.findBestMove();
if (best == null) break;
System.out.printf("第%d步: 选择 %s (位置:层%d, x%d, y%d)%n",
++moves, best.pattern, best.layer, best.x, best.y);
engine.clickCard(best);
if (engine.isWin()) {
System.out.println("恭喜通关！总步数: " + moves);
break;
}
}
if (engine.isGameOver()) {
System.out.println("游戏结束，槽位已满！");
}
}
}
算法复杂度分析
- 覆盖检测：对于每张卡牌，检查所有更高层卡牌的重叠情况，时间复杂度
O(L × C)，L为层数，C为总卡牌数。 - DFS可解性验证：最坏情况指数级
O(C!)，但通过以下剪枝大幅优化： - 槽位满剪枝
- 优先选择能立即消除的卡牌
- 图案分组减少分支
- Minimax搜索：深度为d的搜索，分支因子约为可点击卡牌数（通常5-15），使用Alpha-Beta剪枝后实际复杂度约为
O(b^(d/2))。
扩展方向
- 关卡生成优化：使用约束满足问题（CSP）求解器确保生成的关卡100%可解
- 概率分析：计算随机点击通关的概率，分析不同层数和卡牌分布对难度的影响
- 道具策略：实现洗牌、撤回、提示等道具的最优使用时机算法
- 多人对战：基于博弈论的实时策略调整，预测对手行为并做出最优响应
