UPDATED: May 21, 2008
A bot path searching algorithm that will find the shortest and least cost path to the final state (goal). I wrote an example to visually explain how this is used in the real world. This type of bot searching is commonly used in games that are based on a grid system. The images below are taken from the example program that you can get below this description.
For example, say we have a map of some terrain. Shown below.
The bot must reach the goal with the shortest distance possible (if the path exists). The bot must also take into account different terrain types, each of them have their own difficulty level of traveling. The easiest type of terrain to move on is flat ground, so the bot will choose this over any other. The difficulty levels are ordered from easiest to hardest below.
Easy - Flat ground
Medium - Sand
Hard - Water
Very Hard - Hill
The bot then searches all possible nodes, only searching those that are the easiest to travel on as well as those closest to the goal. Below shows the nodes that the bot searches denoted with a yellow block "SN". Note that not all the nodes on the grid are searched, that is why this algorithm is so fast.
The bot then calculates the shortest and easiest path to get to the goal only using those searched nodes. Below is the path the bot takes.
1. There must be a Start and a Goal.
2. The path does not have to exist.
Here is a screen shot of the program that lets you play around with it for fun.
Below is a GUI example that lets you see how this works. Download the script below the screen shot.
Edited by Toady, 21 May 2008 - 05:43 PM.