AI Pathfinding Demonstration

The environment for the demonstration was provided by Professor Steve Rabin.

First off a legend for the colors you'll see:
Black: obstacles
Pink: goal destination
Blue: closed list
Green: open list
Cyan: nodes along the path before any reducing or smoothing
Red: path the AI travels along; arrow heads show the number of nodes along the path


This starts off with a demonstration of Dijkstra's Algorithm, by setting the heuristic weight to zero i.e. it only uses the distance traveled so far in its calculations. Next it shows traveling to the same location using a normal A* implementation with an admissible heuristic. Then it shows what happens when weighted in favor of the heuristic, thus making a more depth-first search for the goal.

Afterward there is a demonstration on how, when a heuristic is more accurate, a slight weight in its favor can make a noticeable change. First we show Euclidean heuristic at 1.00 weight and then 1.01 weight. There isn't a noteworthy change. When we look at the more accurate cardinal/inter-cardinal heuristic, however, we see changing the weight from 1.00 to 1.01 removes the anomalies in the search pattern as it helps deal with the floating point errors that occur in the calculation of the cost to the goal.

Finally, the video demonstrates the polishing touches to the AI. First there is rubberbanding, where the AI cuts across squares where it knows there to be no obstacles. Then there is smoothing in conjunction with it, using Catmull-Rom splines to generate a more natural curved path for the AI to travel.

See the rest of my portfolio at www.cassandraboykin.com

Category:

Education

Tags:

• AI
• Pathing
• Pathfinding
• DigiPen
• Cassandra
• Boykin

[ramiBudemaris]

nice stuff .... is there any pdf about it ?