Pathfinding & Navigation
Path Planning is core component in today's game. A magical profound system that makes computer-controlled characters move towards goals efficiently while avoiding obstacles and hazards.
Visit: http://jessicajosejohn.blogspot.com/ for more on the demo of path finding.
Navigation meshes are an efficient way of representing walkable regions in the game world. A collection of connected convex polygons. Each polygon is a node and each edge is shared by two polygons forming a solid connection between nodes.
Finding Path with AStar
Now that we can represent the search space - What's next? How will that help the NPC's to get where we want them to go? The answer is A* algorithm, one of the proficient way of getting a path between two points on a graph.
Understanding the theory of A* is only half the battle. How do we build a good navigation system around it? What do we need to watch out for to make sure the pathfinding behavior still remains robust? Which are the biggest obstacles to performance & multi-threading? All this criteria's need to be considered when considering building efficient AI for the game.
The main idea is to maintain a frontier of unexplored nodes a character could visit at any point in time and to explore the one most likely to be part of the least costly path to the goal first. To accomplish this task, the algorithm uses heuristic function to determine the cost based on the distance from a node to the goal. Here's a implementation of A* -
For smooth navigation system, we worked out a way where the NPC's instead of taking smooth straight line path we made it traverse the path in natural way by moving between adjacent neighbors/ edges creating node points between nav meshes. For more look into funnel algorithm that forms triangles around each mesh for natural behavior.
References
http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf
http://digestingduck.blogspot.com/
http://www.gamasutra.com/view/feature/3317/smart_move_intelligent?print=1
Visit: http://jessicajosejohn.blogspot.com/ for more on the demo of path finding.
Getting started with proper path finding behavior can be daunting in making it smooth. The internet is filled with descriptions of standard A* algorithms for grid-based navigation. But modern 3d games often involve complex environment, right? So how do the programmers go about making the characters move around in those? Why don't we see zig-zag movement of characters towards you with good AI?
In this blog, we'll take a short look at how we can navigate the character using Navigation Mesh, which was particularly found in Left Dead 4 by Valve.
Navigation meshes are an efficient way of representing walkable regions in the game world. A collection of connected convex polygons. Each polygon is a node and each edge is shared by two polygons forming a solid connection between nodes.
Finding Path with AStar
Now that we can represent the search space - What's next? How will that help the NPC's to get where we want them to go? The answer is A* algorithm, one of the proficient way of getting a path between two points on a graph.
Understanding the theory of A* is only half the battle. How do we build a good navigation system around it? What do we need to watch out for to make sure the pathfinding behavior still remains robust? Which are the biggest obstacles to performance & multi-threading? All this criteria's need to be considered when considering building efficient AI for the game.
The main idea is to maintain a frontier of unexplored nodes a character could visit at any point in time and to explore the one most likely to be part of the least costly path to the goal first. To accomplish this task, the algorithm uses heuristic function to determine the cost based on the distance from a node to the goal. Here's a implementation of A* -
References
http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf
http://digestingduck.blogspot.com/
http://www.gamasutra.com/view/feature/3317/smart_move_intelligent?print=1
Comments
Post a Comment