从梦幻西游学会广度优先搜索和A*算法

前言

前面介绍了一期pixi的入门，本期主要是补充一下自动寻路的知识，这次不会介绍太多pixi，感兴趣的可以看一下从英雄联盟来学pixi.js，这次主要是通过梦幻西游的案例来学习A* 算法。加上这篇的话，有2篇写了游戏了，其实我并不是做游戏的，也一点都不专业，大多数时候是在写大屏项目，只是觉得通过这样的案例学起来更有动力，程序员这个行业内卷真的挺厉害的，动不动就是框架原理，着实劝退不少人，我写文章的目的其实就跟我的名称一样，趣编程，希望能保持好初心，若干年后年纪大了，还搬好每一块砖，也能给阅读文章的你感受到乐趣。好了不废话了，进入今天的主题, 实现一下梦幻西游里的自动寻路。假设蓝色区域是不可走，点击地图位置，人物会避障绕行(效果)。

构造一个梦幻西游

如果你是被标题吸引新来的，那我相信你曾经跟我一样是一位梦幻西游的玩家吧。80、90后几乎都一大半的网民都接触过这款游戏，尽管很久很久以前我们就脱坑了， 但似乎时至今日，梦幻西游仍旧是网易最吸金的游戏。
因为最近有写到promise的递归，这次又在这个案例里练习实现了一下导致连续点击的画会有问题，感兴趣的朋友可以用requestAnimationFrame和tween改写一下人物移动动画，目前请忽略这个小问题。

1. 编写人物

import { AnimatedSprite } from 'pixi.js'
export class Player extends AnimatedSprite{
  
  constructor(textures) {
    super(textures)
    this.anchor.set(0.5, 0.85)
    this.position.set(250, 250)
    this.animationSpeed = 0.1
    this.play()
  }
}

2. 建立场景

import { Sprite } from 'pixi.js'
import { appFactory } from './app'
import { IMAGES, MAP_OBSTACLES } from './config.js''
import { Player } from './player'
const app = appFactory()
app.loader.add(IMAGES).load(setup)
let jianxiake

function setup() {
  initScene()
}

function initScene() {
  const mapTexture = app.loader.resources['background'].texture
  const map = new Sprite(mapTexture)
  app.stage.addChild(map)

  jianxiake = new Player(
    [ 
      app.loader.resources['player1'].texture,
      app.loader.resources['player2'].texture,
      app.loader.resources['player3'].texture,
      app.loader.resources['player4'].texture,
      app.loader.resources['player5'].texture
    ]
  )  
  app.stage.addChild(jianxiake)
  app.stage.interactive = true

}

至此，剑侠客已经出了建业城，在东海湾与大海龟一战了。

深度优先搜索 (DFS) && 广度优先搜索 (BFS)

深度优先搜索和广度优先搜索一般是在树或者图之类的数据结构中做遍历使用。
先假设我们有一棵树:

const tree = {
    val: 'A',
    children: [
        {
            val: 'B',
            children: [
                {
                    val: 'D',
                    children: [],
                },
                {
                    val: 'E',
                    children: [],
                }
            ],
        },
        {
            val: 'C',
            children: [
                {
                    val: 'F',
                    children: [],
                },
                {
                    val: 'G',
                    children: [],
                }
            ],
        }
    ],
};

深度优先搜索

先看一下网上的定义：
深度优先搜索(Depth-First-Search，DFS)，是一种用于遍历搜索树或图的算法。这个算法会尽可能深的搜索树的分支。我们一般使用堆数据结构来辅助实现 DFS 算法。

1. 访问顶点 v
2. 依次从 v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和 v 有路径相通的顶点都被访问
3. 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止

动手实现一下

const dfs = (root) => {
    console.log(root.val);
    root.children.forEach(dfs);
};

dfs(tree);
// 输出 ABDECFG

广度优先搜索

还是先看一下网上的定义： 广度优先搜索（Breadth-First-Search, BFS）,是一种图形搜索算法。根据它的特点，我们一般使用队列来辅助实现 BFS 算法。

1. 将根节点放入队列中
2. 从队列中取出第一个节点，并检验它是否为目标。如果找到目标则返回搜索结果。否则将它所有尚未检验过的直接子节点加入到队列中
3. 若队列为空，则返回
4. 重复步骤 2

动手实现一下

const bfs = (root) => {
    const q = [root];
    while (q.length > 0) {
        const n = q.shift();
        console.log(n.val);
        n.children.forEach(child => {
            q.push(child);
        });
    }
};
bfs(tree);
// 输出 ABCDEFG

寻路算法

最常见的寻路算法叫A*。这是基于广度优先搜索之上优化实现的。

1. 首先解释一下为什么是广度优先遍历，而不是深度优先遍历。 有那么一句歌词叫做，可能我偏要一路走到黑吧，说的就是深度优先搜索，深度优先搜索是一直搜索到树或图的最底层，用在寻路上也就是一条路要尝试走到尽头，实属下策，下等马莫得上位。
2. A* 在广度优先搜索上加上了什么? 其实就是取出了距离目标最近的点位。大概就是本来没有方向感，突然闻到了香味，就寻觅到了食堂。

A* 的步骤：
假设起点a，终点b
首先，将 a 节点放入队列中 取出 a 节点，a 不是目标节点，则将 a 的"子节点" "上" "下" "左" "右" (如果还有其他方向也加入，在本案例中有8个方向)分别放入队列中 取出某一节点，该节点为离 b 最近的节点。重复上述步骤,直到找到目标点位b。

动手实现梦幻西游里的A*

1. 构造地图

export const WIDTH = 500
export const HEIGHT = 500
export const CELLS_IZE = 5
export const MAP_WIDTH = WIDTH / CELLS_IZE
export const MAP_HEIGHT = HEIGHT / CELLS_IZE

// 假定50 50 到 60  70有障碍
const MAP_OBSTACLES = new Array(MAP_WIDTH * MAP_HEIGHT).fill(0)
for(let x = 50; x < 60; x++) {
  for(let y = 50; y < 70; y++) {
    MAP_OBSTACLES[x + y * MAP_WIDTH]  = 1
  }
}

实现一个100✖100的数组来表示地图，并且在[50,50] - [60, 70]设置障碍物。 2. 创建一个guide类，帮助人物引导路径

export class MapGuide{
  mapObstacles
  target = [0,0]
  guide = false
  constructor(mapObstacles, player, container) {
    this.mapObstacles = mapObstacles
    this.player = player
    this.container = container
  }
  bindPlayer(player) {
    this.player = player
  }
 }

3. 给人物绑定guide类，和鼠标事件

  mapGuide = new MapGuide(MAP_OBSTACLES, jianxiake, app.stage)
  mapGuide.drawObstacles()
  app.stage.addChild(jianxiake)
  app.stage.interactive = true
  app.stage.on('click', e => {
    const { x ,y } = e.data.global
    mapGuide.pathTo({x,y})
  })

4. guide的pathTo实现

  pathTo(to) {
    const that = this
    const path = this.findPath(to)
    if (!path) return
    return new Promise((resolve, reject) => {
      const index = path.length -1
      playerStep(index)
      function playerStep(index) {
        that.player.goto(path[index][0] * CELLS_IZE, path[index][1] * CELLS_IZE ).then(() => {
          if (index <= 0) {
            resolve()
          } else {
            playerStep(index -1)
          }
        }).catch((e)=> {
          console.log(e)
          reject()
        })
      }
    })
  }

调用findPath得到路径，递归
5. 创建一个优先级队列

export class PriorityQueue{
  items = []
  constructor(compare) {
    if (!compare) {
      this.compare = (a, b) => { return a - b }
    } else {
      this.compare = compare
    }
  }
  enqueue(item) {
    this.items.push(item)
  }
  dequeue() {
    if (!this.items.length) return
    let minIndex = 0
    for(let i = 1; i < this.items.length; i++) {
      if (this.compare(this.items[i], this.items[minIndex]) < 0) {
        minIndex = i
      }
    }
    // 最小项出队列
    const min = this.items[minIndex]
    this.items[minIndex] = this.items[this.items.length -1]
    this.items.pop()
    return min
  }

  get length() {
    return this.items.length
  }

}

6. findPath实现

findPath(to) {
    let map =  [].concat(this.mapObstacles)
    let from = {
      x: this.player.x / CELLS_IZE,
      y: this.player.y / CELLS_IZE
    }
    this.target[0] = parseInt(to.x / CELLS_IZE)
    this.target[1] = parseInt(to.y / CELLS_IZE)
    if (this.mapObstacles[this.target[0] + this.target[1] * MAP_WIDTH]) {
      return
    }
    console.log(`从(${from.x}，${from.y})移动到${this.target[0]}，${this.target[1]})移动到`)
    const queue = new PriorityQueue(this.distance.bind(this))
    queue.enqueue([from.x, from.y])
    function tryGo(x, y, pre) {
      // 边界判断
      if(x < 0 || x>= MAP_WIDTH || y < 0 || y >= MAP_HEIGHT) return
      // 地图障碍
      if(map[x + y * MAP_WIDTH]) return
      // 存储上一步位置
      map[x + y * MAP_WIDTH] = pre
      // 如果该点位可以正常行走，入栈
      queue.enqueue([x, y])
    }
    while(queue.length) {
      let [x, y] = queue.dequeue()
      if (x === this.target[0] && y === this.target[1]) {
        console.log('找到路了')
        // 找到路线 倒序回去
        let finalPath = [];
        while(x!= from.x || y!= from.y) {
          finalPath.push(map[x + MAP_WIDTH * y])
          let oX = x
          let oY = y
          x = map[oX + MAP_WIDTH * oY][0]
          y = map[oX + MAP_WIDTH * oY][1]
        }
        return finalPath
      }
      const direction =  [
        [1, 0], [0, 1], [-1, 0], [0, -1], // 四个正方向
        [1, 1], [-1, 1], [1, -1], [-1, -1] // 四个斜角方向
      ]
      direction.forEach(dir => {
        tryGo(x + dir[0], y + dir[1], [x, y])
      })
    }
    return 
  }
  
  distance(point1, point2) {
    // 求出和终点距离较近的点位
    const dis1 = Math.pow(point1[0] - this.target[0], 2) + Math.pow(point1[1] - this.target[1], 2)
    const dis2 = Math.pow(point2[0] - this.target[0], 2) + Math.pow(point2[1] - this.target[1], 2)
    return dis1 - dis2
  }

这是A* 具体的代码实现， 用力上面写好的PriorityQueue优先级队列，朝着上下左右以及四个斜角方向出发，寻找目标的，distance函数求出距离目标的最近的位置，让距离目标点位最近的一个点优先出栈，也就是优先尝试走距离目标点最近的位置。如图所示，第一步尝试向12345678个方向走出第一步，由于1点距离目标最近，下一次优先尝试用1去寻找目标点位。

最后得到所有的点位，逆向输出。

游戏也是核心资产？

玩梦幻西游是小学的时候了，多年未曾在与之接触。之所以想到写这篇文章，是因为前段时间在抖音上看见了一个新闻视频，一个无级别的破血鞋子居然卖出了700万人民币的天价，抖音上说的是不是真的，我也不清楚，但我看了一下，确实有上百万的装备存在。2020是一个特别的年份，由于疫情、美国大放水等原因，通货膨胀得厉害，似乎周围的人都在买基金、学区房，拥抱核心资产来对抗通货膨胀。但你可能想不到，游戏居然也能对抗通货膨胀，当年我玩梦幻西游的时候130无级别限制的装备似乎是一两万还没什么人敢买，现在居然好几十万，还不好买到，有的甚至高达百万。这是我看到抖音的新闻时候我才到的意识，多么不可思议啊，颠覆了我的认知，原来游戏的核心资产也是价值投资。回报率丝毫不逊色茅台。在这场对抗通货膨胀的战斗中居然是比特币、游戏等虚拟资产站在顶端。直至现在我也很难接受这样的现实，我只会老实写代码打工，这大概就是我是一个穷人的原因吧，嗯嗯，打工才人上人。

最后

小时候玩梦幻西游我也曾梦想仗剑走天涯，如今只与代码共春秋。尽管多数文章都是面经八股文很无聊，但我依然相信分享技术应该是一件有趣的事情，我也正在尝试分享我写代码的乐趣。本期代码地址，我是阿隆，我们下期见。