I am about to implement A* pathfinding algorithm and I wonder how should I implement this - from the point of view of architecture.

I have the pathfinder as a class - I think I will instantiate only one object of this class (or maybe make it a Singleton - this is not so important).

The hardest part for me is whether the closedSet and openedSet should be attached to objects that can find the path for them or should be stored in pathfinder class ?

I am opened to any hints and critique whatsoever.

What is the best practice considering pathfinding in terms of design ?


The open and closed sets are only relevant to the algorithm itself (unless you are interested in more than the shortest path, e.g., maybe you want to make an animation of the algorithm in progress) and they depend on the algorithm's parameters (the closed set, for example, is initialized as containing the path's starting node). This means the sets should only be accessible by the algorithm's code. A concrete example can be seen in the pseudocode on Wikipedia's A*-article.

Since you've tagged your post and are open to any critique whatsoever: Don't use a singleton. (Good explanation by munificent.) Instead, implement your A* as a static function or as a method on a graph(-like) object, which could be the object representing your game world. Nevertheless, the open and closed sets should be local variables of this function or method.

| improve this answer | |
  • 2
    \$\begingroup\$ Why a static function or a method on a graph? Surely it should be an implementation of a path-finding interface which can be used as a strategy? \$\endgroup\$ – Peter Taylor Dec 18 '12 at 13:23
  • 1
    \$\begingroup\$ I considered adding that option, but I'm guessing the asker isn't planning on switching A* out for other implementations from time to time. In that case Strategy is a waste of time. I also figured including it wouldn't help driving this point (initially re Singleton) home: Design patterns are Good if your design needs them, that doesn't mean they still are if it doesn't. \$\endgroup\$ – Eric Dec 18 '12 at 15:05
  • 1
    \$\begingroup\$ Adding a "PathFinder" interface really doesn't require any extra time... Also, a note for OP: quite often the ClosedSet doesn't actually exist; the developer will instead add a HasBeenVisited property to the Node class. \$\endgroup\$ – BlueRaja - Danny Pflughoeft Dec 18 '12 at 16:34
  • \$\begingroup\$ @Eric Thanks for the answer - I ended up putting these sets as local variables in method that finds paths. \$\endgroup\$ – Patryk Jan 3 '13 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.