Game Tree algorithms

Unity Engine
1

Hi Forum,
it’d be interested in our thoughts about a general software design problem I have with Unity:

Background My background is in machine learning and AI, and I’d like to try Unity for Demos or Visualisations of experiments. However, many decision making algorithms (e.g. Monte Carlo Tree Search, Min Max) in multi-agent simulations rely on so called Game Trees, i.e. a projection of hypothetical game states based on potential actions of an agent, which then can be used to determine the agent’s next action.

I’m currently implementing a simple task planning algorithm that determines the sequence of actions an agent has to take to achieve a certain goal. It basically spans out all possible actions, looks what the resulting effects might be, how close the goal state is, what the possible actions then are etc. etc. However, the decision making algorithm isn’t really my topic here.

Problem Now, my problem is to find an efficient way to represent possible future game states. I figured that just cloning the Unity Scene graph doesn’t do the trick because each time I clone (Instantiate) a GameObject, its adjacent resources (e.g. mesh filter) are cloned as well. So I encapsulated my relevant game data as an object inside a MonoBehaviour script. Then, my agent’s decider queries all objects in a scene for this MonoBehaviour, grabs the data object inside and uses that for building the game tree (the data object implements IClonable). Of course, I have to clone and maintain the relations between the objects as well if necessary. For example, if my agent has to reach a coffee cup on a table, it has to move to the table in a hypothetical state so that it can discover that it has to move in order to reach the cup. But the hypothetical future table has to have a link to a hypothetical future coffee cup or this won’t happen. I hope that explains the idea a bit.

However, what this basically does, is building a parallel scene graph and I end up re-implementing something Unity already does.

So my question would be if anyone could think of a more efficient pattern, or has already tried that?

2

Maybe you could instead represent the possible future game states as a sequence or queue of actions, that you can play back and reverse?

For example, you’d have one sequence that was Move To Table → Grab Cup. To get back to the original state you’d just Put Back Cup → Move Away from Table.

3

Representing the entire scene graph as data is a big ask. Most game designs work by cheating, using a simplified version of the world for AI calculations. Navmesh is one example of this, the actual mesh is far simpler the the visually represented one.

Think MVC. Use a simple model that works with your AI system, then use Unity as your viewer to visualise the system. This visualisation can be far more complex then the actual simulation.

4

I thought about using just deltas, but I still need copies of the GameObjects to observe their states after an action without using the actual object. The reason is, that I have no a priori info about the possible chain of actions, i.e. their is no causal link between moving and grabbing, because I could have moved somewhere else than the table.

But decoupling the AI system from the GameObject scene graph seems like a pretty good idea. Unity doesn’t really seem to be designed for this kind of pattern. I always used my custom game engine code for the visualisation before, but it worked with JMonkey so I thought I could use Unity in the same way. GameObjects apparently can hardly exist outside the master scene graph. Thanks for the feedback though.