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?
Inheritance vs. Templates
I would have a component called Navigation, which could be used by any given Entity.
Author
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?
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.
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.
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.
(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).
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).
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.
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.
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.
Author
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^)
Hopefully by the end of next week the design and implementation will be done and I can not question it further. 8^)
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
