New Job System(tm)

[vogonistic]

Coming soon to a Porcupine-style game near you!

This is an attempt at describing the new Job System(tm) that we (@svmnotn @gunthergun) are working on.

Here is how it operates more or less: You create a Goal based on one or more Needs:

new Goal("Build a Wall", World.current.GetTileAt(0, 0), new Needs()
    {
        { steelPlateResource, 5 },
        { iceResource, 50 }
    });

Goal will be created from a Job, or maybe replaced by a Job.

Resolve will create a Path from the Goal and for each Path we have, loop over a list of functions that looks for matches of the Needs. If they find a match, they output an Action that has Needs it provides and requires. We take the action and create a new Path that also includes that action. We keep going until we've exhausted the search or we found the goal. There is only some basic actions implemented now, like forging and fetching. Here is the result of running it to fetch 20 ice:

foundPath =>  [PathToGoal cost: 97
  [Goal name: Build a Wall, tile: [Floor, X=51, Y=51], requires: ([Needs
  Ice: 20,
])]
  Fulfilled: [Needs
    Ice: 20,
  ]
  Actions:
    [Action name: Fetch Ice, cost: 24, tile: [Floor, X=31, Y=27]]
    [Action name: Fetch Ice, cost: 6, tile: [Floor, X=26, Y=29]]
    [Action name: Fetch Ice, cost: 43, tile: [Floor, X=13, Y=71]]
    [Action name: Fetch Ice, cost: 24, tile: [Floor, X=36, Y=79]]
[Overrides
  [Floor, X=31, Y=27]: 0,
  [Floor, X=26, Y=29]: 0,
  [Floor, X=13, Y=71]: 0,
  [Floor, X=36, Y=79]: 1,
]
]

Things I'm thinking about:

1. I'm currently tracking cost in time. Need to ask the Character if they want to apply a modifier to paths and actions (Afraid of open spaces? Hate a particular machine?)
2. Do we optimize the walking to the closest resource (create a walk action) or do we just check that it exists and let the character deal with it (recreate the pathfinding and verify that the resource still exists) as they pop the action? Can the pathfinder give us a rough estimate?
3. How do you detect loops? Do we just let them happen and have a cutoff in how long the paths can be?
4. What can't we implement with a system like this?
5. If people are idling and have an organization skill, they could look at all the actions in the queue and determine that there is a need for 100 steel plates in room 42. If there is a stockpile, they could create a job to transfer the plates there.
6. How do we create a job to do basic housekeeping items? Removing dust, feeding the generator, stocking items, carrying stuff to stockpiles?
7. How does this work with something like defending against attackers?
8. How do we integrate some kind of smartness so that a guy a mile away doesn't grab a critical job, like building a tile in a bridge.

Next actions:

• [x] Replace Condition with Needs<string, int>
• [x] Split into 1 class per file
• [x] Create XML tag allowing for multiple inputs and outputs, plus provide the machine max and output ratio (use inventory prefab max stack size as default max)
• [x] Need to take walking into account. I.e. if you need ice and steel, go fetch one, drop it off, fetch second, drop it off. Different path from being able to carry both.
• [ ] Add code that can figure out if we need to drop off inventory or can pick up more
• [ ] Let the Character modify cost for path and action
• [x] Integrate into InventoryManager
• [x] Add support for changes to InventoryManager that hasn't happened yet
• [ ] Move jobs to rooms
• [ ] Create job manager
• [ ] Be able to batch and sort jobs intelligently

It's early code so take it for what it is: https://github.com/vogonistic/ProjectPorcupine/blob/job-optimizer/Assets/Scripts/Jobs/

@svmnotn Ping!

[vogonistic]

I put it here instead of in #86 so that it doesn't drown in an otherwise silent thread, but they are definitely related.

[guntherwullaert]

@vogonistic can't we make the goals and conditions in a graph and then let dijkstra run on it --> that would solve the looping problems ?

[yonner]

Hi all, as just pointed out to me by @mmooxy I also raised an issue #732 in order to discuss a possible implementation of GAB (Goal-driven Agent Behaviour) in project porcupine. If this is a repeat of this discussion I would be happy for my issue to be closed.

Again I certainly don't want to steel anyones thunder but I would like to be a part or contribute to this in some way.

How I would implement the system would be that each Agent iterates over a list of GoalEvaluator s to find the best overall goal to satisfy the agents current need.

Each Goal inherits of a general IGoal interface which allows the agent to have a single Goal_Think member variable which is a composite of IGoal.

This design allows the agent to satisfy its current need by calling a SetGoal() on the current goal evaluator that best satisfies the agents need. By creating a stack of goals which can be broken down into further sub goals if needed.

In practice this would work by giving the agents a number of stats eg energy, sleep, oxgen and then decreasing (or even increasing) these over time usually using some kind of function (we would probably have to play with the numbers until we get the right balance). Then top level goals might be Goal_GetOxgen which might add sub goals such as Goal_PathFindToNearestRoom and Goal_FillOxygenTank, other top level goals might be Goal_GetRest etc..

This system allows for a very flexible system to allow any number of goals which satisfy the current agent desires, we can even interrupt the current goal with another goal allowing the agents to have a memory. I would really recommend reading the book Programming Game AI by Example by Mat Buckland which goes through this and other methods of creating convincing AI. We can also add personalities to this by tweaking the evaluation functions so that some characters would prefer to sleep more then do any works etc...thoughts?

[MSigma]

@vogonistic Glancing through it, your system seems to pick the first viable goal-path and run with it, which would probably make the agents behave a little bit too predictably.

More importantly, cost in time should probably not be the single deciding factor in what makes a path better than another. Say the goal was to build a wall. The agent, using the proposed system, could decide that deconstructing all of the beds and using the material toward the wall's construction was the best option, as long as it's faster than grabbing it from a stockpile. If I'm mistaken, I apologize!

@yonner You're proposing a GAB system in an issue that was raised specifically to propose a GAB system. This is us discussing it! :)

[yonner]

My work here is done :)

On serious note though I did have a FPS example game that used the GAB system I proposed and the AI looked very convincing. Also it allows us to start with a very minimal list of needs and goals and to build up on the complexity as the game grows.

[vogonistic]

@gunthergun I don't think we can build a graph, there might be valid reasons for someone to require steel for two different dependencies. That is, we can't pre-build it.

[vogonistic]

@yonner It sounds like you are describing a system for handling the needs of the characters, while what I'm trying to build is a system the finds how how achieve a goal, after we know that it exists. If I'm correct then your system would run higher up and when there is something the character needs that is important enough to do now, it would create a goal in my system and it would be used to figure out how to achieve it the cheapest.

Is that correct?

[vogonistic]

@MSigma No, you are spot on for this first naive implementation. We might need to add modifiers to the actions cost based on the character and maybe needs of the station.

Ideally, the cost would be such that when the lowest cost path is found, it's also the best fit.

[guntherwullaert]

@vogonistic I still think that is possible though a graph can have multiple paths. but I think for a game like this this is to deep, to build at runtime

[vogonistic]

@gunthergun Yeah. I'm also trying to avoid having to rebuild a graph when a new piece of furniture is placed.

[guntherwullaert]

@vogonistic But I must say I like the start of your system... It definitely will be a big improvement of what we have now if it gets finished... Will you be working on it now ?

[yonner]

@vogonistic I would say that the GAB system would both handle the characters needs, which then equate to goals that should satisfy that need. Once we have an overall goal eg Goal_GetFood that Goal would add a whole host of sub goals to achieve the goal. Eg Goal_FindNearestFood which would determine the nearest food source and generate a path. Once the character has achieved his goal of following this path the next goal might be to eat food Goal_EatFood. If there is no food left then a new Goal would be added to the stack which would satisfy that need etc..

To handle things like building a wall/furniture when the user puts down the tiles to build a wall the need to build for a character is increased and the only why to reduce this need is to Goal_BuildWall of course we need to weight the evaluation methods just right such that the character doesn't just build walls all the time instead of sleeping.

• note: The GAB system would kind of work similar to Quill18 video apart from my suggestion would be to decouple the goals and evaluators and the goals are stack of nested sub goals which allows more complex actions.

[MSigma]

Another concern of mine is that planners like these, when introduced to a changing world-state with a lot of inputs and possible actions tend to be pretty heavy duty. Traditionally, they're not suited to run-time usage, right? Has performance been a factor in the discussion at all?

[yonner]

@MSigma I would imagine games like Prison architect would use systems similar to this. In order to improve performance things like splitting the map into regions and keeping lookup tables of all resources would help. But we need to start somewhere and then maybe think about performance tuning if we notice that things are beginning to slow down.

[vogonistic]

@MSigma I don't envision it being very heavy since we are just matching a list of input conditions. Each iteration in the loop is checking for that limited set of conditions which most actions will not be able to fulfill. We could even optimize and register the calls for types of conditions, so we can exclude some of them. I.e. don't look at stockpiles if we need to walk. If I'm wrong, we can optimize or rebuild it in a better way.

[vogonistic]

@yonner It sounds good but how does the actual selection of subgoals work?

[vogonistic]

Updated posts with actions and thoughts as we've figured things out.

[yonner]

Once a Goal_Evaluator has been selected to satisfy the most pressing need the Goal_Evaluator adds a top level goal to the current stack. These goals in turn add their own sub level goals to their own stack until eventually single actions can be performed such as move here, do job here, eat here (replenish energy stat) etc...

[lameox]

Disclaimer: I currently dont have much time to read over the whole thread but one thought i just had is below:

Do you have a System in place for handling Conditions other than fulfill all specified conditions. For Example, if i had a Job that required either iron or aluminum to complete, how would i specify that? Also i think if we allow some kind of boolean logic to chain conditions in a more complex way there might be great benefits in simplifying the logic first before handling it. E.g. Evaluate "20 Iron or 30 Iron" to the easier to fulfill "20 Iron" only before passing it through the goal system. This would also be a really nice Task for a beginner to intermediate programmer and could be implemented at a later time if we design the code interface correctly now.

[yonner]

@lameox

I think each furniture should have a preconditions hash set (dictionary) and effects hash set (dictionary).

The GAB system can then handle this, for example if the user placed a "food station" furniture which required 5 iron and 7 aluminium then the need stat for iron would increment by 5 and the aluminium need stat would increment by 7 we might also add a need flag to build "food station" (these would probably be added to the world state hashmap). When evaluating all goal evaluators it looks like we have a goal Goal_BuildFurniture which goes through all available furniture's and finds that a food station would satisfy the need to use up the iron and aluminum and might also satisfy hunger (for this character or the world?(feed the world)). So we would add this top level goal to our current stack (We always have an initial Goal_Think. The GOAL_BuildFurniture goal then might have a sub goal to travel to nearest stock pile Goal_FindNearestStockPile, then another goal to gather resources Goal_GatherResourcesFromStockPile then another goal to travel to build site Goal_TravelToBuildSite then a final goal to do the job Goal_DoBuildFurnitureJob. Goal_GatherResourcesFromStockPile might then have further sub goals, If we dont have the required resource at the stock pile we might need to add a goal of Goal_GatherRawResources (which goes of to the nearest resources and brings it back to the stock pile, again further goals). A goal in the stack can only be actioned if the previous goal was complete. Once the overall goal is finally complete we can reduce (remove from dictionary) the need stats be the relevant value and clear the flag for the need to build the food station. All the while we would still be evaluating the goal evaluators incase a pressing need takes over which would be pushed to the top of current stack.

[no-realm]

It may also be interesting to let multiple characters work on different conditions at the same time. For example, I have a job which requires '20 iron' and '10 uranium', then let one character handle the first condition and a second character the second one. This would accelerate things a lot. We could even take this a step further and let two (or more) characters work on the same condition. What I mean with this is, that if there is a condition with '70 iron', then let one character take 50 and some other character take the 20 rest. These are just some thoughts I had while reading this 😄 .

[vogonistic]

@yonner Took me a few reads to think about it, but that sounds like almost exactly what we are building. We aren't thinking of it as needs and we are doing the accounting in a slightly different way, but I like your way better so we might switch what we are suggesting.

We are also not focusing on looking at the basic needs, instead looking at the system that gets kicked off when there is a need to fulfill.

[vogonistic]

@Randshot This system would allow an idling character with the OCD/Organizer trait to look at the jobs and very quickly (like 1 ms) get a list of all the requirements for jobs in the queue and go fetch a stack of the biggest need.

[vogonistic]

We've also discussed adding jobs in batches so that someone can claim a batch, or part of it and get all the inventory needed at once. It's all possible with this kind of system.

[guntherwullaert]

@vogonistic Are you gonna work on this system now ? I have finally again some time to code and I want to help get this system working over the weekend... Do you still need any help ?

[vogonistic]

@gunthergun Me and @svmnotn have started working on it. If you want to help out, take a look at Scripts/Jobs/JobUtils.cs in my branch job-optimizer

There is a todo at the top, but it's slightly inaccurate after the discussions here. Ping me in discord so we can talk more if you feel like helping.

[svmnotn]

@gunthergun actually because of organization, what was there is now split across separate files in: https://github.com/vogonistic/ProjectPorcupine/tree/job-optimizer/Assets/Scripts/Jobs

Any help is much appreciated!

[guntherwullaert]

@vogonistic @svmnotn A little progress update, I could make the Resolver use the InventoryManager to search for the desired Items. This has only one negative and that is search times are majorly increased. But I already like it how he searches for the closest items nearby and factors in the cost to get there.

[svmnotn]

XML tag is done-ish now all that is needed for it is to integrate it into the system

[svmnotn]

So, in order to keep things organized, I will move jobs to be room based, search for jobs based on rooms, and then we need to do something about batching jobs together and magically sort them

[vogonistic]

@svmnotn I added your items to the list.

Since last update, we've implemented a class called InventoryManagerOverride that allows us to model changes to the inventory and search in the hypothetical state with the path finder. It's required when we search for something and pick up multiple piles so that we don't try to pick up the same one repeatedly.

[lameox]

@svmnotn @vogonistic Wouldn't we be better off if we clustered the jobs not by room but by something like k-means clustering? This would give us roughly equally big clusters of jobs.

[vogonistic]

The benefit I see of clustering per room is that it makes sense from a character perspective. When there is a job that is visible, it'll be taken before traversing the base for something else.

[lameox]

@vogonistic I see your point and i think i am trying to solve the same problem. Imagine I have a giant room with jobs spread throughout and just behind my character is a door to a small room which has jobs that are relatively much closer. In that case the room clustering would fail to be efficient. Also how do you cluster jobs that are not within a room? would a character that steps outside become a miner as long as there are ores to find in the outside room?

[vogonistic]

Yeah. I'm just not convinced that it's more natural for a character to go to the other job. This is not true for all rooms, but things you can see are contextually closer than something that might be on the other side of a wall, even if it would be faster to go there.

As for stepping outside. I guess it would depend on why he is outside, if he does mining jobs and there are good jobs close outside.

I'm right now struggling a bit with finding the right job for a character without making the evaluation too costly, but we might just have to improve it over time.

[mikejbrown]

Has anyone taken over this, or do you want to go ahead and make a [WIP] PR on this so people can work on it?

[vogonistic]

This is nowhere near completion. I'm moving it off the 0.1 milestone.

[koosemose]

The aspects of this I would consider to be specifically targeted for 0.2 would be a job manager and batching of jobs.

Job manager should be capable of prioritising closer jobs of the same priority (if there are two medium priority jobs, the closest should be returned to the character looking for a job, rather than taking one across the map), and possibly take a parameter with a character's personal priorities ( an ordered list of some form with types of jobs they want, even if for now there is only one job type and it is just a string) and return jobs first based on the character's preferred jobtypes, and within that jobtype be sorted by each job's priority (This could be subject to change, it is just a suggestion for an initial implementation).

Batch jobs should have some way that multiple jobs can be grouped (such as building a large section of flooring), and added to jobmanager/jobqueue as a single entity, and a character will take the batch job, take as many jobs out of it as they want , and return it so others can take jobs from it as well (or maybe keep it as long as they are using it? But I think just taking however many they want out is preferable, as it will allow very large batch jobs to still be worked on by multiple people). Things to consider: should a character take care of just getting rid of a batch job that is empty or should the job manager take care of getting rid of a batch job that is returned to it with no jobs left.