Sometimes you have an algorithm that manipulates or looks at some data in your simulation, and the algorithm needs to keep track of some kind of metadata that is strongly associated with the data, but that metadata belongs to the algorithm, not the data itself.

Like in A*, the h and g values of a node aren't a quality of that node, so you probably don't want to have your node contain public members h and g (in fact doing so would make multi-threading harder, though that's probably (hopefully) not a concern).

Or, if your updating the position of some reacting rigid bodies, and you want to keep track of which entities you've visited on the current pass. That data certainly doesn't belong to the entities themselves, but it is strongly paired with individual entities. It must be bonded to them somehow until you finish the pass.

The ways I can think of to store/organize the data are ...

Making wrapper classes:

class node:  int x  int y  list_of_neighboring_nodesdef A*(to, from, nodes):   class node_wrapper:      node the_real_slim_nodey      node his_daddy      int g      int h   // wrap all the nodes   // blah ...

And storing the metadata in local dicts/maps:

class node:  int x  int y  list_of_neighboring_nodesdef A*(to, from, nodes):   gs = dict()   hs = dict()   parents = dict()      // blah ...          // visiting a node          gs[node] = gs[parents[node]] + 1          hs[node] = h_function(node, to)          for node_2 in node.neighboring_nodes:             parents[node_2] = node   // blah ...

Any other approaches? What do you prefer?

I think I understand your first approach, you've taken all the pieces of meta-data about each node, like its costs, and rolled them together into one place, but its not a wrapper, it sits alongside the node. That can be easier than wrapping if you have multiple references to something, because you don't have to worry about whether each reference passes through the wrapper first (e.g., you have a pointer to the start node, but there is another pointer to the same node inside the graph.)

I'm not so sure I understand the second approach.

I would start like this?

abstract class path_finding_algorithm:   // constructor collecting graph and start/end nodes, and a pure virtual invoke method with no arg.sclass A* implements path_finding_algorithm:   def invoke():      // blah, the actual algorithmclass depth_limited_search implements path_finding_algorithm:  // blah ...// does not implement path_finding_algorithm because it's not interchangeable with the others in the face of negative edge lengths (according to the wikipedia list of pathing algorithms that I had to lookup)class bellman_ford_search:  // blah ...

(It's a little extreme to optimize by picking and choosing pathing algorithms, but it's just an example.)

Then, to find a path

// blah ...if (foo_graph.has_alot_of_bars):   pather = A*(graph, to, from)else:   pather = depth_limited_search(graph, to, from, depth-limit=3)// maybe some intermediate blah ..// possibly invoked elsewhere, maybe the engine puts the pather in a queue and schedules it for a less CPU-intensive framepath = pather.invoke()// blah ...

We instantiate the pathing algorithm we want to use, and it becomes a command that we can invoke later, to calculate the path.

Or, maybe

class A*: // possibly implementing some abstract pathing algorithm class   // constructor takes the graph   def invoke(to, from):      // find path and return it

where each instance of the A* class is bound to a specific graph. It would use member variables to store its node costs, and clear them after generating each path.

So, either way, the meta-data like the heuristic-cost and open and closed lists would all be protected members of the A* class, and the depth_first_search class would have current_depth, current_node, and visited_node_list members? Instead of wrapper class instances and node->cost maps and PathNode helper classes being local to a function, they are member variables of instances of the A* class?

Am I understanding this right?

>This is something I use on occasion, because generally it's only needed for truly complex or powerful algorithms, but it certainly is a great tool to have in the box.

Advantage number 1?: You could roll a class representing the AI of a baddy in a fighting sim with functions initial_move(), check_out_the_players_response(some_data_about_the_player), and respond(). You would instantiate it once per update, and call the members in sequence, and all three sub-components of the algorithm would share state.

Advantage number 2?: For an algorithm with lots of state and meta-data, you could separate the real meta-data (like the node-costs), from temporary variables by making only the real meta-data member variables, while the temporaries would be local to the member function invoke.

When you say "rather than an interface for the data on which the algorithm operates", what is the interface we are avoiding? The wrapper class / the map of nodes to their costs?

Sorry if I'm not catching on.

I appreciate the new approaches.

Just to be obnoxious and pedantic, wouldn't that be best described as simply a visitor pattern? Unless I'm missing some detail, which is entirely possible. If I'm right, though, searches for "visitor pattern" will probably be most fruitful.

Quote:Original post by ApochPiQ
Dammit, I knew there was a name for that, but I couldn't find my copy of Design Patterns so I improvised [lol]

"There's a pattern for that"

EDIT: I've had to use this pattern a whole lot in doing work with graphs, so it sticks.

I think I get it now, thanks :).