Patent ID: 8257173

Claim:
A computer-implemented method of moving a computer animated character in a virtual environment, the method being implemented in a computer system comprising one or more processors configured to execute computer program modules, the method comprising: determining a goal location in a virtual environment for a non-player character to move toward from a first position of the non-player character within the virtual environment; evaluating the first position of the non-player character with respect to the goal location in a navigational graph of the virtual environment to determine at least one potential route through the virtual environment from the first position to the goal location, wherein the navigational graph includes a series of predefined paths between location nodes within the virtual environment, and wherein the one or more routes of the at least one potential routes are formed along the predefined paths in the navigational graph; selecting a route from the at least one potential route; and moving the non-player character toward the goal location, wherein the moving comprises moving the non-player character along the selected route, concurrent with movement by the non-player character along the selected route, searching for an alternate route to the goal location that are off the navigational graph, and responsive to finding an alternate route to the goal location, controlling the non-player character to move off of the selected route and onto the alternate route.