從夢幻西游學會廣度優(yōu)先搜索和A*算法
轉(zhuǎn)載自：阿隆_趣編程
https://juejin.cn/post/6945963711580340232
前言
這次主要是通過夢幻西游的案例來學習A* 算法以及鞏固pixi,沒學過pixi的可以看一下從英雄聯(lián)盟來學pixi.js：https://juejin.cn/post/6937862827499749406, 加上這篇的話，有2篇寫了游戲了，其實我并不是做游戲的，也一點都不專業(yè)，大多數(shù)時候是在寫大屏項目，只是覺得通過這樣的案例學起來更有動力，程序員這個行業(yè)內(nèi)卷真的挺厲害的，動不動就是框架原理，著實勸退不少人，我寫文章的目的其實就跟我的名稱一樣，趣編程，希望能保持好初心，若干年后年紀大了，還搬好每一塊磚，也能給閱讀文章的你感受到樂趣。好了不廢話了，進入今天的主題, 實現(xiàn)一下夢幻西游里的自動尋路。假設(shè)藍色區(qū)域是不可走，點擊地圖位置，人物會避障繞行(效果)。
構(gòu)造一個夢幻西游
因為最近有寫到promise的遞歸，這次又在這個案例里練習實現(xiàn)了一下導(dǎo)致連續(xù)點擊的畫會有問題，感興趣的朋友可以用requestAnimationFrame和tween改寫一下人物移動動畫，目前請忽略這個小問題。
編寫人物
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()
}
}
復(fù)制代碼
建立場景
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
}
復(fù)制代碼
至此，劍俠客已經(jīng)出了建業(yè)城，在東海灣與大海龜一戰(zhàn)了。
深度優(yōu)先搜索 (DFS) && 廣度優(yōu)先搜索 (BFS)
深度優(yōu)先搜索和廣度優(yōu)先搜索一般是在樹或者圖之類的數(shù)據(jù)結(jié)構(gòu)中做遍歷使用。
先假設(shè)我們有一棵樹:
const tree = {
val: 'A',
children: [
{
val: 'B',
children: [
{
val: 'D',
children: [],
},
{
val: 'E',
children: [],
}
],
},
{
val: 'C',
children: [
{
val: 'F',
children: [],
},
{
val: 'G',
children: [],
}
],
}
],
};
復(fù)制代碼
深度優(yōu)先搜索
先看一下網(wǎng)上的定義：
深度優(yōu)先搜索(Depth-First-Search，DFS)，是一種用于遍歷搜索樹或圖的算法。這個算法會盡可能深的搜索樹的分支。我們一般使用堆數(shù)據(jù)結(jié)構(gòu)來輔助實現(xiàn) DFS 算法。
訪問頂點 v 依次從 v 的未被訪問的鄰接點出發(fā)，對圖進行深度優(yōu)先遍歷；直至圖中和 v 有路徑相通的頂點都被訪問 若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發(fā)，重新進行深度優(yōu)先遍歷，直到圖中所有頂點均被訪問過為止
動手實現(xiàn)一下
const dfs = (root) => {
console.log(root.val);
root.children.forEach(dfs);
};
dfs(tree);
// 輸出 ABDECFG
復(fù)制代碼
廣度優(yōu)先搜索
還是先看一下網(wǎng)上的定義：廣度優(yōu)先搜索（Breadth-First-Search, BFS）,是一種圖形搜索算法。根據(jù)它的特點，我們一般使用隊列來輔助實現(xiàn) BFS 算法。
將根節(jié)點放入隊列中 從隊列中取出第一個節(jié)點，并檢驗它是否為目標。如果找到目標則返回搜索結(jié)果。否則將它所有尚未檢驗過的直接子節(jié)點加入到隊列中 若隊列為空，則返回 重復(fù)步驟 2
動手實現(xiàn)一下
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
復(fù)制代碼
尋路算法
最常見的尋路算法叫A*。這是基于廣度優(yōu)先搜索之上優(yōu)化實現(xiàn)的。
首先解釋一下為什么是廣度優(yōu)先遍歷，而不是深度優(yōu)先遍歷。有那么一句歌詞叫做，可能我偏要一路走到黑吧，說的就是深度優(yōu)先搜索，深度優(yōu)先搜索是一直搜索到樹或圖的最底層，用在尋路上也就是一條路要嘗試走到盡頭，實屬下策，下等馬莫得上位。 A* 在廣度優(yōu)先搜索上加上了什么? 其實就是取出了距離目標最近的點位。大概就是本來沒有方向感，突然聞到了香味，就尋覓到了食堂。
A* 的步驟：
假設(shè)起點a，終點b
首先，將 a 節(jié)點放入隊列中 取出 a 節(jié)點，a 不是目標節(jié)點，則將 a 的"子節(jié)點" "上" "下" "左" "右" (如果還有其他方向也加入，在本案例中有8個方向)分別放入隊列中 取出某一節(jié)點，該節(jié)點為離 b 最近的節(jié)點。重復(fù)上述步驟,直到找到目標點位b。
動手實現(xiàn)夢幻西游里的A*
構(gòu)造地圖
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
}
}
復(fù)制代碼
實現(xiàn)一個100?100的數(shù)組來表示地圖，并且在[50,50] - [60, 70]設(shè)置障礙物。2. 創(chuàng)建一個guide類，幫助人物引導(dǎo)路徑
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
}
}
復(fù)制代碼
給人物綁定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})
})
復(fù)制代碼
guide的pathTo實現(xiàn)
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()
})
}
})
}
復(fù)制代碼
調(diào)用findPath得到路徑，遞歸
5. 創(chuàng)建一個優(yōu)先級隊列
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
}
}
復(fù)制代碼
findPath實現(xiàn)
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
}
復(fù)制代碼
這是A* 具體的代碼實現(xiàn)， 用力上面寫好的PriorityQueue優(yōu)先級隊列，朝著上下左右以及四個斜角方向出發(fā)，尋找目標的，distance函數(shù)求出距離目標的最近的位置，讓距離目標點位最近的一個點優(yōu)先出棧，也就是優(yōu)先嘗試走距離目標點最近的位置。如圖所示，第一步嘗試向12345678個方向走出第一步，由于1點距離目標最近，下一次優(yōu)先嘗試用1去尋找目標點位。
最后得到所有的點位，逆向輸出。
游戲也是核心資產(chǎn)？
玩夢幻西游是小學的時候了，多年未曾在與之接觸。之所以想到寫這篇文章，是因為前段時間在抖音上看見了一個新聞視頻，一個無級別的破血鞋子居然賣出了700萬人民幣的天價，抖音上說的是不是真的，我也不清楚，但我看了一下，確實有上百萬的裝備存在。2020是一個特別的年份，由于疫情、美國大放水等原因，通貨膨脹得厲害，似乎周圍的人都在買基金、學區(qū)房，擁抱核心資產(chǎn)來對抗通貨膨脹。但你可能想不到，游戲居然也能對抗通貨膨脹，當年我玩夢幻西游的時候130無級別限制的裝備似乎是一兩萬還沒什么人敢買，現(xiàn)在居然好幾十萬，還不好買到，有的甚至高達百萬。這是我看到抖音的新聞時候我才到的意識，多么不可思議啊，顛覆了我的認知，原來游戲的核心資產(chǎn)也是價值投資?；貓舐式z毫不遜色茅臺。在這場對抗通貨膨脹的戰(zhàn)斗中居然是比特幣、游戲等虛擬資產(chǎn)站在頂端。直至現(xiàn)在我也很難接受這樣的現(xiàn)實，我只會老實寫代碼打工，這大概就是我是一個窮人的原因吧，嗯嗯，打工才人上人。
最后
小時候玩夢幻西游我也曾夢想仗劍走天涯，如今只與代碼共春秋。盡管多數(shù)文章都是面經(jīng)八股文很無聊，但我依然相信分享技術(shù)應(yīng)該是一件有趣的事情，我也正在嘗試分享我寫代碼的樂趣。本期代碼地址:https://github.com/betteralong/visual-example/tree/main/dream-swims，我是阿隆，我們下期見。