Skip to main content
gamedev.net
🔒 Locked

Dynamic token "pattern"?

Started by Sneftel 7 replies 1.2k views
Original Post
Sneftel
Sneftel
There is a technique that I have found myself both using, and disliking, more than once in my code: An implementation of an abstract class returning an object of a particular implementation of a different abstract class, then later expecting that an object of the same implementation be returned to it. I most recently ran into it when coding up a generic min-max algorithm... here's the basic idea: 

class GameState
{
};

class Game
{
public:
    virtual GameState* GetInitialState() = 0;
    virtual std::vector<GameMove> GetSuccessorStates(GameState* currentState) = 0;
};

class MancalaGameState : public GameState
{
    int bins[14];
};

class MancalaGame : public Game
{
    virtual GameState* GetInitialState() { return new MancalaGameState(...); }
    virtual std::vector<GameMove> GetSuccessorStates(GameState* currentState)
    {
        MancalaGameState * mancalaGameState = static_cast<MancalaGameState *>(currentState); // <-----
        ...
    }
}
Basically, "GameState" is an entity which MinMaxSolver will want to keep around, as well as use to generate more states from the implementation of Game which has been given to it. It doesn't contain anything specific to a Game; rather, implementations of it add fields (and accessors) which specify the actual state in the proper vocabulary. For each implementation of Game there is an implementation of GameState which it uses. MancalaGame expects that the only GameState that will ever be passed to it is a MancalaGameState, but nowhere is this contract enforced (in this case it can't be, since GameState has no virtual methods!) and the required casting looks very ugly. This isn't the best example, since GetSuccessorStates could conceivably be moved to GameState, but there are situations where it makes absolutely no sense to give the method to GameState. Possible solutions: 1. What I'm doing right now, with the casting. Ugly, and seems to subvert OOP. 2. Generic interfaces, where GameType is expected to provide a GameType::State. Somewhat more in line with how I think C++ wants me to do things, but doesn't allow runtime binding of games to solvers (I actually do want this). 3. Shovel everything from Game to GameState, regardless of where it SHOULD go. Even this doesn't always work... consider a function intended to provide a partial ordering on GameStates, where you'd always need to pass at least one in as an argument. 4. ??? It's not a big thing, but it irks me. It irks me even more that other people seem to be doing it too (see argument objects passed to C# event handlers) and not discussing it. Ideas?
MaulingMonkey
MaulingMonkey
This is the kind of thing... oh frak what's the term... is supposed to solve...

You know, the thing where you can change the return type during virtual overrides to a more specific derived class!!!

Something ala:

class IGame {public:    virtual GameState* GetInitialState() = 0;    virtual GameState* CurrentState() = 0;    virtual std::vector<GameMove> GetSuccessorStates(GameState* currentState) = 0;};template < typename GameStateT > class GameBase : public IGame {    BOOST_STATIC_ASSERT(( boost::is_base_of< GameState , GameStateT >::value ));    boost::scoped_ptr< GameStateT > state;public:    virtual GameStateT* GetInitialState() = 0;    virtual GameStateT* CurrentState() { return state.get(); }    //      ^^^^^^^^^^---- legal as long as GameStateT derives GameState (and yes, overrides the IGame::CurrentState, not shadows!)};class MancalaGame : public GameBase< MancalaGameState > {public:    virtual MancalaGameState* GetInitialState() { return new MancalaGameState( ... ); }virtual std::vector<GameMove> GetSuccessorStates(GameState* currentState)    {        MancalaGameState * mancalaGameState = CurrentState();        ...    }};


Two components I'm trying to bring to attention here: That return type change while overriding thing, and the increased potential for shoving stuff into the "base implementation" if you use template parameters (which is sane if you keep the interface decoupled)

EDIT: And of course, for enforcing stuff without interfaces, BOOST_STATIC_ASSERT (and boost type traits) are your friends. Boost's site isn't responding, so no guarantees I've got the syntax right :-/.
ToohrVyk
ToohrVyk
MaulingMonkey, you might be groping for the term "covariant return types", but I'm pretty sure these don't work for types other than the class itself.

In this situation, it's pretty clear that the type for each class is different. Type parametrization rings the "template" bell to me, although how far you ring the bell depends (for example, an intermediary template wrapper from which you inherit, that only implements these two functions on top of a non-template base class).
Blog — Facebook
Sneftel
Sneftel
Covariant return types are fun, and may be put to a limited use here (MancalaGame::GetInitialState() could return a MancalaGameState*), but they don't solve the underlying problem, which is the argument to GetSuccessorStates. Remember, the MinMaxSolver will be operating only on the Game interface, so it won't have access to the covariant return type. And again, generics (aka templates) solve this problem but cannot do so dynamically.
MaulingMonkey
MaulingMonkey
Quote:
Original post by Sneftel
Covariant return types are fun, and may be put to a limited use here (MancalaGame::GetInitialState() could return a MancalaGameState*), but they don't solve the underlying problem, which is the argument to GetSuccessorStates.


Gosh I'm blind, I didn't even see that argument.
Erm, yeah, I'd use boost::polymorphic_cast or boost::polymorphic_downcast. The alternative is to make MinMaxSolver depend on template parameters (impossible, given that the appropriate parameters arn't exposed by IGame), or to compare the input pointer against internally (to MancalaGame) stored pointers of the correct type which are then used instead (which only adds even more potential error conditions - that is, of the correct type yet not on the list - meaning it's at a further disadvantage to boost::polymorphic_*cast, which seems to be a better solution)
NotAYakk
NotAYakk
How about:
class GameState;class Game;class BoundGameState;class HasAGameState { public: virtual GameState* GetGameState() = 0; };class HasAGame { public: virtual Game* GetGame() = 0; };class Game{public:  virtual BoundGameState* GetInitialState() = 0;};class BoundGameState:  public virtual HasAGameState,  public virtual HasAGame{  public:    std::vector<GameMove> GetSuccessorStates() = 0;};class MancalaGame : public Game{  class BoundMacalaGameState:    public HasAGameStateImpl<MacalaGameState*>,    public HasAGameImpl<MancalaGame*>  {  public:    std::vector<GameMove> GetSuccessorStates() {      GetGame()->GetSuccessorStates( GetGameState(); );    }  };  BoundMacalaGameState( ... ): ... {}public:  BoundMacalaGameState* GetInitialState() { return new BoundMacalaGameState(...); }}


No type casting. The two tied together types (gamestate and game) are bound together at the creation of the BoundGameState, and it contains all of the functions that need to know both the GameState and the Game.

Sneftel
Sneftel
Looks interesting, but confusing. Where are the definitions of HasAGameStateImpl and HasAGameImpl?
NotAYakk
NotAYakk
Quote:
Original post by Sneftel
Looks interesting, but confusing. Where are the definitions of HasAGameStateImpl and HasAGameImpl?


In:
  class BoundMacalaGameState:    public HasAGameStateImpl<MacalaGameState*>,    public HasAGameImpl<MancalaGame*>


I just left the template unwritten because they are damn easy. :)

Details:
template<typename actual_storage>class HasAGameStateImpl: public virtual HasAGameState{private:  actual_storage* GameStateStorage;  // or an auto pointer of some kindprotected:  void ChangeGameState(actual_storage* NewGameState)    {GameStateStorage=NewGameState;};  HasAGameStateImpl(actual_storage* GameState_):    GameStateStorage(StateStorage_)  {}public:  // works if your compiler supports covarient return types:  virtual actual_storage* GetGameState()    {return GameStateStorage;}};template<typename actual_storage>class HasAGameImpl : public virtual HasAGame{  // .. pretty the same as above, except:public:  virtual actual_storage* GetGame()    {return GameStorage;}};


The pattern is vaguely functional.

Your Game produces a bound pair of (Game, GameState), which rest of the program acts upon as an object. It has the methods that require knowng about both the Game and the GameState at the same time.

This doesn't replace every double-dispatch problem.

Double-dispatch is when you have a function you want to be virtual in more than one of the arguements. C++ has little support for double-dispatch. It supports single-dispatch via virtual methods.

One could imagine extending C++ to support double dispatch via syntax like:

// a function: (notice the use of the keyword virtual) :std::vector<GameMove> GetSuccessorStates( virtual Game* game, virtual GameState* game_state );// a strange, not-supported in C++, form of overriding:std::vector<GameMove> GetSuccessorStates( virtual TicTacGame* game, virtual TicTacGameState* gamestate );std::vector<GameMove> GetSuccessorStates( virtual ChessGame* game, virtual ChessGame* gamestate );


Lacking the above syntax, double-dispatch problems have to be delt with by the programmer. There are a number of techniques that help solve this problem -- from manual dynamic_cast and switch through to complicated map-based methods, or the above "bind the types together at a level that knows both types".

Topic Locked

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

Sign in to reply to this topic.