Understanding Goal-Based Vector Field Pathfinding

hello my name is Sidney Durant and I'm a programmer Georgia Tech student and tuts plus contributor if you enjoyed this video feel free to check out my blog at Sidney Durant blog spot.com I'm here today on behalf of gamedev tots to explain a goal based path finding as you can see right now on the screen I have over 20,000 particles all simultaneously pathfinding towards my mouse cursor in the upper left corner of the screen with traditional path finding and this would be impossible but goal based path finding is extremely efficient traditional pathfinding works by finding the optimal path from every single Pathfinder to the goal this is an efficient especially if many pathfinders are calculating a similar paths goal based path finding works differently though it finds the shortest path from the goal to every single tile on the map and then the particles simply refer to the tile they are on to determine the direction they need to go in to get closer to the goal there are three steps to implementing goal based path finding the first is to calculate a distance field which can be seen here as you can see the goal has a distance of 0 from itself and the distances increase as you get further away from the goal it is important to note that the distance is calculated our path distances and not linear distances so even though this area right here is closer to the goal than this area over here it is considered further away in path distance because path finders will have to circumnavigate obstacles to get to it the second step of goal based path finding is to calculate a vector field which can be seen here the vector field that simply looks at the distance field to determine what direction Pathfinder's much must go in to get closer to the goal the vector field looks at the gradient of the distance field and always points towards the lower numbers the third part of goal based path finding is the Pathfinder movement itself here the particles are simply accelerating in the direction indicated by the vector field more complicated movement behaviors can be used though for example steering behaviors can easily be implemented with goal based path finding goal based path finding is a flexible and efficient approach to path finding especially in situations where path finders are recalculating these same paths over and over again it is not always the best kind of path finding to use though it is inefficient with large maps and if there are many men goals it can cause a lot of CPU strain it is often a very good solution to the pathfinding problem especially with large numbers of particles small maps and fewer goals I hope you enjoyed the demo and if you would like to read the full article that explains how to implement goal based path finding in much more detail there is a link in the video description thank you for watching and I hope you enjoyed the video

Channel: Tuts+ Game Development

Views: 111,279

Keywords: gamedev, pathfinding, math, vector field pathfinding, goal-based pathfinding

Id: Bspb9g9nTto

Length: 3min 18sec (198 seconds)

Published: Fri Jul 05 2013