HELLO Computer Craft Forums!


Today I'd like to educate you on path finding algorithms and my implementation of it in Lua. (Disclaimer: The program is not finished, but it works well in most situations)

THIS IS A PROOF OF CONCEPT!

Resources: http://www.raywenderlich.com/4946/introduction-to-a-pathfinding
http://theory.stanford.edu/~amitp/GameProgramming/

Current Program: https://github.com/LNETeam/Path (This includes the level find program located in computer 12) or "apt-get install lnet-find" (This installs the file itself)

Recommendations:
[indent=1]Clone the level.[/indent]
[indent=1]Place one of the DemoBots down[/indent]
[indent=1](I recommend my APT-GET utility. It's free and easy to update and install programs. You can also make your own programs)[/indent]
[indent=1]Run: "rm find"[/indent]
[indent=1]Run: "apt-get install lnet-find"[/indent]

[indent=1]To Run: "find <x> <z>"[/indent]

Introduction to Path-Finding:

[indent=1]Basically path-finding is exactly what it sounds like. The objective is to get from point A to point B. The more common algorithms actually find the shortest path to the destination using heuristic mathematics to "estimate" the best probable distance to the target. Implementations of path-finding can exist in games where you need to follow an AI or writing a program for a robot to navigate a complex course to complete an objective. The easiest way to visualize a "map" or "navigation-plane" is to imagine plot with (x,y) coordinates split into evenly distanced blocks or squares. These "distances" are known as costs. A cost is a unit of movement from one "square" to another. Most models are associated with DAG's or Directed Acyclic Graphs. These are essentially one way graphs with no negative edge costs and no infinite cycles. Some algorithms can handle these but for the time being we'll forget them as they don't pertain to this implementation. The most common algorithms are: Dijkstra's Algorithm, A*, Bellman-Ford. For the purposes of this demonstration, I used A*. A* uses shortest-tree-set to accomplish it's path discovery. Three functions are normally associated with movement: f(x),g(x),h(x). F is the summation of G and H. G is the cost all the way up to that particular "square". H is the heuristic or probable distance to the target. Upon a movement, the current square will analyze all adjacent squares or nodes. For this demonstration, all costs are 1. You could theoretically assign higher costs to water obstacles or higher altitude traversals, but I left it to 1. Once all adjacent nodes are discovered, if it is not a blocked and not previously discovered, then add it to a tentative add queue. It will then calculate a tentative f(x) score. The node with the lowest f(x) score is then selected. You'd then add the parent node to the path, all the way to the target. However, the turtle computes this in real time so no need for back tracking.[/indent]

My Implementation:

[indent=1]The plot uses a set of four computers with predefined gps hosting coordinates to correlate with our plot. It can theoretically be any size as long as the plot is set correctly. If at anytime, you run "gps locate" anywhere in that plot and you don't get a whole number, your coordinates are messed up. Post-movement, the turtle will evaluate all four sides to get an open query, Once calculated, a directional number is assigned to that face. Then using it's current location and vector manipulation, I calculate the exact distance to the target, add it to the cost and select the lowest f(x) score. [/indent]

Optimality:

[indent=1]Right now, it's pretty decent at solving puzzles thrown at it. However, if it gets backed into a 1x1 edge with only one way in, it may not complete the task. Navigating to the target directly behind an obstacle can confuse the turtle due to parent derivation problems. It is currently being addressed now.[/indent]

I shall be posting a video to this thread to demonstrate the algorithm in action. As always, Google is your friend and let the F=ma be with you :D/>