Sign in to follow this  

attaching metadata in algorithms

This topic is 2660 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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_nodes

def 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_nodes

def 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?

Share this post


Link to post
Share on other sites
I typically use a lot of locally-defined structures for this (which I suppose would equate best to your second example). For instance, in my C++ implementation of A* pathing, I use a local helper struct to contain information on previously-checked paths, including the heuristic and total-cost scores. I use similar approaches quite a bit.

Another thing that can be very powerful is a combination of the Strategy pattern and the Command pattern, wherein you write an interface for the algorithm itself rather than an interface for the data on which the algorithm operates. (It's a weird inversion if you aren't used to it, but it makes a lot of sense once it clicks.) The algorithm object then stores the state it needs internally, and an invocation of the algorithm can be encapsulated via the command pattern method. 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.

Share this post


Link to post
Share on other sites
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.s

class A* implements path_finding_algorithm:
def invoke():
// blah, the actual algorithm

class 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 frame
path = 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.

Share this post


Link to post
Share on other sites
Sounds like you got the gist of it [smile]


Quote:
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?


Instead of:

class FooData
{
public:
int Frobnicate() const
{ return Foo + (Bar * Quux); }

int Blifficate() const
{ return (Foo + Bar) * Quux; }

private:
int Foo;
int Bar;
int Quux;
};



We write something like this:

struct FooData
{
int Foo;
int Bar;
int Quux;
};

class Processor
{
public:
Processor(const FooData& data) : TheData(data)
{ }

virtual int Process() const = 0;

private:
const FooData& TheData;
};

class Frobnicator : public Processor
{
public:
virtual int Process() const
{
return TheData.Foo + (TheData.Bar * TheData.Quux);
}
};

class Blifficator : public Processor
{
public:
virtual int Process() const
{
return (TheData.Foo + TheData.Bar) * TheData.Quux;
}
};



Obviously in this trivial case it's a lot more code, but when there's actual metadata attached to the frobnication/bliffication processes, that data can be contained succinctly within the Processor subclasses rather than having to fit it into a single function. It also lets you swap out algorithms dynamically using polymorphism rather than a switch or function pointers or some other dispatching method to get to the Frobnicate()/Blifficate() functions. When there's a lot of algorithms to choose from (or a lot of associated metadata) this can be quite a bonus.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

This topic is 2660 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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

Sign in to follow this