Sign in to follow this  
kirkd

Inheritance vs. Templates

Recommended Posts

At the risk of starting a religious war...

I'm in the design process and currently looking at pathfinding. I'm happy to use A* as my graph search alogorithm, and I like the idea of making this pathfinder as reusable as possible since we don't have anything at this point requiring less than a massive rewrite.

My first instinct is to use class structures and inheritance. Specifically, my search algorithm (A* in this case) would accept an AStarSearchable class, which would implement the appropriate ExpandNode function and have some friend functions to take care of other details such as DistnaceFromStart, HeuristicToCoal, DistanceToGoal (DistnaceFromStart + HeuristicToGoal). In the extreme, I cold make a SearchAlgorithm base class and then have different algorithms derived from that.

On the other hand, if I use templates and make my A* algorithm a template class with the expectation that the supplied parameter type implements the functions I mentioned, I see another way to get at the same result.

Which would you choose, and why?

Share this post


Link to post
Share on other sites
[quote name='Goran Milovanovic' timestamp='1347467274' post='4979351']
I would have a component called Navigation, which could be used by any given Entity.
[/quote]

OK. Could you throw a teeny more detail in there?

Share this post


Link to post
Share on other sites
I'd go with the template unless you need polymorphism at runtime. That's the key factor.

The only other consideration I can think of is whether your team are familiar enough with templates to pick it up and use it - though I swear by the above advice, I default to inheritance if it saves arguing with my team!

Edit:

It's worth mentioning that the reason I'd go with the template (apart from personal style) is that compile-time polymorphism avoids the extra indirection of a vtable - [url="http://www.gamedev.net/page/resources/_/technical/general-programming/improving-performance-in-c-with-compile-time-r2015"]clicky[/url]. Style-wise, as [url="http://www.artima.com/cppsource/codestandards3.html"]"inheritance is the second-tightest coupling in c++"[/url] I tend to avoid it unless it's the perfect tool for the job. IMHO this also makes templates (huge generalisation coming up here) easier to reuse, maintain, and test than inheritance hierarchies. Edited by mrbastard

Share this post


Link to post
Share on other sites
Of those two options I would go with templates, mrbastard gave some good reasons why.

In terms of making it "reusable as possible" I could be tempted to follow the principles used by the standard library and have the search accept the path-cost function, the admissible goal-distance function and a node-expander function instead of assuming they are all members of the node type (so now a node could simply be a pointer into a 2d array, etc), e.g.

[code]
template <typename NodeT, typename PathCostFunctionT, typename GoalDistanceFunctionT, typename NodeExpanderFunctionT>
void search(NodeT start, NodeT goal, PathCostFunctionT pathCostScorer, GoalDistanceFunctionT admissibleGoalDistanceEstimator, NodeExpanderFunctionT nodeExpander);
[/code]

(Obviously what this signature is lacking is away to emit the discovered path, assuming the full path is what you're trying to discover. I'll leave that up to you, you could return a collection of nodes, or perhaps take an iterator to write out nodes in the path - and then pass it a back_insert_iterator). Edited by dmatter

Share this post


Link to post
Share on other sites
[quote name='kirkd' timestamp='1347464838' post='4979340']
Which would you choose, and why?
[/quote]

Neither.

I would make some interface for pathfinding and then use the actual interfaces your game is using as the parameters for it to work. It's far more likely that your abstraction point is on the pathfinding implementation than the types used for your graph/map.

Once you get to game #2, worry about re-use then. Frankly, it should take a day or two to make a functional A* implementation. The re-use win just isn't worth the added complexity of making the solution generic.

Share this post


Link to post
Share on other sites
Thanks to everyone for their input! It certainly helps to have other opinions to help with my decision. I'm much more comfortable with inheritance, but maybe this is a good excuse (and not too complicated of a project) to get comfortable with templates. Of course, the suggestion to go with neither has strong merit, too.

Hopefully by the end of next week the design and implementation will be done and I can not question it further. 8^)

Share this post


Link to post
Share on other sites
[quote name='kirkd' timestamp='1347471718' post='4979381']
OK. Could you throw a teeny more detail in there?
[/quote]

[code]
// Pseudocode

class Soldier:Entity{

init(){
nav = Navigation(this)
}

run(){

if keyHit(somekey):
nav.setDestination(somevec)

pos += nav.getDirection() * speed
}

}
[/code]

It's an oversimplified example, but that's one alternative.

I would additionally like to echo what Telastyn said: Generic is not always better.

Make games, not engines/platforms/libraries; Reusable code is something you should distil from previous games.

Share this post


Link to post
Share on other sites

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