This is part of the series by Cocos developer “Billion Dollar Programmer” on helping developers build their own games. We’ll be sharing his stories on the forum. You can read the originals from his website.
What is a map editor?
An in-game map editor is a game developer’s software tool to create, edit, and customize in-game maps or levels. A map editor allows the player or designer to customize the game map by adding, moving, adjusting, and deleting in-game elements, including terrain, buildings, paths, character generation points, enemy and item placement, and more.
What is the A-star algorithm?
A-star algorithm is a widely used path planning algorithm designed to find the shortest path between two nodes in a graph or network.
Principle of A-star algorithm
A-star algorithm is a heuristic search algorithm that combines the features of breadth-first search and best-first search. The core idea is to evaluate each possible path to find the best path from the starting point to the target node. In the A-star algorithm, each node has two key values:
G-value (cost): indicates the actual cost from the starting point to the current node, i.e., the path length traveled.
H-value (heuristic value): indicates the estimated cost from the current node to the goal node, i.e., how far it is expected to travel to reach the goal.
Steps of the A-star algorithm
A simple list of the steps of the A-star algorithm, you can write code according to the steps of the algorithm directly “translated” over the line:
- Create an open list and a closed list to store nodes to be explored and nodes already explored.
- Add the starting point to the open list and set its G-value to zero.
- Repeat the following steps until the target node is found or the open list is empty: a. Select the node with the smallest F-value from the open list (usually the node with the smallest H-value + G-value). b. Move that node from the open list to the closed list. c. Iterate through the neighboring nodes of that node, calculating their G-values and H-values. d. If the neighboring node isn’t in the open list, add it to the open list, and update its G-value and parent node. e. If the neighbor node is already in the open list, check if the current path is shorter and update the G-value and parent node if it is shorter.
- The search ends when the target node is found, or the open list is empty.
Advantages of A-star algorithm
Completeness: the A* algorithm can find the best path if a feasible solution exists.
Heuristic search: Using heuristic estimates, the A* algorithm can efficiently search large graphs and reduce the search space.
Adaptability: The A* algorithm can be customized to meet the needs of different problems and heuristic functions.
Widely used: The A* algorithm is widely used as it has a track record of successful applications in several fields.
A-star algorithm practice
- Open the project of the previous article
As shown below, the author has edited the blocking information of the whole map (red part). The blue origin is the starting position. The green one is the end position. The white one is the path point.
- Abstract data based on map information
Create a grid and mark blocking grids as non-walkable based on map information.
- Create the AStar class
Create an open list and a closed list for storing nodes to be explored. And add the starting point to the open set setting. The G value is set to 0.
- Retrieve the path
Repeat the following steps until the target node is found or the open list is empty: a. Select the node with the smallest F-value from the open list (usually the node with the smallest H-value + G-value). b. Move the node from the open list to the closed list. c. Iterate through the neighboring nodes of the node and compute their G-values and H-values. d. If the neighboring node is not in the open list, add it to the open list and update its G-value and parent node. e. If the neighbor node is already in the open list, check if the current path is shorter and update the G-value and parent node if it is shorter. f. If the neighbor node is not in the open list, add it to the open list Until the end point is reached retrieval ends.
- Building paths
Form the path by reversing the chain list.
- Write test code
Still, go through cc.Graphics to draw the start point, endpoint, path, and blocking.
The path is regenerated and redrawn after each click on the map.
- Presentation of results
Summary
The A-star algorithm is a powerful path-planning algorithm capable of finding the optimal path in game pathfinding by combining practical costs and heuristic estimation. It is simple but powerful and provides a powerful tool for solving many game navigation and planning problems.
Code Example: