In search of the lost Idiom (Refactoring core classes)

[daniel.santos]

Ok, I'm trying to work out the last major kinks in GAEs architecture in relation to the primary objects (Game, Gui, World, Commander, etc.) and network play.  Since these will affect everyone working on the code, I thought it would be a very good idea to run this buy everybody else for feedback.

So here's a summary of my problems:

• The class name Game::Net::GameInterface is supposed to represent a generic "network interface" to the game, but this is a sucky name for it.
• I want a generic method of representing the "interface" (as in where commands & chat messages are sent to and come from), rather it's local or via network.  Currently, code is scattered about that does a lot of NetworkManager::getInstance().isNetworkGame(), and that's both very ugly and rigid.
• The "network interface" object (either Game::Net::ClientInterface or Game::Net::ServerInterface) exists before the Game object (i.e., Game::Game) exists, so it makes it hard for the Game to own it.
• The "network interface" is closely tied to GameSettings from a functional standpoint because it changes when setting up a new network or local game.  However, it too is a core data member of the Game object.  Further, the GameSettings is not static after game play begins either, because a player may disconnect and their faction be re-assigned to an AI, or visa-versa.  (Future features may need support of other dynamic changes to GameSettings as well.)
• It would be nice to have an architecture that will allow the future implementation of "server migration", i.e., allowing somebody else to dynamically become the server (not very feasible with the current design).  Reasons for this could include:
  • the server goes away (crashes, etc.) in a 3 player game and the other two players want to continue
  • it's determined at run-time that one host has a substantially better connection than the current server
  • etc.

So here's what I'm thinking thus far:
Add a new class to the Game namespace named GameConnector.  This will be an abstract class and serve as a source and sink for commands, chat messages and whatever else might potentially go across the network in a network game.  A concrete class named LocalGameConnector will exist to perform the exceedingly simple task of directly delivering commands and chat messages (for those very special players who like to talk to themselves ) locally.  An abstract class named NetworkGameConnector will in replace the current GameInterface in Game::Net and the subclasses will be called NetworkClientConnector and NetworkServerConnector or some such.

Preparing to play a game can involve the following:

• Creating GameSettings
• Changing GameSettings
• Setting up a network server, accepting connections, dropping them, etc.
• Connecting to a server (who's hosting a game) and receiving changes to the GameSettings (as the server changes the settings or new players connect).

Throughout this process, we need to have a Game object in existence to encapsulate the GameConnector and GameSettings, it just doesn't make sense to have those alive without a "Game" concept that they belong to.  However, the current Game class derives from ProgramState and can't exist while any other ProgramState does.  Thus, I propose that the functionality of Game(Play)ProgramState and Game be de-coupled.  As such, the new Game class will be something that can be constructed when you enter a menu in preparation of launching the game and modified as this process continues (maybe only by changes to the GameSettings and GameConnector).  Then the GameProgramState (or GamePlayProgramState) is created at the actual time of launch (which is also then owned by the Game object).

I believe that this will buy me is a clean mechanism to solve the above problems.  Any feedback greatly appreciated!

[daniel.santos]

Hmm, then again, maybe the Game::Gui class should be the ProgramState for in-game play?  It is already handling a large portion of the user interface duties.  I dunno, I guess I need to analyze this more.  Again, any feedback more than welcomed here.

[daniel.santos]

OK, I'm thinking for now, I'm just going to make a very small base class for Game so as to minimize the damage and just note that this is something we might want to get back to at some point (i.e., de-coupling Game's program state & UI stuff from the "I am the game" object).

Code: [Select]

class GameBase {
    GameConnector *connector;
    GameSettings gs;
    shared_ptr<XmlNode> savedGame;
};


[silnarm]

Certainly good food for thought. I like the idea of decoupling the 'meta information' about the game from the actual simulation.  Scenarios might benefit from such a system too.  Need to think on this some more. 

I'm not sure I understand what you're proposing properly, the 'connectors' have me a bit confused, but that may just be the terminology... So this may be conceptually identical, I'm not sure
I Couldn't resist the urge to play with Impress some more, and apparently pictures are worth a thousand words, that's less typing for me



So I think what I've called Game Proxy is the equivalent your Game Base, and the Faction Controllers the equivalent of Game Connector(s?).

GameProxy would be abstract, derived twice for networking (client/server) and once or twice for local games (normal/scenario?)... multi-player scenarios is something to keep in mind for the future too.

The Proxy would hold the game settings and saved game pointer, and the (possibly NULL) Game pointer, and would 'connect' to all the faction controllers.  How much it needs to do depends on its specific type.  In this model, the Local/Scenario GameProxy is the simplest, just routing commands straight to the Game. 
The Networked Proxies require some re-routing, the Client Proxy would be responsible for receiving local commands/messages and sending them to the server (and local Game?) and receiving commands from the server and sending them onto the game.
The Server Proxy would need to receive commands from all controllers, 'process' them (decide what frame this will take effect, etc) and then send it back out to all the network controllers and on to it's own Game.

So in effect, the Faction Controllers are the source of all commands, from the Faction Controller's point of view, it sends all commands/messages to the local GameProxy.
The Proxy decides what to do with commands coming from various sources depending on context (ie, its concrete class), and ultimately forwards commands to the local Game object (or changes GameSettings, sets a saved game, etc if the Game doesn't exist yet).

So that's my initial thoughts anyway... this is a worthwhile endeavour I think, whether there should even be a class called Game may be something to discuss too   

[hailstone]

What about a player centric approach where you update a player representative and it updates all the players?

[daniel.santos]

Hey, I'm sorry I haven't responded to this yet, I've had a lot going on, but this is at the top of my list for GAE development right now.  Also, you didn't properly understand what I was saying and have subsequently given me new ideas to think about!  I made a UML class diagram a few days ago, but since then, I gave up on the idea of de-coupling the game state & UI from the Game, so it's already out dated.  I usually host images on my own server (*sniff*  :'( ), so I finally created a goddam photobucket account (and it tried to get my personal info, I presume to spam me).

Connector, Interface, Proxy? (Local game, vs Network Client or Server)
So I guess the actual design pattern name I'm looking for, that I've called "connector" is really a Strategy to facilitate the connection between the command endpoints (producers and consumers).  The thing is that every host in a game will consume commands generated by every other host, so this is a distribution issue.  Thus, commands host A generates will be consumed by hosts B and C, commands host B generates will be consumed by hosts A and B, etc.  The same is generally true for chat messages, except that they can be selectively routed (i.e., if you're chatting with your team, you don't send a copy to hosts who aren't playing on your team).  I'm not settled on the name "connector".  Just like the term "interface", it seems to create confusion.

What is important here is that we have an abstract base class that everybody uses and we de-couple the logic of implementing the game across the network from the rest of the code as much as possible.  I'm actually responsible for introducing a lot of this into the UnitUpdater, but I'm not overly happy with the network strategy I was shooting for earlier.  What I did manage to preserve with my previous network play implementation is that commands that all hosts give to units are executed on their machines immediately, taking away from some of the feeling of lag.  I'm still open to this approach in the future, but I want the new paradigm to work 1st and then we can go back and see what we can optionally turn on and off (from the older paradigm) -- I'm not going to worry about that too much right now.  The only thing I might re-use from the older paradigm right now is the way new units are created on clients because the alternative is making GAE tolerant of unit IDs being inconsistent for a period of time and I'm not screwing with that.

So what should we call this layer "local vs network" layer?

Scenarios and Network Play
Actually, I've been designing the new network code to work with scenarios from the start, so there should be no distinction in the "network vs local" layer as to rather or not a scenario is present.  I've already merged the trunk into the network branch so it has all of the Lua stuff (minus the extensions of course).  I'm not going 100% scenario support in network games initially however.  This is what it will lack:

• A mechanism for Lua-generated random numbers to be synchronized
• A mechanism for stateful Lua variables to be synchronized

The optimal solution will probably be to provide an interface to Lua for scripts to store and retrieve stateful variables, create random number generators and retrieve random numbers from those generators.  Then, when the network code is doing its synchronization stuff (described in the revised network paradigm thread) the client can create hashes for these objects and the server can validate them and possibly send corrections to clients that get out of sync.  But something like this will be needed for meaningful mods written in Lua anyway.  Specifically, the ability to store custom values globally and at the at the levels of the unit, faction and team (we may discover other scopes that are appropriate as well).

Faction Controllers (Local, Server, Client and AI)

What about a player centric approach where you update a player representative and it updates all the players?

Hailstone, I'm not sure what you mean here, but I need to draw a terminology distinction.  You may have noticed in the map editor that I changed the word "Player" to "Faction" everywhere.  This is because, starting with the network re-write, multiple players can control a single faction.  So Faction will be the concept we formerly considered a player, they belong to a team, they get starting units and a start location on the map, they have their own resources, etc.  I've been using the term Player to describe somebody who is controlling a faction.  So now, when you build a GameSettings object, you first add Teams, then you add Factions to those Teams, then you add Players to those Factions.  Here's a UML diagram of how it looks now:



Should they be called FactionControllers instead, as Silnarm suggests?  It would seem to clarify things.  However, at this level, if they are a human player, I don't care if they are the server or the client -- each will have identical control of their respective factions.  This code also doesn't currently distinguish between local and remote "players" (or "controllers").  However, when playing a local game, the networkInfo is never populated.  Interestingly, the class Host derives from NetworkInfo and, in a network game, the HumanPlayer's networkInfo data member is actually populated with a pointer to the Host object (which is also abstract and is actually one of several different sub-types).

EDIT: Clarification!  Also what's different here is that these classes are more data-centric than behavioral.  Both in original Glest & GAE, there isn't anything special from one faction/player/controller to the next as to where there commands can go to, since each command has a UnitReference embedded in it and there is always a one to one relationship between the Command object the the Unit that's commanded.  When you have multiple units selected and you issue an order, it creates a single command for each unit you have selected.  The member function Commander::giveCommand() is where these commands are actually issued (locally).  I'm guessing, at this point, that this is OK, but I'm certainly open.

GameProxy
Actually, I wasn't thinking about making this an abstract class, so I'll have to consider this possibility.  I like the idea of having it own the Game (possibly a NULL pointer).  That way, the same object can be brought into existence as soon as the user enters a menu that can lead to game play and stay in existence until the game is over and the Battle Ending screen is exited.  While we're at it, this class can hold the Stats as well, which the Battle Ending screen also needs and I've been shuffling around in a tedious fashion.

Now that I think about it more, what I don't like about making this class abstract and sub-classing for local, network client and network server roles is that it will kill our ability to transform those roles dynamically.  I mean, it's true we can be a network server and if a client disconnects and the player wants to finish the game out with the AI playing the former player's role, he can just be playing as a server with no connections (like it does now actually).  But this wont work if they are a client, we would have to transform them into a "local" game (or maybe a server with nobody connected  to give the other player a chance to re-connect).  But the main reason for this functionality is to dynamically migrate the game to a different server.

So here's a revised diagram (still using the "Connector") name.

And I don't like the name GameRoot either.  Below is roughly what the "connector" would look like:

Code: [Select]

class GameConnector : private Uncopyable {
public:
    virtual ~GameConnector() {}
    virtual void postCommand(Command *command) = 0;
    virtual void postTextMessage(const string &text, int teamId) = 0;
};
Note that the Command class will probably have "targetFrame" added to it.  If not, then it will be a parameter of the postCommand() function.

So the menu will create the "GameRoot" object to setup the game (connections, settings, load saved game and scenario if any).  Then, when it launches, the GameRoot can manage creating the actual Game object and such.  Maybe we can call this GameManager and give it all of the responsibilities for "managing" the game play state?  I don't mean to derive it from ProgramState, just from a behavioural perspective.

AI Controller
I should note here that in the original Glest as well as current and planned GAE networking, AI code is executed on all hosts of the game.  Martiño's original plan to keep this in sync is to use a custom psudo-random number generator so that (in theory) each host would generate the same numbers when seeded with the same seed.  However, inconsistencies with networking can cause this to get out of sync.  So part of my "client sync" I described in the networking thread is to make sure that each AI's random number generator is at the same value across hosts.  If everything else is in sync, they should behave exactly the same across hosts.

Proxies
Finally, this is another old diagram of the new networking classes.  I posted this in the other thread, but with codemonger.org down, it wont show, so here's the photobucket copy.  I don't have time to re-do it right now, but just know that I nixed RemoteHost and replaced it with RemotePeerInterface directly, instead of having RemotePeerInterface inherit from RemoteHost.  I also made Host derive from NetworkInfo, so all of those data members are now in the base class.  Finally, I renamed {Game,Server,Client}Interface to {Game,Server,Client}Connector and will probably rename it again.



I think that what I previously called RemotePeerInterface is best called something-Proxy.  Ditto for each of the subclasses.  Here, "peer" is an abstraction of client or server, but can also represent a real "peer", which is the connection between two clients.  I think there's still room for improvement here, but I don't have time to get into that at the moment.

Please let me know what you think and thanks for all of the feedback, it's been exceptionally helpful!!!!

[daniel.santos]

What about a player centric approach where you update a player representative and it updates all the players?

Ooh, I think I know what you mean now.  Are you talking about when you have 3 hosts in a network game one client gives a command, but isn't directly connected to the other client so lets the server route the command?  I was starting to think that that functionality should be encapsulated in it's own class somehow, but I'm not fully certain.  It's very good food for thought!  As it was, I was just going to have the "ServerConnector" class route the command if the client doesn't claim to be connected to another client.  The connect state between clients is transmitted in the header of most messages now, since it's only a few bytes (well, one byte for now, but it will be two bytes when we support up to 16 players).

See the definition for the NetworkPlayerStatus class for more details on this, but note that this class will be changed again because the "game parameter change" functionality will be removed from it, put in it's own message class and made more flexible because there are more game parameters besides game speed and pause on/off that may potentially need to be changed and there are a lot of rules that players may want to set on how this occurs (or doesn't) in a network game.

But the point is that clients will attempt to connect to each other (to reduce latency and, thus, the delay enforced on all commands).  With each message, they report their connection state to the server (and eachother, but I don't think peers will give a damn).  if a client issues a command at any time they are not connected to another client (peer), this info is in the message and the server will route the commands.

[hailstone]

Not sure if this would be any good for message sending.

[daniel.santos]

Messenger!  That's what we should call it!  Somewhere in Effective C++ Scott Meyers goes into this long "what's in a name?" discussion, and I'm glad because it validates the way I feel.  I think that names are very important to be as accurate as possible, especially since they tend to drive the design.  How we code a class is influenced on the linguistic terms we use for them.

And by the way, if somebody finds a nice stable version of Umbrello, let me know.  This thing crashes constantly right now, but it does cool stuff when it's not crashing!


So here, I've included more of the networking classes and actually got Umbrello to import my Host and NetworkInfo classes (only showing data members right now).  So the NetworkMessenger class owns the proxies.

Dedicated Server?
However, all of this discussion is causing me to consider something drastically different, and that's probably a very good thing.  So what if we scrapped this architecture, made everybody a client and then made a dedicated server, the way most FPS games work?  In other words, we implement the "server" as a stand-alone concept.  The server may actually live in the same process as the game where a client is playing, but it also has the option of running it as a dedicated server in it's on process on a different machine than those where humans are actually playing.

Advantages

• Majorly simplifies networking code for execution of the game (where players will play) -- because everybody is a client, we wont have to treat things any differently on the machine that happens to be hosting the game.
• Opens up more possibilities.  Example, players connect to some centralised server to find players and they launch the game from there, allowing the server to host the game.  Maybe they set up game rules so that the AI initially plays a few factions, but other players can join and leave, taking ownership of those AI-controlled factions.  This type of thing is more common in FPS-style games, but there are a lot of possibilities.
• De-couples the rolls of "network game controller/manager" from the "network game player".  This is largely de-coupled through abstraction of the
  
• It will expose a lot problems in the current design, such as enmeshed rolls and overly-rigid designs like Singleton over-use.

Disadvantages/Challenges

• We'll be forced to fix whatever problems it exposes.
• Unless we do something snappy, whomever is hosting the game will have a larger CPU load with the current model, because AI and pathfinding will happen in both the server & the client.  Since this model will make the person hosting the game both a client & a server, their load from AI and pathfinding will double.
• It's more work, but may reduce the amount of work it takes in the future to maintain the code.

Mitigating patherfinder load (i.e., "something snappy")
I think I have an idea for mitigating the CPU load, but Silnarm will have to sanity-check it for me.  Whenever a command is requested on any client, even though the command is actually scheduled for the future, the client can execute the pathfinding and send the tentative path out with the commands.  This will save each client (and the server) from having to calculate this themselves.  Although it's possible that by the time the command needs to be executed all or part of the pre-calculated path may have become invalid, it will probably be valid over 90% of the time.  I suppose it's also possible for the server to perform pathfinding for the AIs, and set that info out in advance to aid in reducing the CPU load for clients.  Would it be worth the reduced CPU load?  I don't know and I don't want to pursue it unless we're pretty sure it's worth it.

One note on the network size of adding a pre-calculated path, this can be exceedingly small.  With my new Int30 class, unsigned number less than 128 take one byte.

Code: [Select]

enum PathStep {
    NO_CHANGE = 0,
    MINUS_ONE = 1,
    PLUS_ONE = 2
};
Int30 startX;  /**< The starting X position (1-2 bytes) */
Int30 startY;  /**< The starting Y position (1-2 bytes) */
Int30 size;   /**< How many steps are in this path (probably 1 byte) */
// these repeat ( (size + 1) / 2 ) times, so each byte contains two steps in the path
byte step1X:2;
byte step1Y:2;
byte step2X:2;
byte step2Y:2;

We probably wouldn't store it like that, but that's how it would look on the network.  I'm guessing that most of the "misses" (when the pre-calculated path doesn't work by the time it's executed) will be due to the start location having changed, if the unit was moving when the command & pre-calculated path was generated.  This can probably be mitigated by checking the 1st few steps of the path to see if the current start unit location is in the path.  Maybe there can even be a specialized pathfinder algorithm that will try to pick this up (like see if I can path to the 2nd or 3rd node in the pre-calculated path)?

Memory & CPU
Also, as far as CPU and memory usage of the dedicated server is concerned, remember that it will be substantially less than running the normal game because we wont be:

• loading model data, textures or sounds into memory
• animating models (interpolation)
• rendering
• screwing with UI

Server and AI
Rather or not we use a dedicated server, I'm starting to consider the possibility/plausibility of only having the server run the AI Controller (like both of you have modeled).  It could definitely simplify things and leave the client with less CPU overhead.  The AI doesn't use much CPU at all right now.  That's not actually a terribly good thing either, because it's partially due to the fact that the AI isn't thinking much!  None the less, here's what I'm thinking:

• So-called "auto-commands" (attack, repair, flee) are still generated on each client and fed to themselves locally.  I believe that with the current GAE networking, auto-commands are never transmitted because we presume that everybody else generated them.
• AI-generated commands are transmitted from the server, with a command lead-time, just like every other human player does.

So this will increase total bandwidth used, but Commands are very skinny on the network (4 to 14 bytes each) and all Commands generated in a single server frame are always sent together in one NetworkMessageCommandList, so that overhead is kept to a minimum.  We can even look at zlib-compressing them, but I'm not thinking it would be worth-while.

[daniel.santos]

One more note about the dedicated server idea.  I'm working on actually implementing the ideas we've discussed for the Game classes, using the name "GameManager" for the class that will be instantiated from the menus, etc.  The class Game::Program is heavily tied to the UI as it derives from GlWindow, etc.  So supporting 100% de-coupling to have a dedicated server process (with no windows) will take the complete de-coupling of the Game class from the ProgramState, Gui, etc.  I don't want to screw with this part now and I think we have enough for me to cleanly implement the networking.

I'm still a bit up in the air on rather or not to support it from the networking layer, though, I would like to get you guys' feedback first.  Maybe for now, I can find a way to implement everything in the networking layer so that the "server" functionality is as encapsulated as possible and can later be made into a true dedicated server later on.

[silnarm]

Mitigating patherfinder load (i.e., "something snappy")
I think I have an idea for mitigating the CPU load, but Silnarm will have to sanity-check it for me.  Whenever a command is requested on any client, even though the command is actually scheduled for the future, the client can execute the pathfinding and send the tentative path out with the commands.  This will save each client (and the server) from having to calculate this themselves.  Although it's possible that by the time the command needs to be executed all or part of the pre-calculated path may have become invalid, it will probably be valid over 90% of the time.  I suppose it's also possible for the server to perform pathfinding for the AIs, and set that info out in advance to aid in reducing the CPU load for clients.  Would it be worth the reduced CPU load?  I don't know and I don't want to pursue it unless we're pretty sure it's worth it.

With four players I don't think it would be a problem to have all clients calculate paths, but with up to 16, it would be most wise to have the path calculated by the command issuer in advance.

One note on the network size of adding a pre-calculated path, this can be exceedingly small.  With my new Int30 class, unsigned number less than 128 take one byte.

Or possibly even run length encoding,

Code: [Select]

struct PathSegment {
    uint8 direction: 3;
    uint8 length: 5;
};


We probably wouldn't store it like that, but that's how it would look on the network.  I'm guessing that most of the "misses" (when the pre-calculated path doesn't work by the time it's executed) will be due to the start location having changed, if the unit was moving when the command & pre-calculated path was generated.  This can probably be mitigated by checking the 1st few steps of the path to see if the current start unit location is in the path.  Maybe there can even be a specialized pathfinder algorithm that will try to pick this up (like see if I can path to the 2nd or 3rd node in the pre-calculated path)?

There is 'local repair' in the pathfinder branch already, small paths are actually exceedingly cheap, so it might make sense to just send the 'full' calculated path, and if something is screwy with it when it comes to using it, all clients can repair it themselves.

Server and AI
Rather or not we use a dedicated server, I'm starting to consider the possibility/plausibility of only having the server run the AI Controller (like both of you have modeled).  It could definitely simplify things and leave the client with less CPU overhead.  The AI doesn't use much CPU at all right now.  That's not actually a terribly good thing either, because it's partially due to the fact that the AI isn't thinking much!  None the less, here's what I'm thinking:

I have one souped-up tool at my disposal now, in the form of the SearchEngine, which is far, far more than just a path finder.  I'll have some other new tools to go with it in the not to distant future... AI CPU load may raise substantially within the next few months :-)

I think ideally, any player would be able to run any AI, so for example a 4 player game with two humans might run the two AIs both on the 'server' if it were the significantly more powerful machine, or the humans might share the load, and run one AI each.

• So-called "auto-commands" (attack, repair, flee) are still generated on each client and fed to themselves locally.  I believe that with the current GAE networking, auto-commands are never transmitted because we presume that everybody else generated them.

This strikes me as a dangerous assumption, there will always be slight synchronisation problems, with numerous units in close proximity to each other, auto-attacks in particular could be generated quite differently in each simulation.

In general, I certainly like the dedicated server model, I can't really give you any good feedback on it though atm, I've had my head stuck in Game::Search

[daniel.santos]

• So-called "auto-commands" (attack, repair, flee) are still generated on each client and fed to themselves locally.  I believe that with the current GAE networking, auto-commands are never transmitted because we presume that everybody else generated them.

This strikes me as a dangerous assumption, there will always be slight synchronisation problems, with numerous units in close proximity to each other, auto-attacks in particular could be generated quite differently in each simulation.

In general, I certainly like the dedicated server model, I can't really give you any good feedback on it though atm, I've had my head stuck in Game::Search

Ahh, well then especially thanks for taking the time and brain room to give feedback on this!

Actually, with the new multiplayer model, each game should always be exactly in sync unless:

• The CPU load on a machine rises too high and an insufficient number of server frames execute per second (I think they call them "world" frames in Glest)
• A command (or set of commands) arrives late.

Command should generally not arrive late.  When they do, each receiver will fast forward the command(s) (clients for sure, I'm not certain we'll do this on the server) and this triggers a "lets make sure that didn't screw things up" procedure where clients send checksums to the server, which can potentially trigger a "stop the world" re-sync.

SearchEngine
As far as the Search engine, I've been trying to find a long thing I wrote up about AI and "annotated paths" or some such.  This was basically a concept for an extension to the path-finding engine where you pass extra parameters to give restrictions on the path and you specify that you want information about the path when you receive it.  Similar (or the same?) to what you've already implemented, it would require each team to have a map of non-visible areas where it stores the last-known contents of those cells (enemy units, buildings, etc).  Slightly off-topic, the renderer should render these units (or at least the buildings & walls) when the area is not visible anymore.

So I'll try to remember the basic proposed features (listed below).  If you're going to be working on the AI soon, I want to bring this up now so you can take any opportunities to add stuff when you're already in the code (personally, I find it easier that way).  Plus, maybe you can find use of some of my ideas in your own, making an even better idea (well, ideally ).

Path Query Parameters

• Generate the most direct path (even if it's through enemy units/walls/buildings, etc.).  This can be useful when an AI has a very large army with siege machinery and wants to perform a blitz on you, blazing it's own trail.  The idea of this blitz attack is that the AI should have amassed a large force and it doesn't want to give you any time to pick them off, as it probably would if it attempted to navigate a less obstructed path.  Also, with a large force, it would probably breach defences quickly.
  
• Generate a path that may travel through enemy units/walls/buildings, but prefer open nodes.
• Same as above, but also choose the weakest units to path through when open nodes aren't available.  I don't know that we would ever use the above, without this parameter, but they are logically different, so I thought it should be separate.
• Avoid visible enemy units (any, military, etc.)
• Avoid last-known locations of enemy buildings
• Avoid last-known locations of all enemy units
• Stay as far as possible from known enemy bases (in hopes of avoiding any scouts, workers, etc.).

Path meta-data (what the pathfinder returns if you ask for it)

• A list of known (i.e., "visible") and/or last-known enemies that can see the path and their distance to the path (at their closest).
• Various sums for the above:
  
  • Total hit points
  • Total hit points of units that can hurt you (can attack the field you're traveling in)
  • Total attack value (their attack damage to speed ratio adjusted)
  • Total attack value, adjusted for your armor.
• A list of friendly units near the path.
• Various sums for the above (similar to data for enemy units):
  
  • Total hit points
  • Total hit points that can harm units in the enemies list (above)
  • Total attack value that can harm units in the enemies list.
  • Total repair value of units that can heal you.

That's a rough list and I want to find the original thread eventually.  This was in one of my brain-storming sessions on how to make better AI decisions.  But the basic idea is that you don't ask this information each time you want a path.  Instead, the AI code will make these queries when it's trying to make decisions.  If it thinks it wants to attack, it can check a path between the center of it's forces and where it wants to attack and see if it looks like it would win or not.  If the path finder shows that they have more hitpoints of military units and a higher attack value, than the total of its own forces, then the AI can wait for a better opportunity.  I realize that this approach to AI assessment is still quite rudimentary,  It would be better if it divided the data up into segments of the path, so you wont assume you can get heals from units that you wont encounter at the time you encounter the enemy, but this would be a nice start.

But perhaps the most important part of this exercise (at the time) was to give a way for the AI to deal with walls -- ignore them, unless they are in the way.

[daniel.santos]

Not sure if this would be any good for message sending.

Hey, sorry I didn't respond to this yet!   Right now, each Game::Net::GameInterface (which I'm renaming to Game::Net::NetworkMessenger, a sub-class of Game::Messenger) has a single queue for incoming commands for all factions.  Since the Command specifies the unit that is commanded, we don't have to track it by unit or faction.  (Note: the below typedefs are probably poorly named.)

Code: [Select]

class NetworkMessenger : public Game::Messenger, public Host, private Thread {
public:
    typedef queue<shared_ptr<Command> > Commands;
    typedef map<int, Commands> CommandQueue;

private:
    Commands requestedCommands;  /**< Commands requested locally */
    CommandQueue futureCommands; /**< Commands (incoming and local) queued up for future execution */
    Commands pendingCommands;    /**< Commands (ready to be executed) */
    ChatMessages chatMessages;   /**< Incoming chat messages */
    int commandLeadTime;
// etc...
}

So the requestedCommands is populated when the ProgramState posts keyboard & mouse input (which goes to Game and then Gui) and then the Gui class issues commands.  At the end of each world frame (or maybe even when the commands are manually issued, not sure yet), the commandLeadTime (dictated by the server) is applied to determine the command's target frame, the commands are packed into a NetworkMessageCommandList object and transmitted.  Finally, the commands are added to futureCommands, so that they are mapped to the target frame.

We have our own networking thread now, so as soon as a complete message arrives, it is processed (no waiting for the world frame or some such).  So when the world frame starts, it calls Messenger::beginUpdate(int frame).  If the NetworkMessenger has commands due on that frame, it removes them from futureCommands and adds them to pendingCommands, so that the world update code can access them (or directly delivers them or something).

I'm glad you brought up spectator though!  I need to make sure I keep this in mind during this redesign process.

[silnarm]

Actually, with the new multiplayer model, each game should always be exactly in sync unless:

Ahh, ok... I need to check out what you're up to a little more closely

• Generate the most direct path (even if it's through enemy units/walls/buildings, etc.).  This can be useful when an AI has a very large army with siege machinery and wants to perform a blitz on you, blazing it's own trail.  The idea of this blitz attack is that the AI should have amassed a large force and it doesn't want to give you any time to pick them off, as it probably would if it attempted to navigate a less obstructed path.  Also, with a large force, it would probably breach defences quickly.
  
• Generate a path that may travel through enemy units/walls/buildings, but prefer open nodes.
• Same as above, but also choose the weakest units to path through when open nodes aren't available.  I don't know that we would ever use the above, without this parameter, but they are logically different, so I thought it should be separate.
• Avoid visible enemy units (any, military, etc.)
• Avoid last-known locations of enemy buildings
• Avoid last-known locations of all enemy units
• Stay as far as possible from known enemy bases (in hopes of avoiding any scouts, workers, etc.).

The 'effect' of these can be achieved with Influence mapping, the data will be less specific (less detailed) than some of what you want here, but the net effect should be very similar.  I have three types of Influence Map I want to introduce, I've been building them in a test project, as I'm scared Hailstone might scold me for overuse of templates I've made use of the Curiously Recurring Template Pattern to gain static polymorphism.

The three types of InfluenceMap I have so far are, FloatMap (a map of floats), PatchMap (bit packed(template param) uint8 map) and FlowMap (bit packed 'direction' map).

Most of what you want would probably use a 'traditional' InfluenceMap, which from my collection would be a FloatMap, filled in with positive values for military strength of your own and allies units, and negative values for visible enemies, recently seen enemies, enemy base "projections", and a 'fear of dark' factor.

Path meta-data (what the pathfinder returns if you ask for it)

Using the influence map, hopefully the need for much of this would be obviated, however there are some things in there that would be nice, and probably couldn't have their effects simulated with the traditional influence map, but I think Influence mapping is ultimately the way to go, I think for example the hit points and attack values things could be simulated with specially constructed PatchMaps.

The key thing to remember here is, while specifics are very good to get you thinking about the problem, we need to keep generic here, in particular I don't think we want to be counting attack values versus our armour values along a potential path, simulate the effect with cheaper & easier methods.  We don't want to build an expert system here.

Influence Maps are just the ticket!

[daniel.santos]

Cool!  I trust you on this.  I think you get the point of what I'm getting at so I'll let you go about in whatever genius fashion you see fit.   I remember CRTP, I actually read a bit about it a few weeks ago.

[silnarm]

No need to trust me, just give it some time and hopefully you can see for yourself   I've been adding a lot of doco to the Game::Search namespace recently, admittedly not much that would make too much sense to anyone not very familiar with heuristic search (ie, A* & Dijkstra search), but I'm not done yet... and once I've documented the 'users' of the SearchEngine properly (with examples), you may even want to give it a spin yourself

But as to Influence Maps, I might put it off actually using them for a little while... I still have a few things to do to get the RoutePlanner (formerly known as PathFinder) back up to scratch, then I wouldn't mind spending some time checking in on Hailstones and your own work.

atm, I have my usual problem of doing too much at once in the pathfinder branch, I'm moving the explored & visible state information into the (new) Cartographer object, to lump everything of interest to A* together to get better caching, and because I like the idea of a 'Cartographer' that manages all such map related information.  But it was previously done by polling every tick (once a second), clearing the previous state and recalculating by iterating through every unit and applying its visibility. I didn't like that much, so I re-implemented it using Dijkstra searches to de-apply and re-apply visibility when a unit moves across a tile boundary (and when they are born and die, of course).  So the visibility status is always perfectly up to date.

Also... I started trying to make a unit test for the AnnotatedMap, and quickly hit the 'externals required' problem, so there are parts of it I can test in isolation, but to test it properly, I need a World to plug into it.  So I think the decoupling of the game simulation from the rest of the program needs to be brought back onto the table, sooner rather than later, or at least, preferably

[daniel.santos]

I didn't like that much, so I re-implemented it using Dijkstra searches to de-apply and re-apply visibility when a unit moves across a tile boundary (and when they are born and die, of course).  So the visibility status is always perfectly up to date.

Ahh, most cool!

Also... I started trying to make a unit test for the AnnotatedMap, and quickly hit the 'externals required' problem, so there are parts of it I can test in isolation, but to test it properly, I need a World to plug into it.  So I think the decoupling of the game simulation from the rest of the program needs to be brought back onto the table, sooner rather than later, or at least, preferably

Yea, I was starting to get that impression, especially when I started looking at what it would take to make a dedicated server process.  I need World de-coupled for a scenario editor.  I also need Game de-coupled for that, but I'm getting part of that with the GameManager.  Maybe I'll take a small break from what I'm doing, check out the pathfinder branch and do the World de-coupling.  Then I can cherry-pick that into the network branch as well.

[daniel.santos]

ok, so I lied.  I don't think I'm going to de-couple the World in the pathfinder branch.   The main reason for this is that loading the Tileset, FactionTree, etc. invloves loading a lot of media files (sounds, textures, models, etc.) into memory and I want that split up so I can have a dedicated server process that doesn't load crap I don't want.  Thus, I propose we alter the load(const string &dir, Checksums &checksums) standard mechanism to have separate load() and a loadMedia() functions.  Further, this would be a good time to figure out a cleaner way to do XML validation.  Let me know if you have any good ideas for this because I don't yet.   But I'm going to do this now in the network branch and then (hopefully) we can merge that part over to the pathfinder branch.

I will, however, check out the pathfinder branch again (here at home) and re-fix a few items that will fix gcc compilation issues (if you haven't gotten them already).  I re-added an operator unsigned int() to the Enum class to get it to compile, but I like your approach better if we can get it to work.  I'm rather eager to use it to encapsulate stuff like the KeyCode enum in shared_lib/include/platform/input.h because, in my IDE, it shows all of the enum values when I'm browsing classes and it's very annoying.

[silnarm]

I will, however, check out the pathfinder branch again (here at home) and re-fix a few items that will fix gcc compilation issues (if you haven't gotten them already).  I re-added an operator unsigned int() to the Enum class to get it to compile, but I like your approach better if we can get it to work.  I'm rather eager to use it to encapsulate stuff like the KeyCode enum in shared_lib/include/platform/input.h because, in my IDE, it shows all of the enum values when I'm browsing classes and it's very annoying.

I have had a few RL things preventing me from working on GAE at all this last week, but I'll be checking this one out today... As best I can tell, everything I've added is standard C++, so hopefully we can get this one sorted :-)

[daniel.santos]

OK, this is just a heads up.  As I'm working on some of the refactoring for the network branch, I decided that some of this should just be done in the trunk (and then I'll merge it over to the network branch).  So let me tell you what I'm doing:



Program will become an abstract base class of the ConsoleProgram and GuiProgram.  ConsoleProgram will be used later on for the dedicated server.  The following classes will loose their singleton status (along with their static getInstance() methods):

• Config
• Lang
• Console
• Metrics
• Renderer
• SoundRenderer
• CoreData

Instead, each of these will be retrieved from the Program or GuiProgram object.  That is as deep as I intend going on the trunk, the rest of the changes will only be in the network branch.  The main reason I want to do this in the trunk is that I'm also going to chop up the Shared::PlatformWindowGl class and to some extent, Window as well, and I need to be able to test them.  Also, it just make sense and it will leave less work for merging the network branch into the trunk later.

EDIT: Clarification: The SDL implementation of WindowGl has some uglies in it (this "Private" namespace for example) and I'm getting rid of all of that.  I'm adding proper constructors to Window and WindowGl so that all of their initialization information can be passed to a constructor instead of after the object is created.  I'm leaving the default constructors in place, however.  This way, when execution returns from calling the Window's full constructor, the window will be completely created, initialized, sized, positioned and, if running in full screen, the screen resolution set.  In addition, when calling WindowGl, the OpenGL context will have been initialized.  In the future, we need to add support for anti-aliasing frame buffers, and this should be done in one of these two classes.

[silnarm]

Where does this all leave the Commander ?

I'm trying to finish up work on the RoutePlanner, for long and 'group' paths, and my travels have seen me deposited in Commander for the human, and looking at a messy road ahead for the AI.

In short, I need the Commander object as it now exists to continue existing, with some new functionality, and I would like to make one for AIs as well...

It might fit in somewhat like this,


I need to pre-process commands, and handle group commands before they get 'separated' into individual commands, as indicated above, the Commander would then forward the commands (with precalculated paths) to the Connector/Messenger object. [Did you decide on 'Messenger' ?]

This would only be done for locally controlled factions, the HumanCommander would be hooked up to the Gui (or perhaps the Gui becomes the HumanCommander) and AiCommanders would link with AiInterfaces (or, again, the AiInterface becomes an AiCommander aswell). Commands from the network will have had similar treatment on their originating machine.

[daniel.santos]

I hadn't planned on altering the commander at all really, only the code feeding it commands from the networking layer (the whole command queue thing I discussed earlier in the networking threads).  So anything you want to do to it, please go right ahead. =)

If you think there's value in keeping commands issued to groups of units together as one entity, then please state your case, I'm not ideologically opposed to that or altering the network messages if there's a good pay off for it.  But the pre-calculated paths, I'm thinking is a good idea.  I've also been considering attaching a small amount of the unit state with each command.  This would be the state of the unit at the time the command is executed (not at the time it was given).  So if the command lead time is 300 milliseconds, then I'm talking about where that unit will be in 300 milliseconds (so the client will have to project that) and this is only:

• x, y position (4 bytes max)
• skill (1 byte)
• progress on skill (maybe 2 bytes)
• if moving, next x, y position (actually the offset, it fits in one byte)

And realistically, this can be fit into about 8 bytes on the network, so it wouldn't be an unwieldy payload to add to a command and it would help with assuring synchronization and mostly remove the need to re-wind a skill if the command arrives late.  Late commands can still lead to inconsistency, so all the stuff I mentioned in the new network paradigm threads about the "resync" still applies, but it will reduce the chances of that need and make it look much smoother.

[silnarm]

If you think there's value in keeping commands issued to groups of units together as one entity, then please state your case, I'm not ideologically opposed to that or altering the network messages if there's a good pay off for it.  But the pre-calculated paths, I'm thinking is a good idea.  ...

No need to keep them grouped, I just want to pre-process the group, because I can (literally) calculate all the paths 'at once'.  Once the pre-processing is done there is no need for them to grouped, so there'll be no need for changes elsewhere, I just thought/assumed you had plans for the Commander and wanted to make sure we weren't pulling in different directions

[daniel.santos]

Groovy! And I really like the idea of calculating all of the paths at once.  Since each client will receive the commands for each unit individually (and ungrouped) it's all the better that we're pre-calculating the paths -- it definitely makes a lot of sense!  I finally read through all of your A* stuff and I really like it! =)