Best way to inform Agents of Game state

7a7adca207e7fd8d9b51fa6e83df893a
0
Dark_Storm 101 Mar 26, 2007 at 17:14

I’m looking for tips on the best way to inform agents in a 2d world of the gamestate.

To exist in the game world, all objects implement interface Entity which has only a single method, public void act().

All actions each object need to do are done when the data structure holding all the entities in the game is iterated thru and act() is called on each object.

The clearest way I can see to do this is to add a second method to the interface Entity, public void resolveGameState(Entity[] e), which would be called just before act() and would pass a list of all entities in the world to each entity and let each object implement its own way to parse this data and glean what it needs.

13 Replies

Please log in or register to post a reply.

4e70f904a74bd2aa8773733b25b77d41
0
SigKILL 101 Mar 26, 2007 at 17:39

I have no idea what you’re trying to do, but what is wrong with polling for game state in act()?

What you describe is something that’s O(n\^2) which is not good from a realtime point of view. Your agents will most likely require some specific data anyway, like the states of the nearest enemy or objects in sight etc. So you might want to implement a quadtree and do these things in an efficient manner…

7a7adca207e7fd8d9b51fa6e83df893a
0
Dark_Storm 101 Mar 26, 2007 at 19:32

You are right, my agents need specific data depending on which state (im using a FSM for AI) they are in. A marine unit would only need to do collision detection when it is moving, and when it was sitting still it would need nearest enemy/objects in sight data, and when it is shooting at a specific unit it would only need data on that unit (plus data on any obstacles in the line of fire).

my resolveGameState() method would be implemented by each agent and change according to whatever state they were in so worst case would be O(n\^2) and best case would be O(n) (although it would never reach O(n), actual performance would never be better than 2n).

As far as polling for gamestate, I’d rather not give each agent a pointer to the GameEngine.

In time I will implement a quadtree, but for simplicities sake now, I’m gonna do without. If I were to implement a quadtree, I still don’t see any other way of doing things than to instead of pass it all entities on the map, pass it all entities within its quadtree region + any overlaps but that only reduces collision detection loads, not scanning for nearby objects which is the second biggest performance hit in my engine since each marine needs to constantly know if any enemy units have entered his line of sight and I can’t see how a quadtree would help this.

Thanks for your response!

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Mar 26, 2007 at 19:57

@Dark Storm

As far as polling for gamestate, I’d rather not give each agent a pointer to the GameEngine.

Why not? That’s a common and perfectly reasonable way to do it…you don’t need to expose the entire game engine interface to the entities, you can just make an interface that provides functions specific to entities. Besides, how do entities do things like spawn new entities without talking to the engine?

7a7adca207e7fd8d9b51fa6e83df893a
0
Dark_Storm 101 Mar 26, 2007 at 20:14

Maybe we aren’t talking about the exact same thing here. When I mean game state, I basically mean the locations and boundaries, etc of all other objects in the world relevant to each individual object. A marine would only care about other entities within its line of sight, but to determine which units were in its line of sight it would need to check every other entity in the world. Correct?

So when I call resolveGameState() on each agent and pass them a pointer to the data structure containing all entities in the game, its basically the same as having each agent ask the GameEngine for the same data structure except each agent doesn’t require a pointer and so memory is reduced.

All the computational work that goes into determining collisions, objects in range, etc, is still done by a method within the agent.

I’m interested in any other approaches that may be out there.

Again, thanks for the response.

4e70f904a74bd2aa8773733b25b77d41
0
SigKILL 101 Mar 26, 2007 at 20:51

what you do is the root of all evil. You’ll run into worse problems before that pointer becomes an issue. Why do you need to store a pointer for every entity? Why not pass some class as a parameter to act() which enables the actor to poll? And why would you like the collision detection, objects in range be done in a method within the agent? This sounds like a really bloated design…

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Mar 26, 2007 at 20:54

Well, for the time being it may work to pass the entity a list of all the other entities, but what about when you have enough entities that you want to use a quadtree or something to organize them because searching a plain list would be too slow? Then you won’t want to rewrite the quadtree traversal code in every single entity - rather you’ll want to provide the entity an interface to the game engine by which it can ask for a list of the specific entities it needs (and the engine implements the quadtree searching or whatever). So it seems to me that letting the game engine tell an entity to update itself, then letting entities ask the game engine for the state they need is a much better and more future-proof way to do things (besides being more elegant, frankly).

Write your code for the present, but design your architecture for the future.

7a7adca207e7fd8d9b51fa6e83df893a
0
Dark_Storm 101 Mar 26, 2007 at 21:29

The way I figured it, since the specific data each marine would need would depend on its state, rather than have a bunch of data swapping back and forth between the game engine, this interface object, and the marine itself to determine what state it was in and what data it need, I thought that it would be less cpu intensive to just pass the entity list to each entity and let the entity do what it needed to do since obviously the entity already knows what state it is in.

You do have a point, though, about entities spawning other entities.

The way my design is laid out now, you have the GameEngine which stores the data structure holding all entities in the game. Currently I have it stored as a Vector (i’m programming in Java) but in the future I could implement it as a quadtree.

Each entity itself has only an act() method, and all other attributes, such as mobility, position, etc are added in as extra objects.
So a Marine object woudl implement Entity, but would also have a Movement object that would be passed the marine’s Position object to move it around the map by calling the Movement’s move() method.
I implement Marine this way so that I don’t get unneeded functionality if I later want to implement a missile or a rock or something. Each game object is assigned the attributes it needs and nothing more.
The downfall is that only a marine knows all the attributes of a marine, so the Entity[] list has no way to globally interact with all the entities except act() and type casting.

So since each entity will need very different data, I thought it best to let each entity control how they parse the data.

It isn’t too bloated because each state in the FSM would implements its own resolveGameState() so when the Entity’s resolveGameState() is called, it would in turn call the current state’s resolveGameState() method.

This puts the code relevant to moving, such as collision detection, in the MoveState, nearby object scanning would be in ScanState, and so on. Obviously if there are no collisions when the game begins, the only collisions that will be caused are those that occur with moving objects and those objects will be in MoveState. That reduces collision detection somewhat.

When I implement a quadtree, each quadrant in the quadtree will hold a list of all entities inside that quadrant and so each entity would only be passed a list of entities in the same quadrant.

If I were to implement this interface object, it would have to do the extra work of type casting to the appropriate class, then determining which state the object was in and thus which data it would need. That sounds bloated and unnecessary.

This is just how things are implemented in my program at the moment, feel free to comment on how ridiculous it may be. I am always looking for ways to improve it.

Now that you have a general idea of how my program works, do you still think that putting all the code for determining which entities need what data is more efficient that letting the entities determine for themselves?

How did you guys do it in your own work?

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Mar 26, 2007 at 23:52

I’m not sure you understand the system I was proposing.

Presumably in your engine someplace you have something that loops through the entities and calls an update method each frame (e.g. your act() method). Right now it sounds like you actually call two methods: resolveGameState followed by act. I think the entity interface does not need a resolveGameState function. The entities do not need to be told what the entire game state is each frame. Rather, the entities would each have a pointer to an interface object (they would all point to the same one, and it would be only created once at startup and exist for the entire session), provided by the engine, which contains methods that the entities can call to get different pieces of the state. For instance, it might contain a getEntitiesInRadius() function that would retrieve a list of the entities within a radius of a point.

The execution flow goes like this:
game engine calls act() on each entity
entity’s act() function calls game engine functions through the interface
game engine returns data to entity
entity does some processing, which may include calling more game engine functions for things like moving, spawning, and so forth
act() returns, passing control back into the engine

I think this is a better architecture for several reasons:
* Game state is owned by the engine. If you want to change the internal representation of the game state (e.g. from a list to a quadtree), you don’t need to modify ANY entity code, only the functions implementing the entity-to-engine interface. In your architecture you would need to alter the code in EVERY entity to make this change.
* Similiar to above, if you want to add more information to the game state, all you need to do is add more functions to the interface. It requires no changes to the entity code unless entities need to be aware of the new state. Compare this to your current architecture where adding more state information requires you modify the resolveGameState method of every entity.
* Each entity gets only the data it wants. This can be great savings if for instance you later on decide to network your game and run some entity code on the client and keep the game state on the server. You only need to send a subset of the game state over the network. It can also mean memory savings.
* You can easily expand the entity-to-engine interface in order to allow entities to change things in the game state as well as just looking at the game state - for instance, spawning or moving could be implemented this way.

These are things to consider; ultimately it’s your architecture, but that’s how I would do it and I hope you can see why I consider it better.

7a7adca207e7fd8d9b51fa6e83df893a
0
Dark_Storm 101 Mar 27, 2007 at 00:59

So on each call of act(), it would actually be act(GameStateInterface gsi) where the GameStateInterface object would be stored in the GameEngine and passed to each entity. Each entity would then ask the GameStateInterface object for the data it needed, such as collisions or nearby objects and the GameStateInterface would in turn call methods in the GameEngine?

So rather than each entity iterating thru the list themselves to find the data it needs, it would call a method in the GSI and have the GSI determine the data and return it?

So instead of

for (int index = 0; index < entities.length; index++)
{
   if (this.collidesWith(entity[index])
   {
      collision = entity[index];
      break;
   }
}

if (collision != null)
   //do stuff

I would have

collision = gamestateinterface.checkForCollision();

if (collision != null)
   //do stuff

I can understand this, I think, and I definitely see the potential for network savings. It still sorta seems like just putting the gamestate into an object and giving it methods when the entities themselves could do it for less cpu cost. Don’t get me wrong I am very interested in what you are saying and I am going to implement it to see how it works, I just don’t think I’m absolutely clear on how to apply it.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Mar 27, 2007 at 04:22

Yes, it would be something like that. I actually envisaged giving the entity a reference to the GameStateInterface in the constructor and letting it hold that in a member variable the whole time, but passing it to each call of the method would also work. Also the checkForCollision method would probably take a pointer to the entity, so it would be called like checkForCollision(this).

The CPU cost is absolutely negligible. Doing a few extra virtual calls won’t produce a measurable impact on your performance on a modern PC platform (it might if you were on an embedded platform). In fact, the CPU cost might actually be lower than for your original idea due to cache effects.

7a7adca207e7fd8d9b51fa6e83df893a
0
Dark_Storm 101 Mar 27, 2007 at 18:39

I will take your advice and give a pointer to it in each constructor. Maybe I will change the Entity interface to an abstract class and then require the GameStateInformer in the Entity’s constructor that way it is present in every Entity.

However should the GameStateInformer hold the complete list of entities in a pointer or should that list exist only in the GameEngine and then the GSI object would merely relay method calls to methods in the GameEngine itself.

Or should I reconfigure how the game works and have the GameStateInformer object actually be just the GameState and all entities are stored there. The GameEngine calls for the entity list to run through, or tells the GameState to do it.

If I do give each entity a reference to this singular global GameStateInformer object though, how do pointers work over a network?

4e70f904a74bd2aa8773733b25b77d41
0
SigKILL 101 Mar 27, 2007 at 19:11

@Dark Storm

If I do give each entity a reference to this singular global GameStateInformer object though, how do pointers work over a network?

They don’t, you would typically use ID’s instead.

7a7adca207e7fd8d9b51fa6e83df893a
0
Dark_Storm 101 Mar 28, 2007 at 19:57

Ignore my last post (except you sigkill, thanks for the answer!) I asked some retarded questions that had already been answered.

Thanks for the answers and advice.