消灭星星类游戏核心算法

xmxx-algorithm.js

const GAME_CONSTS = {
  BOARD_WIDTH: 10,
  BOARD_HEIGHT: 10,
  STAR_COLOR_CODE_START: 1,
  STAR_COLOR_CODE_END: 4,
  scoreCounter (starNum) {
    return starNum * starNum * 5
  },
  remainScoreCounter (remainNum) {
    return remainNum * 20
  },
  LEVEL_GAP: 5,
  WIN_SCORE: 5000
}

class Board {
  constructor (unitsTemplate) {
    this.width = GAME_CONSTS.BOARD_WIDTH
    this.endColumn = this.width - 1
    this.height = GAME_CONSTS.BOARD_HEIGHT
    this.units = []
    if (unitsTemplate) {
      for (let xUnits of unitsTemplate) {
        this.units.push(xUnits.concat())
      }
    } else {
      /**
       * 坐标系（和客户端保持一致）
       *       |
       * -----------> y
       *       |ooooo...
       *       |ooooo...
       *     x v
       */
      for (let x = 0; x < this.height; x++) {
        this.units[x] = []
        for (let y = 0; y < this.width; y++) {
          this.units[x][y] = GAME_CONSTS.STAR_COLOR_CODE_START + Math.round(Math.random() * (GAME_CONSTS.STAR_COLOR_CODE_END - GAME_CONSTS.STAR_COLOR_CODE_START))
        }
      }
    }

    /**
     * 连接性递归算法中间值的存储区
     * 使用一维指代二维
     * a = 100y + x
     */
    this.linkedStarsFlatten = []
    /**
     * {
     *  <y>: {
     *    maxX: <x>,
     *    minX: <x>,
     *    nums: Number,
     *    isEmpty: Boolean,
     *    xList: [<x1>, <x2>...],
     *  }
     * }
     */
    this.clearListMetaRecords = {}
  }

  /**
   * 给玩家的消除提示
   * （从 Board 左下角开始扫描）
   */
  findHint () {
    if (this.units[this.height - 1][0] === 0) {
      return [] // 面板上的星星已被全部被消除
    }
    let luckyStar = null
    let x = this.height - 1
    let y = 0
    // 从左到右，从下到上扫描
    while (this.units[this.height - 1][y]) {
      while (this.units[x] && this.units[x][y]) {
        let pos = {x, y}
        if (this._checkIsStarLucky(pos)) {
          luckyStar = pos
          break
        }
        x--
      }
      if (luckyStar) {
        break
      }
      y++
      x = this.height - 1
    }
    if (luckyStar) {
      this.linkedStarsFlatten.push(100 * luckyStar.x + luckyStar.y)
      this.scanLinkedStars(luckyStar)
      return this.linkedStarsPosReverseFlatten()
    } else {
      return []
    }
  }

  _checkIsStarLucky (pos) {
    return (this.units[pos.x - 1] && this.units[pos.x - 1][pos.y] &&
      this.units[pos.x - 1][pos.y] === this.units[pos.x][pos.y]) ||
      (this.units[pos.x][pos.y + 1] &&
        this.units[pos.x][pos.y + 1] === this.units[pos.x][pos.y]) ||
      (this.units[pos.x + 1] && this.units[pos.x + 1][pos.y] &&
        this.units[pos.x + 1][pos.y] === this.units[pos.x][pos.y]) ||
      (this.units[pos.x][pos.y - 1] &&
        this.units[pos.x][pos.y - 1] === this.units[pos.x][pos.y])
  }

  scanLinkedStars (pos) {
    if (this.units[pos.x - 1] && this.units[pos.x - 1][pos.y] &&
      this.units[pos.x - 1][pos.y] === this.units[pos.x][pos.y] &&
      this.linkedStarsFlatten.indexOf(100 * (pos.x - 1) + pos.y) === -1) {
      this.linkedStarsFlatten.push(100 * (pos.x - 1) + pos.y)
      this.scanLinkedStars({
        x: pos.x - 1,
        y: pos.y
      })
    }
    if (this.units[pos.x] && this.units[pos.x][pos.y + 1] &&
      this.units[pos.x][pos.y + 1] === this.units[pos.x][pos.y] &&
      this.linkedStarsFlatten.indexOf(100 * pos.x + pos.y + 1) === -1) {
      this.linkedStarsFlatten.push(100 * pos.x + pos.y + 1)
      this.scanLinkedStars({
        x: pos.x,
        y: pos.y + 1
      })
    }
    if (this.units[pos.x + 1] && this.units[pos.x + 1][pos.y] &&
      this.units[pos.x + 1][pos.y] === this.units[pos.x][pos.y] &&
      this.linkedStarsFlatten.indexOf(100 * (pos.x + 1) + pos.y) === -1) {
      this.linkedStarsFlatten.push(100 * (pos.x + 1) + pos.y)
      this.scanLinkedStars({
        x: pos.x + 1,
        y: pos.y
      })
    }
    if (this.units[pos.x] && this.units[pos.x][pos.y - 1] &&
      this.units[pos.x][pos.y - 1] === this.units[pos.x][pos.y] &&
      this.linkedStarsFlatten.indexOf(100 * pos.x + pos.y - 1) === -1) {
      this.linkedStarsFlatten.push(100 * pos.x + pos.y - 1)
      this.scanLinkedStars({
        x: pos.x,
        y: pos.y - 1
      })
    }
  }

  linkedStarsPosReverseFlatten () {
    let linkedStarsPosReverseFlatten = []
    for (let flattenPos of this.linkedStarsFlatten) {
      let x = Math.floor(flattenPos / 100)
      let y = flattenPos % 100
      linkedStarsPosReverseFlatten.push({
        x,
        y,
        color: this.units[x][y]
      })
    }
    this.linkedStarsFlatten = [] // 重置
    return linkedStarsPosReverseFlatten
  }

  findLinkedStars (startPos) {
    if (!startPos) {
      return []
    }
    if (this._checkIsStarLucky(startPos)) {
      this.linkedStarsFlatten.push(100 * startPos.x + startPos.y)
      this.scanLinkedStars(startPos)
      return this.linkedStarsPosReverseFlatten()
    } else {
      return []
    }
  }

  /**
   * 消除星星
   * @param posList 坐标列表，一般由 this.linkedStarsPosReverseFlatten 获得
   */
  clearLinkedStars (posList) {
    if (posList.length <= 1) {
      return
    }
    for (let pos of posList) {
      if (!this.clearListMetaRecords[pos.y]) {
        this.clearListMetaRecords[pos.y] = {
          maxX: 0,
          minX: this.height - 1,
          nums: 0,
          xList: []
        }
      }
      let clearListMetaRecord = this.clearListMetaRecords[pos.y]
      if (pos.x > clearListMetaRecord.maxX) {
        clearListMetaRecord.maxX = pos.x
      }
      if (pos.x < clearListMetaRecord.minX) {
        clearListMetaRecord.minX = pos.x
      }
      clearListMetaRecord.nums++
      clearListMetaRecord.xList.push(pos.x)

      this.units[pos.x][pos.y] = 0
    }
  }

  drop () {
    let clearListMetaRecords = this.clearListMetaRecords
    let dropMetaRecords = []
    let emptyMetaRecords = []
    for (let y in clearListMetaRecords) {
      y = Number(y)
      if (clearListMetaRecords.hasOwnProperty(y)) {
        let clearListMetaRecord = clearListMetaRecords[y]
        // xList 从下往上（x 从大到小）排序
        clearListMetaRecord.xList.sort((a, b) => { return b - a })

        let continuous = true
        let continuousZero = 0
        // 从下往上逐个夯实
        for (let x = clearListMetaRecord.maxX; x >= 0; x--) {
          if (!this.units[x][y]) {
            if (continuous) {
              continuousZero++
            }
            continue
          }
          continuous && (continuous = false)
          /**
           * 小于 minX 则不需要遍历 xList
           * 直接得出降落的个数
           */
          if (x < clearListMetaRecord.minX) {
            let color = this.units[x][y]
            this.units[x][y] = 0
            this.units[x + clearListMetaRecord.nums][y] = color
            continue
          }
          let dropNum = 0
          for (let cx of clearListMetaRecord.xList) {
            if (x < cx) {
              dropNum++
            } else {
              break
            }
          }
          let color = this.units[x][y]
          this.units[x][y] = 0
          this.units[x + dropNum][y] = color
        }

        // 记录夯实（drop）过程中的元信息
        if (continuousZero < this.height) {
          dropMetaRecords.push({
            y,
            'start_x': clearListMetaRecord.maxX - continuousZero,
            'end_x': clearListMetaRecord.maxX
          })
        }
        if (this.units[this.height - 1][y] === 0) {
          emptyMetaRecords.push(y)
        }
      }
    }

    let len = emptyMetaRecords.length
    if (len) {
      if (len > 1) {
        emptyMetaRecords.sort((a, b) => { return a - b })
      }
      for (let index of emptyMetaRecords.keys()) {
        let columnStart = emptyMetaRecords[index]
        let columnEnd = emptyMetaRecords[index + 1] || (this.endColumn + 1)
        let moveColumnNum = index + 1
        for (let i = columnStart + 1; i < columnEnd; i++) {
          let y = i
          let x = this.height - 1
          while (this.units[x] && this.units[x][y]) {
            let color = this.units[x][y]
            this.units[x][y] = 0
            this.units[x][y - moveColumnNum] = color
            x--
          }
        }
      }
    }

    this.endColumn -= emptyMetaRecords.length
    this.clearListMetaRecords = {} // 重置

    return {
      clearListMetaRecords,
      emptyMetaRecords,
      dropMetaRecords
    }
  }

  countRemainStars () {
    console.log('==========================')
    console.log(this.units)
    let remainCount = 0
    for (let xUnits of this.units) {
      for (let y of xUnits) {
        if (y) {
          remainCount++
        }
      }
    }
    return remainCount
  }
}

Board.clone = function (board) {
  return new Board(board.units)
}