preface
This time, I will mainly learn A* algorithm and consolidate PIXI through the case of Dream Westward Journey. Those who have not learned PiXI can have A look to learn pixi.js from League of Legends. Plus this article, there are two articles about games. Just think through such AnLiXue up and motivated, programmers volume within the industry really is very bad, always is the frame principle, really making a lot of people, the purpose of my writing is just like my name, boring programming, hope to be able to maintain a good beginner’s mind, after some years old, had moved well each piece of brick, also can give you feel fun to read a text. Good no nonsense, into today’s theme, to achieve the dream of the journey to the West in the automatic path finding. Assuming the blue area is impassable, clicking on the map location will cause the character to avoid obstacles and go around.
Construct a dream westward journey
Because of the recursion that wrote the promise recently, this time I have implemented it again in this case, and there will be a problem with the drawing that causes continuous clicking. Interested friends can rewrite the character movement animation with requestAnimationFrame and tween, please ignore this minor problem for now.
- Write the characters
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()}}Copy the code- Establish scene
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
}
Copy the codeBy this point, the swordsman had left jianye City and was fighting the Turtle in the East Bay.
Depth First Search (DFS) && Breadth First Search (BFS)
Depth-first search and breadth-first search are typically used to traverse data structures such as trees or graphs. Suppose we have a tree:
const tree = {
val: 'A',
children: [
{
val: 'B',
children: [
{
val: 'D',
children: [],
},
{
val: 'E',
children: [],
}
],
},
{
val: 'C',
children: [
{
val: 'F',
children: [],
},
{
val: 'G',
children: [],
}
],
}
],
};
Copy the code
Depth-first search
Take a look at the online definition: depth-first-search (DFS), an algorithm used to traverse a Search tree or graph. The algorithm searches the branches of the tree as deep as possible. We generally use heap data structures to assist the IMPLEMENTATION of DFS algorithms.
- Access vertex V
- Starting from the unvisited adjacent points of V, the graph is traversed depth-first. Until all vertices in the graph that have a path to V are accessed
- If there are still vertices in the graph that have not been accessed, the depth-first traversal is performed again starting from an unvisited vertex until all vertices in the graph have been accessed
Let’s do it
const dfs = (root) => { console.log(root.val); root.children.forEach(dfs); }; dfs(tree); / / output ABDECFGCopy the codeBreadth-first search
Let’s take a look at the definition on the Internet: Broadway-first-search (BFS), which is a graphic Search algorithm. According to its characteristics, we generally use queues to assist the implementation of BFS algorithm.
- Put the root node into the queue
- Extract the first node from the queue and verify that it is the target. Search results are returned if the target is found. Otherwise, all of its immediate children that have not yet been verified are added to the queue
- Returns if the queue is empty
- Repeat Step 2
Let’s do it
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); / / output ABCDEFGCopy the codePathfinding algorithm
The most common pathfinding algorithm is called A*. This is optimized on top of breadth-first search.
- First, explain why breadth-first traversal is used instead of depth-first traversal. There’s a line called “Maybe I’m going to go all the way to the black,” which is depth-first search, and depth-first search is searching all the way to the bottom of the tree or graph, and when it’s used to find a path, it’s a bad idea to try to get to the end of a path.
- What does A* add to breadth-first search? You’re essentially taking the nearest point to the target. Probably had no sense of direction, suddenly smell the fragrance, looking for the canteen.
Steps of A* : Assuming the starting point a and the ending point B, first of all, put node A into the queue to take out node A, which is not the target node, then put the “child nodes”, “up”, “down”, “left” and “right” of A (there are 8 directions in this case if there are other directions added) into the queue to take out a node, This node is the nearest node to B. Repeat the above steps until the target point b is found.
Start to realize A* in the dream Journey to the West
- Tectonic map
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 // If 50 50 to 60 70 are obstructed const MAP_HEIGHT = 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 } }Copy the codeA 100 * 100 array represents the map and sets obstacles at [50,50] – [60, 70]. 2. Create a Guide class to help the character navigate
Export class MapGuide{constructor = false through obstacles = [0,0] container) { this.mapObstacles = mapObstacles this.player = player this.container = container } bindPlayer(player) { this.player = player } }Copy the code- Bind the guide class and mouse events to the character
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})
})
Copy the code- The pathTo implementation of Guide
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() }) } }) }Copy the codeCall findPath to get the path, recursively 5. Create a priority queue
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}} // Minimum items out of the queue 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 } }Copy the code- FindPath implementation
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.target[0] + this.target[1] * MAP_WIDTH]) {return} console.log(' from (${from. X}, ${this.target[0]}, ${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) {/ / boundary judgment if (x < 0 | | x > = MAP_WIDTH | | y < 0 | | y > = MAP_HEIGHT) obstacles if return / / map (map [x + y * MAP_WIDTH]) return [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(' found path ') // find path back 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], / / four positive direction [1, 1], [1, 1]. [1, 1], [1, 1]] / / four diagonal direction direction. The forEach (dir = > {tryGo (x + dir [0], y + dir [1], [x. Math.pow(point1[0] - this.target[0], const dis1 = math.pow (point1[0] - this.target[0], const dis1 = math.pow (point1[0] - this.target[0], const dis1 = math.pow (point1[0] - this.target[0], 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 }Copy the codeThis is the specific code implementation of A*, using the PriorityQueue written above, starting in the direction of up, down, left and right as well as four bevel angles, looking for the distance function of the target, finding the position nearest to the target, making the point nearest to the target priority off the stack. That is, first try to walk to the nearest point of the target. As shown in the figure, the first attempt is to take the first step in the direction of 12345678. Since 1 is the closest point to the target, the next attempt is first to find the target point with 1.
Is the game a core asset?
Play dream west tour is primary school time, many years have not been in contact with it. I came up with the idea of writing this article because I saw a news video on Douyin some time ago, in which a gradeless bloody shoe was sold for 7 million RMB. I am not sure whether what douyin said is true, but I have looked at it and found that there are literally millions of pieces of equipment. 2020 is a special year. Due to the epidemic and the flood of water in the United States, inflation has been severe. It seems that people around are buying funds and school district houses and embracing core assets to fight against inflation. But you may not think that the game can also fight against inflation. When I played fantasy Westward Journey, 130 equipment with no level limit seemed to be 10,000 or 20,000 and nobody dared to buy it, but now there are hundreds of thousands and it is not easy to buy, and some of them are even as high as one million. It was only when I saw the news of Douyin that I realized how incredible it was. It overturned my understanding that the core asset of the game is also value investment. The returns are as good as Moutai’s. Virtual assets such as bitcoin and games are at the top of the battle against inflation. Even now, IT’s hard for me to accept the reality that I can only write code for a job. That’s probably why I’m a poor man.
The last
When I was a child, I had a dream to travel with the sword, and now only code total spring and autumn. Although most of the articles are boring, I still believe that sharing technology should be fun, and I’m trying to share the fun OF writing code. I’m Aaron. I’ll see you next time.