![]() This A* search implementation could be used as a component to larger system (like a game - maybe tower defense or puzzle), or just for learning purposes. ![]() Also see the Wikipedia pseudocode for another example. Here is some high level pseudocode of what is happening in the algorithm. So, a node that took only 1 step to arrive at and 5 to get to the end is more ideal than one that took 10 to arrive and and only 1 to get to the end. Think about it like this: the best node is one that takes the least total amount of time to arrive at and to get to the end. Note: There are many different ways to guess how far you are from the end, I use the Manhattan distance in this implementation. We online need to update this if it is not set already, since the distance to the finish will not change even if the path we took to arrive at a node changes. h(x): The estimated time to reach the finish from the current node.If we reach a node for the first time or reach a node in less time than it currently took, then update the g(x) to the cost to reach this node. g(x): The total cost of getting to that node (pretty straightforward).There are three functions that we keep track of for nodes that we look at: I will do my best to explain what is going on, but feel free to just look at the source of the example, or just download astar.js. This is the actual implementation of the algorithm. For this little page, I’m not too worried about it, but if I do get around to adding in more algorithms, I will probably improve this code. There are some performance issues that could be addressed, and It modifies the Array.prototype to add on specific methods (findGraphNode and removeGraphNode) for search algorithms, which may not be ideal for bigger projects. Please take a look at it, be aware that there are some improvements I would make if I was to rewrite this today. I won’t get too into the code here, since it distracts from the search algorithm. It also has an option to show the debugging information created by the search algorithm. ![]() The point of this file is to build the graph, call the search function, and animate the results after the search has returned. Also, I have a JavaScript block that initializes the page. Just a basic html file that includes jQuery, the excellent JavaScript library, main.css, graph.js, and astar.js. Maybe I will get around to plugging in some more algorithms sometime and making it into a little resource for graph search algorithms. My hope was to build a page that could be extended with other search algorithms by separating the UI code (that generates a graph with walls and animates the path that is determined by an algorithm), and the algorithm that finds the path. This way, people could see what was going on and view the source very easily by using the online demo. Since I know JavaScript pretty well, and most of the examples you can find are in C, Java or a similar language that you cannot run without downloading source code or executables, I thought it would be a good idea to program it on an html page. ![]()
0 Comments
Leave a Reply. |