Jump to content

  • Log In with Google      Sign In   
  • Create Account


Inheritance vs. Templates


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
8 replies to this topic

#1 kirkd   Members   -  Reputation: 505

Like
0Likes
Like

Posted 12 September 2012 - 09:47 AM

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?

Sponsor:

#2 Goran Milovanovic   Members   -  Reputation: 1103

Like
0Likes
Like

Posted 12 September 2012 - 10:27 AM

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

+---------------------------------------------------------------------+

| Need a programmer?        ->   http://www.nilunder.com/protoblend   |

| Want to become one?       ->   http://www.nilunder.com/tutoring     |
| Game Dev video tutorials  ->   http://www.youtube.com/goranmilovano |
+---------------------------------------------------------------------+

#3 kirkd   Members   -  Reputation: 505

Like
0Likes
Like

Posted 12 September 2012 - 11:41 AM

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?

#4 mrbastard   Members   -  Reputation: 1573

Like
2Likes
Like

Posted 12 September 2012 - 12: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.

Edited by mrbastard, 12 September 2012 - 01:37 PM.



#5 dmatter   Crossbones+   -  Reputation: 2979

Like
2Likes
Like

Posted 12 September 2012 - 03: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).

Edited by dmatter, 12 September 2012 - 03:02 PM.


#6 CyberRascal   Members   -  Reputation: 208

Like
0Likes
Like

Posted 12 September 2012 - 03: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.

#7 Telastyn   Crossbones+   -  Reputation: 3724

Like
4Likes
Like

Posted 12 September 2012 - 03: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.

#8 kirkd   Members   -  Reputation: 505

Like
0Likes
Like

Posted 13 September 2012 - 11:10 AM

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

#9 Goran Milovanovic   Members   -  Reputation: 1103

Like
0Likes
Like

Posted 13 September 2012 - 03: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.

+---------------------------------------------------------------------+

| Need a programmer?        ->   http://www.nilunder.com/protoblend   |

| Want to become one?       ->   http://www.nilunder.com/tutoring     |
| Game Dev video tutorials  ->   http://www.youtube.com/goranmilovano |
+---------------------------------------------------------------------+




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS