So I’ve finally written the fabled A* algorithm. I’ve heard quite a bit about A*, though most of it was just name dropping. Anytime I had overheard someone talking about AI, it was sure to be in there somewhere, if not the basis of the conversation. Naturally, I had built up an inflated, almost scary view of it, thinking it was going to be an extremely difficult thing to implement. Turns out that with a neat search space interface to work with and a good understanding of the core principles, it wasn’t too bad.

For those of you out there that are unfamiliar with A*, it is basically a path-finding algorithm that finds the best path to a goal. It does this by comparing two costs, given cost and heuristic cost. Given cost is, in my case, the distance it takes to get to that node from the start. Heuristic cost is a guess cost of the distance to the goal. The beauty of A* is that is uses both of these costs in unison to find the best path with the least amount of processing time. There are, of course, alternatives, but A* is widely accepted as one of the better solutions.

Here’s a sample of my algorithm. WordPress sort of mangles formatting so my indentation was lost. I’ve also trimmed out some optimization and implementation specific code for clarity:

//we've already pushed the first node on, so we continue searching until we run out of nodes to search while(!m_aStar->openList.empty()) { //grab the currently cheapest node Node* node = m_aStar->PopCheapestNode(); //if we've arrived at our destination, we can return true if(node->nodePos.first == m_aStar->goalZ && node->nodePos.second == m_aStar->goalX) { //back tracks along nodes through parent pointers, creating a path for the agent m_aStar->GeneratePath(&m_waypointList, node); //if we clicked on the goal, t he waypoint list will be empty, so put one node on if(m_waypointList.empty()) { m_waypointList.push_back(cur); } return true; } //pass in a neighbor to be filled with data Node* neighbor = NULL; //Generates 8 neighbors and returns 0 when finished while(m_aStar->GenerateNeighbor(node, neighbor) == 0) { //if we hit a wall or invalid position, continue if(neighbor == NULL) { continue; } //calculate our total cost based on heuristics and given cost neighbor->totalCost = m_aStar->ComputeTotalCost(neighbor, GetHeuristicCalc(), GetHeuristicWeight()); //if the node isn't on either list, then push it onto the open list if(!neighbor->onClosed && !neighbor->onOpen) { neighbor->onOpen = true; m_aStar->PushOpenListNode(neighbor); } } //place the node on the closed list, and color accordingly node->onClosed = true; }

One important thing to note is the GenerateNeighbor function. I didn’t post the code because it isn’t terribly interesting, but it does do an important part of the function. Basically it finds neighboring nodes in the grid and calculates their given cost and updates the Open List if it is cheaper than a node of the same coordinates already on the Open List. The Open List is basically a list of nodes to be explored. While there are lots of ways to do A*, I was pretty pleased with my first attempt at it. Even looking over the code now, I can already start thinking about ways to optimize and beautify the code, but I must move on to other projects.

A* was definitely a blast to write, and I really loved the feeling of success I got from completing it. It’s a good algorithm to write and I’d definitely recommend it to anyone curious. The hardest part is getting a visual representation to work with, but past that it isn’t too bad. Well, now I’ll be moving onto a research project in Unity, so we’ll see how that goes!