PathfinderInComputerGames
Hui Li
December 10, 2010
Overview
In this project my goal is creating a pathfinder in computer games to make it easier for characters in the games to get to wherever they want. In an actual map of a computer game, there would be not different paths to get to one place, but also different steps to take in one path or even more complex situations like in a 3D map where a path with the shortest direct distance is actual farther than another path. I mainly use A* search algorithm to avoid the characters running into some walls and barriers and finding the shortest path regarding 3D situations.
Screenshot
Concepts Demonstrated
A* search is used to find the shortest path from starting points to goal points in 2D or 3D maps.
Innovation
The project is innovative using A* search in both 2D and 3D conditions. To make the A* search algorithm work, the concept of a map has to be figured out in the first place. A map, no matter 2D or 3D, is build with many small cubes that are connected in certain principles and saved as map files. In this case, each cube can be regarded as a nod. As the character moves in the map, the map editor tests the cubes around the character to see if they are walls or paths, then calculate for the next step that the character should take. After that, A* search algorithm can work avoiding walls, finding possible paths and the shortest one from the starting point to the goal point.
Technology Used Block Diagram
Evaluation of Results
The project was successfully working on both 2D and 3D maps. Whether the map is 2D or 3D actually does not matter, as long as the nod taken each time has the smallest value of F(n) and the path is connected with all those nods, it is the shortest path for sure.
Additional Remarks
This project is kind of similar to the Pac-Man project, but is different in two aspects. One is that it applies to 3D maps and the other is that in Pac-Man project the size for every path is designed for exactly one Pac-man to pass through while in game maps most paths are much wider than a character is. However, there is also a problem. If the goal point is located in somewhere in the cubes that cannot path through or are actual barriers themselves, there would be an error.