🔒 Locked

Inheritance vs. Templates

Started by kirkd Sep 12, 2012 at 3:47 PM 7 replies 2.1k views

Original Post

Sep 12, 2012 at 3:47 PM

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?

Goran Milovanovic

Sep 12, 2012 at 4:27 PM

I would have a component called Navigation, which could be used by any given Entity.

kirkd

Sep 12, 2012 at 5:41 PM

I would have a component called Navigation, which could be used by any given Entity.

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

mrbastard

Sep 12, 2012 at 6:01 PM

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 - clicky. Style-wise, as "inheritance is the second-tightest coupling in c++" 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.

dmatter

Sep 12, 2012 at 9:02 PM

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.


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

(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).

CyberRascal

Sep 12, 2012 at 9:10 PM

Some negative things about templates for duck-typing:

Executable bloat
Compile time increase
Can no longer separate header / source

For an algorithm like your example I'd probably go with templates anyway though.

Telastyn

Sep 12, 2012 at 9:17 PM

Which would you choose, and why?

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.

kirkd

Sep 13, 2012 at 5:10 PM

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^)

Goran Milovanovic

Sep 13, 2012 at 9:40 PM

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


 // Pseudocode
 
 class Soldier:Entity{
 
 init(){
 nav = Navigation(this)
 }
 
 run(){
 
 if keyHit(somekey):
 nav.setDestination(somevec)
 
 pos += nav.getDirection() * speed
 }
 
 }

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.