Pathfinding is defined as a method to find the best possible shortest path, from a specific start node to a given goal node, in a graph or a map. The path finding concept has been the basis for a large number of games in the gaming world. The common algorithm that is used for path finding which produces the best results for a given heuristic is the A star algorithm. The most conventional search space used to implement this problem is the grid representation. However, this paper proposes a different approach by using geometric information in order to build the search space corresponding to an open terrain and also introducing new methods into the A star algorithm to optimize the solution.
This paper has been published by S.D.Goodwin, S.Menon, R.G.Price. Path finding is an essential concept that many game developers use as part of their projects. It is a problem of determining the shortest path between two( start and stop) given nodes. There are many approaches to finf the optimal path between two points, but, te most widely used algorithm is the A* algorithm. Consider a given heuristic, no algorithm This paper has been published by S.D.Goodwin, S.Menon, R.G.Price. Path finding is an essential concept that many game developers use as part of their projects. It is a problem of determining the shortest path between two( start and stop) given nodes. There are many approaches to finf the optimal path between two points, but, te most widely used algorithm is the A* algorithm. Consider a given heuristic, no algorithm can find a better solution than the A* algorithm. Yet, it imposes some major resource impact in terms of time and space. Numerous attempts to optimize this technique(A*) have been approached by users. The major components of the algorithm that are subjected to change are the heuristic cost funtion and the space representation. The heurictic cost function is the estimated distance of any particular node to the goal node in an area. This can be calculated by using various mathematical formulas such as Vancouver distance, Manhattan distance and teh Euclidean distance. The space representation is also a significant factor that contrubutes to the optimization of the alogirthm. Various space representations have been put to test such as the traditional grid representation, navigation mesh, waypoint graph, etc. Conventionally the underlying world has been modelled as a grid in the computer field, thereby associating each node of a grid to that of an input graph, further the graph is representing by applying suitable data structures according to the level of optimization, in the algorithm. Although this approach has been practiced globally for path finding implemntations, one cannot deny that the grid representation fails to import important spatial information thereby presenting just an approximation of an optimal solution. This diminshes the path accuracy majorly.
