Natural Path Finder: Natural and Intuitive Path Finding Method in Complex 3D Space by Analyzing Players' Movement History
In 3D games, a complex map in which players can move along various paths creates various strategies and thus is an important factor that increases the excitement of games. However, path finding algorithms that control the movement of an NPC (non-player character controlled by a computer) on the map extract the shortest path. Thus, when the map becomes more complex, the difference between a path of a character moved by a human, who does not always move along the shortest path, and the movement path of the NPC, which is controlled by an algorithm, becomes greater. Due to this action gap between humans and NPCs, the behavior of the NPCs looks unnatural and monotonous to human players. Thus, this invention accumulates the movement history of characters operated by players, and, with respect to a human movement path from a certain point A to another certain point B, by performing calculation using frequency values that appear in the history as weights, extracts a path that looks natural for the players and moves the NPC along this path. A technology feature of this invention is that it divides a path from a movement start point to a certain destination into a sequence of sub-destinations calculated from players' logs when an NPC is moved to the destination. In finding movement paths between these divided sub-destinations, a conventional shortest path finding algorithm is used. By doing so, this invention makes it possible to realize path finding that is appropriate for a game and that looks natural to humans by globally adopting a human movement path and locally applying a shortest path finding algorithm. As an application of this invention, it is possible to classify players into, for example, experts, intermediates, and novices, and to calculate the movement path frequency for each group, thereby controlling the skill level of the NPC in a pseudo-realistic fashion.
Full Text: Google Patents