If you've ever played an MMOARPG, such as Warcraft, you'll find that character walking can be fun, and in order to mimic the real-life experience of a character walking, they'll choose the closest route to reach their destination, during which time they'll avoid mountains or lakes, and go around chests or forests until they get to the destination you've chosen.
This kind of seemingly unusual path-finding in the program implementation will require a certain path-finding algorithm to solve, how to find a route with the shortest path in the shortest possible time, this is the path-finding algorithm to consider the problem in the first place.
In this article we'll take a step-by-step approach to explaining how pathfinding algorithms evolve, and you'll see the problems encountered as an algorithm goes from simple to efficient, as well as the process of refining it, so read with questions in mind for faster understanding.
This piece mainly contains the following.
1Figure.2and width-optimized search.3Dijkstra's algorithm.4and greedy algorithms.5、A*Search Algorithms, Search Algorithms6、B*Search Algorithms, Search Algorithms1. How the characters in the game are pathfinding
The way you see the characters walking: the
The way developers actually see it.
For a map, the developer needs to be converted into data objects through certain programs, the common is the above map cut into a grid, of course, the map does not have to be divided into a grid in this way, the use of polygons can also be used, depending on your game, in general, the same area of the map using fewer vertices, the pathfinding algorithm will be faster. A common data structure used in pathfinding is the graph, which we'll learn more about below.
2. Figures
Before we talk about the pathfinding algorithm, we first understand a data structure - graph, data structure is the basis of our algorithm, a good data structure in addition to facilitate our understanding of the algorithm, but also to improve the efficiency of the algorithm. Grid in a sense is also the evolution of the graph, only the graph has changed, understand the concept of the graph can help us better understand the pathfinding algorithm.
Basic Definition of Diagram.
The formal expression for the graph is G=(V,E), V is the set of vertices represented, E and V is a binary relationship, can be understood as an edge, for example, there is an edge from vertex U to the end of the vertex V, then E can be used (u,v) to represent this edge. Specific directed and undirected graphs are also distinguished by whether the edges have directions or not. In order to facilitate understanding, all the data demonstration in our text is based on the grid map to explain, the following is a few kinds of relationship comb, with A as the vertex, BCDE as the sub-vertex, we can see each grid is also a vertex.
3. Search algorithms
Searching a graph means accessing its vertices sequentially in a particular order. For multigraph algorithms, both breadth-first and depth-first search algorithms are important because they provide a systematic way to access graph data structures. We focus on breadth-first search algorithms.depth-first search
Depth-first search algorithm (DFS for short) is an algorithm for traversing or searching a tree or graph. The nodes of the tree are traversed along the depth of the tree, and branches of the tree are searched as deeply as possible. When the edges where node v is located have all been explored, the search goes back to the starting node of the edge where node v was found. This process continues until all nodes reachable from the source node have been discovered.breadth-first search algorithm
(BFS for short), also known as breadth-first search, is a graphical search algorithm that is well suited for exploring the first model of shortest paths, and we'll go along with that.
BFS is a blind search method that aims to systematically unfold and examine all nodes in the graph to find results. In other words.It does not consider the possibility of outcomesaddressesIf you are not satisfied with the results, search the whole map thoroughly until you find the result.It proceeds as follows.
- First put the root node in the queue. - Take the first node from the queue and check if it is the target. - If the target is found, end the search and return the result. - Otherwise put all its direct children nodes that have not yet been tested(Neighboring nodes)Add to the queue. - If the queue is empty, it means that the whole map has been checked - i.e. there are no targets to search for in the map. Ends the search and returns "no target found".
The code we see
var frontier = new Array();(start);var visited = new Array();visited[start] = true;while(frontier.length>0){ current = frontier.get(); //Find surrounding verticesfor(next in (current)){ var notInVisited = (next)==-1; //Not visitedif(notInVisited) { (next); visited[next] = true; } }}From the above, we can find that the width search is to start at the beginning vertex, visit its children nodes (in the mesh is to visit the surrounding nodes), and then keep looping the process until the target is found, this algorithm is more in line with the conventional logic of all the vertices all enumerated. However, this approach also has obvious drawbacks.
Defects.
1The time complexity is T(n).= O(n^2)2, there are no weights between each vertex to define the priority to find the optimal route. For example, when encountering a water area, you need to walk around it, which cannot be covered inside the width algorithm.