A further enhancement of jump point search algorithm applied in beaware: a 3D role playing game 6
6
Miana, Erlyn Joy I. and Pabustan, Charina R.
-
-
- 142 pp. 28 cm.
-
-
-
-
- .
- .
- 0 .
- .
- 0 .
Thesis: (BSCS major in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2016.
5
ABSTRACT: Jump Point Search is an optimization to the A* search algorithm pathfinding algorithm for uniform-cost grids. It reduces symmetries in the search procedure by means of graph pruning, eliminating certain node's neighbors, as long as certain conditions relating to the grid are satisfied. It preserves A*'s optimality, while potentially reducing its running time by an order of magnitude. The researchers seek thoroughly each and every process of the algorithm and how they work. First, the algorithm will identify successors by pruning all the neighbors of the current node. In pruning function, the algorithm will compute for the fcost (which is the current estimated shortest path) by adding the gcost (total distance it has taken to get from the starting position to the current location) and the hcost (estimated distance from the current position to the goal destination). Second, if all neighbors were already pruned, the algorithm will jump to a node that has the smallest fcost. Third, if there is any jump point successor, step in that direction. If the neighboring node is an obstacle, return null to the set of successors. If the neighboring node is closer to the goal, add that to the set of successors. If the direction is diagonal and it is not a straight jump point, add that to the set of successors. If the neighbour is not a jump point, recurse again and step in the diagonal direction. Then repeat the process. There are three problems that the researchers encounter during the study. First is that the Jump Point Search Algorithm manipulates and search nodes at a single time. Computing and analyzing each node is a waste of time. The algorithm spends a lot of time computing for the fcost of each node. Researchers aim to reduce the time that the algorithm spends on computing for the fcost of the nodes by making the computation per block node. The algorithm will already compute for the fcost of the block nodes if the nodes are in the same direction. In this way, we will reduce the time that the algorithm spends in computing the fcost. Second problem is that there are unnecessary jump points expanded such as intermediary jump points. Intermediary jump points are nodes that are not not a jump point but still, the algorithm considers it and compute for its fcost. The goal is to eliminate the computation for the fcost of that intermediary jump point but removing the process of it in the algorithm. Last is that the algorithm doesn't support hexagonal type of grids. Jump point search algorithm is only applicable in a square type of grid. The researchers found out that this algorithm could also be applicable to hexagonal type of grid. To make this possible, the researchers analyse the code of generating the square grid and transforms it to hexagonal grid by adding the third coordinate which points out to be the two sides of the square, so adding another coordinate would make it look like a hexagonal grid which happens to have three identical sides. As a result, the enhanced algorithm algorithm is much faster to compute for the fcost than the existing algorithm so the speed of finding path is faster. The second solution also affects the speed of the algorithm because there is no more computation for the intermediary nodes. And last but not the least, the algorithm can now be applied in a hexagonal type of grid which is more convenient in finding the shortest path. This study is recommended for those programmers who will try to make a pathfinding game. This newly improved algorithm will help a lot on games especially if it is a RPG game. Also, for the gamers who love playing RPG game because this algorithm will surely be the fastest when it comes in pathfinding.