消消乐填充算法_用Vue写一个简单的开心消消乐游戏

消消乐填充算法是一种经典的游戏算法，其主要目的是在一个矩阵中，将相同的方块进行消除，以获得更高的分数。下面我会提供一个简单的Vue实现消消乐游戏的例子，并讲解其中的算法原理。

首先，我们需要创建一个包含所有游戏方块的矩阵。我们可以用一个二维数组来表示矩阵，其中每个元素代表一个方块。例如：

data: {
  matrix: [
    [1, 1, 2, 3, 2],
    [3, 2, 1, 2, 3],
    [1, 2, 1, 3, 2],
    [3, 1, 2, 1, 3],
    [2, 3, 1, 2, 1]
  ]
}

在上述代码中，我们创建了一个5x5的矩阵，其中每个方块的值为1、2或3。

接下来，我们需要实现一个算法来检查矩阵中是否存在相同的方块。我们可以使用深度优先搜索算法来遍历整个矩阵，以找到相邻的相同方块。具体实现代码如下：

function check(matrix, visited, row, col, value) {
  if (
    row < 0 ||
    row >= matrix.length ||
    col < 0 ||
    col >= matrix[0].length ||
    visited[row][col] ||
    matrix[row][col] !== value
  ) {
    return;
  }
  
  visited[row][col] = true;
  
  check(matrix, visited, row - 1, col, value); // 上
  check(matrix, visited, row + 1, col, value); // 下
  check(matrix, visited, row, col - 1, value); // 左
  check(matrix, visited, row, col + 1, value); // 右
}

在上述代码中，我们使用了一个visited数组来记录已经遍历过的方块，避免重复遍历。然后，我们对当前方块的上下左右进行递归遍历，直到找到所有相邻的相同方块。

接下来，我们需要实现一个算法来消除所有相邻的相同方块。我们可以使用一个队列来记录所有需要消除的方块。具体实现代码如下：

function remove(matrix, visited, row, col, value, queue) {
  if (
    row < 0 ||
    row >= matrix.length ||
    col < 0 ||
    col >= matrix[0].length ||
    visited[row][col] ||
    matrix[row][col] !== value
  ) {
    return;
  }
  
  visited[row][col] = true;
  queue.push({ row, col });
  
  remove(matrix, visited, row - 1, col, value, queue); // 上
  remove(matrix, visited, row + 1, col, value, queue); // 下
  remove(matrix, visited, row, col - 1, value, queue); // 左
  remove(matrix, visited, row, col + 1, value, queue); // 右
}

在上述代码中，我们使用了一个queue数组来记录需要消除的方块。然后，我们对当前方块的上下左右进行递归遍历，将所有相邻的相同方块加入到队列中。

最后，我们可以实现一个方法来执行整个游戏的主逻辑。具体实现代码如下：

methods: {
  play() {
    const { matrix } = this;
    const visited = matrix.map(row => row.map(() => false));
    
    for (let row = 0; row < matrix.length; row++) {
      for (let col = 0; col < matrix[0].length; col++) {
        if (!visited[row][col]) {
          const queue = [];
          const value = matrix[row][col];
          
          remove(matrix, visited, row, col, value, queue);
          
          if (queue.length > 1) {
            for (const { row, col } of queue) {
              matrix[row][col] = null;
            }
          }
        }
      }
    }
    
    for (let col = 0; col < matrix[0].length; col++) {
      const stack = [];
      
      for (let row = matrix.length - 1; row >= 0; row--) {
        if (matrix[row][col] !== null) {
          stack.push(matrix[row][col]);
        }
      }
      
      for (let row = matrix.length - 1; row >= 0; row--) {
        if (stack.length > 0) {
          matrix[row][col] = stack.pop();
        } else {
          matrix[row][col] = null;
        }
      }
    }
  }
}

在上述代码中，我们首先遍历整个矩阵，对每个未遍历过的方块进行消除操作。如果当前方块的相邻方块数量大于1，则将所有相邻方块的值设置为null，标记需要消除。然后，我们通过一个栈来将每列中的非null方块向下移动，以填补消除方块留下的空位。

最后，我们只需要在页面上渲染出所有方块，并绑定上点击事件即可。点击方块时，我们执行play方法来更新矩阵，并重新渲染页面。

完整代码如下：

<template>
  <div>
    <div v-for="(row, i) in matrix" :key="i" class="row">
      <div
        v-for="(value, j) in row"
        :key="j"
        class="block"
        :class="{ selected: selected === `${i}-${j}` }"
        :style="{ backgroundColor: colors[value] }"
        @click="onSelect(`${i}-${j}`)"
      ></div>
    </div>
  </div>
</template>

<script>
export default {
  data: {
    matrix: [
      [1, 1, 2, 3, 2],
      [3, 2, 1, 2, 3],
      [1, 2, 1, 3, 2],
      [3, 1, 2, 1, 3],
      [2, 3, 1, 2, 1]
    ],
    selected: null,
    colors: {
      1: '#f00',
      2: '#0f0',
      3: '#00f'
    }
  },
  methods: {
    onSelect(key) {
      if (this.selected === key) {
        this.selected = null;
      } else if (
        this.selected &&
        this.canSwap(this.selected, key)
      ) {
        this.swap(this.selected, key);
        this.play();
        this.selected = null;
      } else {
        this.selected = key;
      }
    },
    canSwap(key1, key2) {
      const [i1, j1] = key1.split('-');
      const [i2, j2] = key2.split('-');
      const di = Math.abs(i1 - i2);
      const dj = Math.abs(j1 - j2);
      return (di === 0 && dj === 1) || (di === 1 && dj === 0);
    },
    swap(key1, key2) {
      const [i1, j1] = key1.split('-');
      const [i2, j2] = key2.split('-');
      const temp = this.matrix[i1][j1];
      this.matrix[i1][j1] = this.matrix[i2][j2];
      this.matrix[i2][j2] = temp;
    },
    play() {
      const { matrix } = this;
      const visited = matrix.map(row => row.map(() => false));
      
      for (let row = 0; row < matrix.length; row++) {
        for (let col = 0; col < matrix[0].length; col++) {
          if (!visited[row][col]) {
            const queue = [];
            const value = matrix[row][col];
            
            remove(matrix, visited, row, col, value, queue);
            
            if (queue.length > 1) {
              for (const { row, col } of queue) {
                matrix[row][col] = null;
              }
            }
          }
        }
      }
      
      for (let col = 0; col < matrix[0].length; col++) {
        const stack = [];
        
        for (let row = matrix.length - 1; row >= 0; row--) {
          if (matrix[row][col] !== null) {
            stack.push(matrix[row][col]);
          }
        }
        
        for (let row = matrix.length - 1; row >= 0; row--) {
          if (stack.length > 0) {
            matrix[row][col] = stack.pop();
          } else {
            matrix[row][col] = null;
          }
        }
      }
    }
  }
};

function remove(matrix, visited, row, col, value, queue) {
  if (
    row < 0 ||
    row >= matrix.length ||
    col < 0 ||
    col >= matrix[0].length ||
    visited[row][col] ||
    matrix[row][col] !== value
  ) {
    return;
  }
  
  visited[row][col] = true;
  queue.push({ row, col });
  
  remove(matrix, visited, row - 1, col, value, queue); // 上
  remove(matrix, visited, row + 1, col, value, queue); // 下
  remove(matrix, visited, row, col - 1, value, queue); // 左
  remove(matrix, visited, row, col + 1, value, queue); // 右
}
</script>

<style>
.row {
  display: flex;
}

.block {
  width: 50px;
  height: 50px;
  margin: 5px;
  cursor: pointer;
}

.selected {
  border: 2px solid #000;
}
</style>