Brief Overview
Path Finding is an engine API designed to create an architecture for AI behaviors by analyzing the problem to be solved and customizing the system of data structures based on the need. In this application, I started sketching out the search graph using the Tile Map containing raw data such as - X, Y, & Weight and then moved on to create Hex Tile Adjacency, a terrain map made up of tiles that are hexagons, however they are stored in 2D array on console window. Then I proceeded to code Breadth First Search Algorithm and worked my way up to A*. The purpose behind building Breadth First Search, Greedy Best First Search, Uniform Cost Search, and A* is to recognize the difference in cost and speed of each to reach their end goal. All of them vary with regards to the neighboring nodes they traverse till their way to the goal. Mechanics Of Path Finding API
A path is found using a graph composed of search nodes, each of which stores information regarding the corresponding tiles and its successors, and the planner nodes , which store information about the paths and its cost. In the application, the blue circles represent all the planner nodes that the search algorithm has visited so far. Nodes with the green inner green circles are open nodes that the algorithm can use to extend existing paths; the lighter the green interior, the closer the node is becoming the current node. Note that the current node is not an open node, so it doesn't have a green inner circle; instead, the application draws a red line from this node through each successive parent node until the starting tile is reached.
While the application is paused, depending on the algorithm, either the orange circles will appear around the neighbors of the current node, or orange lines will extend toward those neighbors. The algorithm evaluates only these successor nodes along with the current node at each iteration.
After setting the current node at the start of each iteration, the search algorithm checks whether or not this node is at the goal tile. As long as this is not the case, the size of the current path and the number of iterations so far will appear as red text in the information display.
When the search algorithm finally reaches the goal, the red line will be decorated with large blue squares that indicate the solution path.
While the application is paused, depending on the algorithm, either the orange circles will appear around the neighbors of the current node, or orange lines will extend toward those neighbors. The algorithm evaluates only these successor nodes along with the current node at each iteration.
After setting the current node at the start of each iteration, the search algorithm checks whether or not this node is at the goal tile. As long as this is not the case, the size of the current path and the number of iterations so far will appear as red text in the information display.
When the search algorithm finally reaches the goal, the red line will be decorated with large blue squares that indicate the solution path.
Github Link -https://github.com/jessjohn123/Artificial_Intelligence_And_Machine_Learning_Algorithms/tree/master/Path_Search
No comments:
Post a Comment