Jump to content
Site Stability Read more... ×
  • Advertisement
  • entries
  • comments
  • views

A-star pathfinding

Sign in to follow this  


Here's an implementation of A* in C++ which hopefully works and is quite sensible.

Note that

  • It doesn't use a million templates, or any for that matter (except std containers).
  • It doesn't do stupid things like trying to erase out of the middle of a queue.
  • It assumes nothing about data structures so is highly generic.
  • It doesn't come with its own memory allocator/hash table/queue/linked list. It's just A*.

    Instructions: derive from it and implement the virtual functions. Then call FindPath(start, end). That's it!
    class AStar{public: void FindPath(int startIndex, int endIndex) { // Add the nodes in the starting zone to the open list. std::vector connectedNodes; GetConnectedNodes(startIndex, connectedNodes); for (int nodeIndex : connectedNodes) { float f = GetDistance(startIndex, nodeIndex) + GetDistance(endIndex, nodeIndex); openQueue.emplace(OpenQueue::value_type(-f, nodeIndex)); nodeMap[nodeIndex] = NodeInfo(f, startIndex, GetData(startIndex)); } while (!openQueue.empty()) { // Get the first item in the queue and remove it. float currentLength = -openQueue.top().first; int currentIndex = openQueue.top().second; openQueue.pop(); // Add it to the closed list; std::pair r = closedSet.insert(currentIndex); if (r.second == true) // If it was already on the closed list, ignore it. { if (currentIndex == endIndex) // Found the final node. { int nodeIndex = currentIndex; // Output the path. while (true) { AddToPath(nodeIndex); if (nodeIndex == startIndex) break; nodeIndex = nodeMap[nodeIndex].parentNode; }; return; } connectedNodes.clear(); GetConnectedNodes(currentIndex, connectedNodes); float g = currentLength - GetDistance(currentIndex, endIndex); for (int newNodeIndex : connectedNodes) { if (closedSet.find(newNodeIndex) == closedSet.end()) { float f = g + GetDistance(currentIndex, newNodeIndex) + GetDistance(newNodeIndex, endIndex); auto it = nodeMap.find(newNodeIndex); if (it == nodeMap.end() || it->second.f > f) { // The node may be in the open set already. If so, this will add it again // with a lower f score and update the NodeMap. openQueue.push(OpenQueue::value_type(-f, newNodeIndex)); nodeMap[newNodeIndex] = NodeInfo(f, currentIndex, GetData(currentIndex)); } } } } } }protected: struct NodeInfo { NodeInfo() {} NodeInfo(float f, int parentNode, int data) : f(f), parentNode(parentNode), data(data) {} float f; int parentNode; int data; }; virtual void GetConnectedNodes(int nodeIndex, std::vector& nodes) = 0; virtual float GetDistance(int node1, int node2) = 0; virtual void AddToPath(int nodeIndex) = 0; virtual int GetData(int nodeIndex) = 0; typedef std::priority_queue> OpenQueue; typedef std::unordered_set ClosedSet; typedef std::unordered_map NodeMap; OpenQueue openQueue; ClosedSet closedSet; NodeMap nodeMap;};
Sign in to follow this  


Recommended Comments

This might be more efficient than my own implementation. What's the OpenQueue type?

Share this comment

Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!