Jump to content
  • Advertisement
Sign in to follow this  
captain_crunch

Production graph prediction

This topic is 1123 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

In my game, I have an extensive production graph that defines what the player can produce in-game. The edges are processes, the nodes are entity types. A process can have inputs, outputs and require tools, all of which are entity types.

I would like for the player to see next to each entity type, whether it is attainable. To do this, I am using a naive approach with a depth first search for each entity type. The problem is that this won't work when there are loops in the production graph.

Which other algorithm is useful here? Note that I am disregarding the amounts needed,  I am just looking to give a hint about what is possible to attain, so any item that is present in greater than 0 amounts will be attainable, and fulfill the next process step.

Share this post


Link to post
Share on other sites
Advertisement
If you keep track of reached entities in your search, and don't search such nodes again, you should be fine, unless you have an infinite graph smile.png

"keeping track" can be a bit in each node, or a separate set of visited nodes, or some other form of storage where you can decide whether a node has been visited.

Share this post


Link to post
Share on other sites

I have a collection where I store the attainable results for each node. What about nodes that are currently being evaluated? When the search reaches such nodes (again) what should it do? Returning "not attainable" would give the wrong result for the starting node.

Share this post


Link to post
Share on other sites
Traverse the entire graph at once, storing the attainability result for every node. Any time your traversal moves to an entity where you didn't change the attainability flag of the output(s), stop that branch of the traversal. You can do this depth-first or breadth-first, whichever you prefer.

When the player acquires (zero -> nonzero) or loses (nonzero -> zero) an entity, update the graph by evaluating successors of that node. Edited by Nypyren

Share this post


Link to post
Share on other sites

Here is some pseudocode for my current approach which does not work with loops. I would appreciate any help in finishing the code.            

ComputeAll()
{
   foreach(EntityType entityType in AllEntityTypes)
   {
       AttainabilityInfo info = GetAttainability(entityType);
       Attainables[entityType] = info; // store it
   }
}


AttainableInfo GetAttainability(EntityType entityType)
{
   AttainableInfo info = Attainables[entityType];
   if (info != null)
   {
      // already computed
      return info;
   }

   if (IsOwned(entityType))
   {
      // we own this
      return new AttainableInfo(true);
   }

   var processes = GetProcessesYieldingOutput(entityType);
             
   foreach(process in processes)
   {
       missingInputs = null;
       missingTools = null;

       foreach (EntityType input in process.InputsByType)
       {
           AttainableInfo inputIsAttainable = GetAttainability(input);

           if (inputIsAttainable.Value == false)
           {
               missingInputs.Add(tool);
           }
       }

       foreach (EntityType tool in process.Tools)
       {
           AttainableInfo toolIsAttainable = GetAttainability(tool);


           if (toolIsAttainable.Value == false)
           {
               missingTools.Add(tool);
           }
        }

        if (missingInputs == null && missingTools == null)
        {
             // we can produce this                       
             return new AttainableInfo(maxDistance);
        }
    }

    return new AttainableInfo(false, missingInputs, missingTools); // we cannot produce this

}   

Share this post


Link to post
Share on other sites


Any time your traversal moves to an entity where you didn't change the attainability flag of the output(s), stop that branch of the traversal.


I am having trouble with this. Can you point to where this test must be done in the pseudocode?

Share this post


Link to post
Share on other sites
Rather than traversing from outputs to inputs, start at the entities you own and traverse towards the outputs.
 
Create a queue

Foreach entity you own
  Mark it attainable and put it in the queue

While the queue is not empty
  Dequeue an entity
  Foreach process using this entity as an input
    Foreach output in that process
      If the output entity is not already marked attainable         <- key step to avoid looping forever.
        Mark it attainable
        Foreach process using this output as an input
          Put it in the queue

Store the attainable set
(assuming C# terminology from here on)

The attainable information can be a bool in each EntityType, or a separate HashSet<EntityType>, or whatever works best for you. I would personally keep a separate set.

Notice that there are a ton of nested foreach loops going through the entire process list. This algorithm will work a lot faster if you have a Dictionary<EntityType,List<Process>> cached ahead of time to reduce the amount of wasted iteration over the process set. Edited by Nypyren

Share this post


Link to post
Share on other sites

Will it still work if a process may require multiple inputs...? You're not checking the tools either so marking it attainable seems premature after checking just one input.

Edited by captain_crunch

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!