I’m using A* to solve the paths for this wire system in my game. The issue I’m running into is that it’s not on a grid system and nodes aren’t always spaced equally which causes some issues when evaluating which is the best node.
Here’s how my implementation currently evaluates the best node
(the Nodes variable is actually just the surrounding nodes, not all of them)
The issue with my solution is shown here:
I see some issues with the algorithm you have posted, but I’m also curious how the returned nodes are being used to calculate a path. Could you post that code or explain it?
As for the A* algorithm… are you familiar with breadth first searches for trees? A* keeps a “fringe” list and keeps adding nodes to it and orders them by cost. Implementation wise, it is very similar to how a breadth first search is implemented except that the nodes are stored in an priority queue instead of a FIFO queue. What I see going on here is a linear scan through the nodes and assigning a cost to each, not a weighted breadth first search at all.
In addition, I see that this confusion has caused issues calculating the gCost. The gCost keeps track of the cost to get to a node: it depends on the gCost of the previous node and the distance between them. This means that for each node, you will have to keep track of which node you came from when traversing. Without keeping track of the history to get to a node and having it affect your cost, the path you take doesn’t matter. While you could use the magnitude squared to the goal as the hCost, it will make your search more greedy and usually not optimal. For A* to work the hCost needs to be less than or equal to the fastest way to reach your goal. The more accurate it is, the more efficient A* will be in general. If it overestimates the cost, then A* may not return the shortest path. Since you can only travel in two directions (up/down and left/right) I would actually recommend using the manhattan distance which is simply the difference in x plus the distance in y. This will yield better performance in both computing the distance and A* runtime, while preserving A*'s guarantee to find the minimum path.
I’ve written a couple A* implementations which you can find by looking at my profile. Here is one:
That solution has two functions which you need to fill out, and will work with any graph type. It doesn’t care about the internal representations of your nodes, you simply pass in a value that represents the start and goal nodes and it will use your two functions to perform A*. The two functions are getAdjacent(node) and getDistance(node, endNode). The first returns a table with nodes as the keys and the cost to those nodes as the values. The second is only used to find the distance to the end node and returns a number. Again: the implementation is node agnostic: it can be grid nodes, a web, or even a navigation mesh.
(I should note that you probably want to use a function other than sort or the getMinimum function included in the code I posted. The sort function runs in O(n * log(n)) time but must be run up to n times, for a runtime of O(n * n * log(n)). The getMinimum function I included runs in O(n) time so in the worst case needing to visit every node it runs in O(n * n). A binary heap will run in O(log(n)), yielding performance of O(n * log (b)) which is MUCH better than the previous two options. I used to have an implementation in Lua I used all the time but I’ve lost it. I’m sure you can find or make one. A radix or counting sort could be used if you know more about the problem for near constant time performance.)
