Job/Priority algorithm and general suggestions

[storm6436]

  I'll preface this with the fact that I've always hated it when people tell me how to do my job, so I'm sorry if this comes off that way, but after futzing about in the preview and seeing the subsequent rollback on a lot of things, here's a number of things I've noticed:

1. If something isn't getting done quickly, there was no way to see why.  Could be I didn't have a groundskeeper or a courier/gofer to pick up that thing... could be they're all busy.  No easy "At a glance" way to see that no one was available at all or if folks were just overworked.

2. Lots of available work-time gets wasted by dupe pathing/job selection choice.  Part of this is user-related, part of it not.   For example, if I'm in a pinch and plowing for wheezeworts to finish my hydrogen chiller, racing against the algae clock, it wouldn't be uncommon for me to set up a bunch of dig, ladder, and tempshift plate orders and then go back to monitoring the base... only to find out some time later that evidently all the oxygen in that area that was there three cycles ago decided it wanted to be somewhere else... and instead of plowing through the abyssalite wall and valiantly careening through the ice field...  they'd walk up to the wall, maybe tap it once, and then run half way back to breathe.   Okay, my bad, kinda, since thin CO2 with certain backgrounds looks pretty much like thin O2... but *shrug*  It's a bit frustrating to watch the dupe train that forms because when dupe 1 quits, someone else picks up the tasker and sprints over... to do the exact same thing.  Now I have 2 dupes in a loop for 1 task and God help you if there's more than one viable task in the same area.  Half your base could be basically doing jumping jacks in low-atmo conditions, eating what little oxygen there is left and accomplishing nothing.

So, as someone who used to get paid as an analyst, I sat back and tried to come up with possible solutions just in case y'all were crazy-busy working on other things and hadn't had much of a chance to mess with the underlying task code, which I will freely admit I have no idea how your task scheduler works so this might all be a waste of time... but I'll toss this out there:

A. When there's a billion bottles generated by a big sweep operation, instead of combining bottles down, dupes will carry them off one at a time, even if 9 of them are in mcg and the last is 50kg.  Pretty sure couriers for solids will keep grabbing until they hit their carry cap, why is this not working for liquids?

B. Seniority preference - My max level miner should not be picking up trash while my untrained (Dig:0) artist beats his face against a sandstone wall.  Same goes with my learning 15 research prof off picking gristle berries while my max level miner pokes about on the research box because the artist is beating his face against the wall.  Highest stat guy needs to be able to tell folks not of his specialty to sod off -- Some sort of specialty restriction should be there to prevent one miner elbowing the rest of the miners off the job.   This would address any profession off wasting efficiency, like my farmers not farming (or applying the greenhouse buff, but that (and the EE's with their gens) are another buggy conversation altogether.

C. Job chaining / job combination / Close proximity preference -- Currently, if I place a 2x3 dig order where only the front two blocks at "visible", it seems that this shows up on the back end as two available job requests which are filled first-come, first-serve... and when those are done and the block appears, the same process is followed.  Problem is, nobody on site necessarily has preference for the following blocks, which translates to a third person, maybe half way across the base taking their sweet time to get there, tapping out one block, and then walking off because the fourth block got claimed by the first guy... who by this point is half way across the base.   This is less of an issue in the early cycles of the game because travel times are very short inside the starting biome... but around cycle 100+ the wasted time from this gets to be a huge time sink.

(Editing note: A and C are actually related.  If you could get the scheduler to combine nearby jobs of trivial duration, that would hit all of A and part of C)

I'm fairly certain if it's possible to implement the above without a massive performance hit (and it might likely not be) I think you'd find a lot of the complaints about the priority revamp would be largely addressed.

Here's a few other things that have been kicking about in the back of my head which are hopefully at least minimally useful:
1. Any chance we can get a mechanical sweeper that can sweep crops?  Not trying to make my farmers unemployed, but it'd be nice to save them the time, especially if the farmers touch buff was intended to be applied to more than 1 or 2 plants at a time.  Even if all it does is pick the plant and drop the food to the ground, less time picking means more time buffing. 

2. In regard to the rollback for skill-ups, I think what you guys tried for the initial part of the preview was a step in the right direction, but underlying issues with the task scheduler like those I outlined above, made your attempt a bridge too far.  IMO, even then the new system was a bit too much even with those issues aside.  Something half-that and half what you rolled back to would be a fair exchange.  Even lowering the cap to 20 isn't nearly enough, but I'm nearly certain the new cap at 20 was a stopgap to keep the forums from filling with hate while keeping the patch deployment on-time.  Just spitballing an idea here:

 a. ambient skill cap at X (Say, 3 or 5) -  specifically, you spawn a guy in with athletics 0, he'll eventually skill up to X (3 or 5).  Same with learning, cooking, etc etc.

b. add new recreational equipment to allow "training" for another 3/5 points, so basically a weight set for strength, treadmills for athletics, bookcases/chairs for learning, construction, digging/anything else you could actually read about and learn.  Give me a reason to build rec rooms and libraries.  Letting the dupes sit and read to reduce stress would give a viable alternate path for stress reduction.  Heck, have a bookworm trait that makes the stress reduction from reading even higher and.or the skill gain faster or unlocks an extra few points non-bookworms don't have access to.

c. jobs themselves?  Give it a +3/+6/+9 (or 2/5/10, or whatever) bonus to whatever's relevant and if you swap them out, they retain half of whatever they've mastered... but honestly, whatever stat buffs they give aught to be because they have access to better equipment/better training.  The Gorflax General Purpose Zero-Point-Energy Beam gun just doesn't cut through rock the same way the amazing RockCrusher 9001 does.  Why?  Because it's over 9000.  Does this mean we need to make new tools? Nah, but it'd be nice to see the job-holders have a different set of equipment, not just a hat.  Though, To be fair, having the ability to make better equipment once you hit plastic does sound kinda nice.  Keep it on a storage rack next to the job desk.  Tie in the rack for justification of the second tier of job bonuses so when you hit top tier and have plastic, then you can make new equipment.

 

 

[Maciej75]

20 hours ago, storm6436 said:

Problem is, nobody on site necessarily has preference for the following blocks, which translates to a third person, maybe half way across the base taking their sweet time to get there, tapping out one block, and then walking off because the fourth block got claimed by the first guy...

Digging is one of most annoying problems with Dupe AI for me. IMO continuation of digging is so important, that it can be even hardcoded.

[Kabrute]

For .03 seconds dupe cannot see further dig jobs, decides to wander across the map to clean a toilet.  That being said I witnessed my first perfect circle last night.  Dupe was working on something, finished it picked something up and hauled it somewhere, once dropped off hit up the near by storage bin and headed back up to do the next one.  I was like "What!  Thats perfect, omg yes"

[Master Miner]

The situation now is that quite soon in the game the travel time becomes higher than any other. It easily happens that the dupes are 70% traveling and only 30% doing something else.

This calls for a solution, where one part is a better AI an the other part perhaps giving the player tools for better management.

Those tools need to better than blocking dupe's way back to the base to prevent him to run away (even if he gets hungry or needs to find a lavatory) until e.g. all of the slime is collected and not just 21kg when 2000kg are lying around within few squares.

An improvement from "pick the nearest task from the currently highest priority class" would be to look at the next task as well. There are few possibilities.

Here's one idea:
- the tasks considered are of currently highest priority
- starting with the nearest task, calculate the needed travel time. intelligently cut off unnecessary calculations
- if there is a task with very short travel time, look no further, take it
- otherwise, starting with the dupes in vicinity of the task site, identify ones who will be able to perform the task, calculate the time needed for them to finish their current task plus needed travel time. Take possibly needed breaks into account. Store calculations / hints for later use.
- pick the task where the dupe in question will be the first who can get there. if there is no such task then take tasks from the next lower priority level

This algorithm would be an improvement, because it looks at the next task and is a step towards planning. It would prevent dupes from switching work sites unnecessarily. E.g. it would prevent a dupe from the base to take next task away from a miner already on the site.

An expansion of this would be to look even further (probably 5-6 seconds in the future) because one dupe on site may possibly get few tasks done (e.g. digging slime and algae) before another one can get there.

One idea for the tools for management would be to have a container attribute "minimum delivery amount" (for storage compactors in the first place) that would mean "don't deliver to me unless you can bring at least an amount of X".

See also: https://forums.kleientertainment.com/topic/87120-poor-dupes-ai-makes-late-game-literally-unplayable/?do=findComment&comment=999891

 

[Kasuha]

Well... let's sum up how the job assignment works at the moment in the first place. Because it's a quite sophisticated already and we don't want to reinvent the wheel.

First, the search for a job starts when a duplicant finishes a task. Quite possibly, he's the only "not working" duplicant in the colony at that very moment, all others are still doing something or running to their workplace.

The search considers every task that is not being worked on (reserved by another duplicant) and reachable by out duplicant. In case of delivery, both piece of material and target building must be reachable. In other cases it's just the workplace. 

First it figures out highest priority and sub-priority used. Priority is the number. Sub-priority now means that occupation-related tasks go first within the priority, and different kinds of tasks are then sorted by their type (e.g. harvests come before deliveries).

The duplicant then picks reachable task with highest priority and sub-priority and within that level it picks the closest one.

Then the duplicant reserves the task, making sure no other duplicant will pick the same task.

Then the duplicant moves to the place of the task and performs it.

Exceptions:

In case of deliveries, duplicants try to cover more - if the source location has more than one pile of material within reach and he can use it at the target, he picks multiple piles. If the target location has more than one possible target (e.g. multiple build orders) asking for the same material, he picks for more and delivers to them all (up to certain distance and up to his carrying capacity).

For some tasks (including digging and building), the duplicant may take over a task already reserved by some other duplicant if that other duplicant is still moving to the location and our duplicant looking for a job stands close to that place. This approach got rid of cases when a duplicant digging narrow tunnel suddenly gave up the work and ran away because some other duplicant way across the map has already reserved digging of the other tile.

 

Currently if a duplicant leaves the dig site, it's only because there's some higher priority job to do, not because some other duplicant wants to take over. But there are still many reasons to leave - first, digging has one of lowest sub-priorities within the priority level. But any order or chore at just one priority higher level will lure him away as well, regardless where on the map it is.

 

To improve the system, I believe it would have to involve some variant of the stable marriage problem algorithm. It would have to consider all duplicants (including the busy ones) and plan one task ahead for them all, taking into account how long will it take them to finish the current task, how long it will take them to move to the new task site, and how long it will take them to finish the new task. Then the duplicant looking for a job would go doing the task that he got in that run, "skipping" all tasks that may be higher priority but can be done faster if another duplicant does them after he's done with his current task.

Even current system is rather performance intensive, late colonies suffer from duplicants staying idle for considerable times because there is only one task planner and the duplicants are queueing for it. An algorithm that takes considerably longer to evaluate would bring this effect much earlier.

[Dujour]

It seems that a lot of the issues talked about here are treating the dupes as if they are fire and forget easy mode task doers. That's just not the case.

You want to dig into the ice biome to get some things and do some stuff? There's a long path to get there? Move the mandatory stupid closer to them, and disable the optional stupid tasks in the jobs panel. 

Build a toilet on the way, build a algae deoxydizer for a pocket of oxygen. Prioritize your tasks correctly. You want your miner to stay there? Give him a temp cot, assign him to it. Assign him a toilet. Bring some food out in a ration box limited to X kg of food. build 1 or two mess tables and assign the workers to them.

You don't need your fully upgraded awesome bathroom for a temporary build site. You need a reasonably happy dupe to be able to ride his current stress level past using a crappy basic needs setup for a short period of time to make your build/dig efficient.

Each efficiency you create further limits their walking around doing stupid things time and creates a more efficient process. 

 

[Maciej75]

4 hours ago, Kasuha said:

This approach got rid of cases when a duplicant digging narrow tunnel suddenly gave up the work and ran away

I would swear that I saw it differently, but thanks to you explanation, I start understanding how did it happen "Triangle of Doom", that made me banging my head at the desk (and was part of my post that Master Miner linked).

Rotation 1
Mi-Ma is at Main Base "far bottom"
Digger digs "far left"
Builder build ladder on "right side" (Tube from Main Base ends in spot near to right side)
There is dropped Material in the middle of dig-site "far left" and "ladder site" on right side, supposedly closer dig site.

Rotation 2
Builder finished one ladder tile, no material, goes Main Base
Digger can see material closer to him, abandons digging on far left, goes looong walk (me facepalming) to right side ladder, picking up material along the way
Mi-Ma at Main Base finished some chore, starts looong walk (me facepalming) from "far bottom" to dig site on "far left".

Rotation 3
Digger, that was builder now, finished one ladder tile, no material, goes Main Base
Mi-Ma can see material closer to her, abandons digging on far left, goes looong walk to right side ladder, picking up material along the way
Some Dupe at Main Base finishes his chore and start a long trip to digging site on far left

I am not 100% sure if this was working this way, but let me here re-paste my videos with travelling Dupes:

Spoiler

Hassan digs "far left" tunnel. But changes his mind for no reason. He goes "right", picking up a Material, with obvious intention of building right-side ladder. But this is so far, that night catches him. Boom boom boom, my head hits desk while watching this:

https://youtu.be/iKWirwSeCiE?t=23 

Mi-Ma travels whole map to dig "far left". Going there, passes Camille that stopped digging there for no reason. Camille is not in hurry (toilet etc.), it is visible she takes Material for another task. Just literally unplayable, as each one digs like one tile deep.

https://youtu.be/WQV7U4wH6ck

 

5 hours ago, Kasuha said:

To improve the system, I believe it would have to involve some variant of the stable marriage problem algorithm.

Strongly disagree. You told me at another thread, that Dupes algorithm should be simple, because part of game is to play with it.
From what you described, I think that main problem is that algorithm become overcomplicated, instead of simplest solution "prefer closer jobs over further".

My expectation as a Player is:
The ladder builder, after finishing one tile, should start on next one (until hungry, need dump and so on, this is acceptable).
If this include long walk for supply, this is Ok, some things need time. This also gives me, a Player, clue what is going on, and what should I do to speed things up - dig some material on construction site.

The problem is:
That overcomplicated algorithm, optimizing supply transport time, gives an impression of total randomness of Dupes behavior.
There is no way for casual player, without help of Kashua (thanks), to understand that disorganization of chores in Main Base can be because of placement of material between far left dig site and right side ladder construction works. 

In typical game of this type, players observes units paths and optimizes it. This is source of fun. But if units does not continue task for some time, or task is indirectly disorganized by another task, this does not work.

I also would like to underline, that such issues can be an side effect of introduction of fu*ed "different materials" that I hate, because it  breaks architecture of game. Without this, there should be enough of basic material everywhere, so problems with supply would not show off.

[Kasuha]

13 minutes ago, Maciej75 said:

Strongly disagree. You told me at another thread, that Dupes algorithm should be simple, because part of game is to play with it.

Well it is simple. "do the closest highest priority task" sums it up nicely, technical details and all kind of exceptions can come later and are not essential for initial understanding.

It just does suboptimal job, I believe we all agree on that. But I strongly doubt any simpler algorithm could do better job. The current algorithm is actually near optimal for bases with just one duplicant - he will always do the closest highest priority job.

The only improvement on it that can be realistically achieved is through considering cooperation with others. And that's what most people who come with ideas are actually asking for, even though they're not aware of it. They want the duplicant to stay in place even if there is more important task somewhere else because it will take him long to get there and - implicitly - some other duplicant closer to the place can do the task faster even though he'll only be available in a while. They don't want the high priority task to be ignored, they want it to get done by some other duplicant.

[clickrush]

@Kasuha this could actually be a funny lategame tech feature that is suited for large bases with many duplicants. You put down a communications relay and your dupes get some kind of swarm intelligence. But at first glance the implications of that seem to be complex, possibly computation heavy and quite frankly not necessary.

[Maciej75]

29 minutes ago, Kasuha said:

The only improvement on it that can be realistically achieved is through considering cooperation with others.

I, again, disagree for same reasons as given last time.

Algorithm has to be simple, so Casual Player can easily understand what is going on. As for me, optimizing by "supply time of material" is overcomplicated, Dupe should optimize by job only. This is user task and fun to optimize supply chain (however tools for this may not be ready yet).

I think, that Dupe behavior should be obvious first, any optimization should be avoided. Because universal optimization is impossible. "Smart asses" that adds such fancy algorithms, usually fixes game for people with their playstyle, while ruining fun for the others.

I would like to refer, for example:

•  to OpenTTD where too smart train brains were uncontrollable for me, as were finding connections unknown to me and traveled through other side of island instead of waiting for path.
• Or good example of "Stronghold", where Woodcutter was tied to his hut and was not expected to "optimize" by using his colleague hut because it was closer. This was player task to move his hut when no more trees avaliable.
• Or example of CAD software I was working on - our Sales Rep found, to his surprise, that customers were "fixing" literally all elements of design to prevent Auto-router, pride of our company, from changing anything.

So it looks for me now, that over development of AI made problems, that can not be solved by additional overdeveloping AI.

[Kasuha]

1 hour ago, Maciej75 said:

Dupe should optimize by job only.

I think that would be a disaster. But if you want optimization by job only, you can play the game that way right now. Keep everything at priority 5, that's all. Dupes will have everything on (almost) the same level, except they'll prioritize their job's tasks. Try playing that way and if you'll be happy about it, good for you. Just keep on mind that not all people are happy about it and the priority system is there to suit their needs.

Or maybe you'll realize that the priority system is there for a reason.

And of course you can also disagree. That's your right. 

[Maciej75]

I meant "job placement only", not "job and material placement".

Looks that a Digger that is one tile from Phospohorite is closer to fertilization task, then Dupe that is in the farm on other side of map, two tiles from Pincha Peper and 10 tiles from storage full of Phosphorite.

Or Dupe one tile from Raw Mineral and 100 tiles from Ladder to be build, is nearer to Build Task the a Dupe that stands on this Ladder, but have 5 tiles to Raw Mineral.

As there is usually only one task, but resources lays in tens of places, then assigning task basing on proximity to material may make impression of being random.

BTW. I am not using Priorities since I decided to check if AI is retarded or I I disorganized unintentionally chores by using Priorities. 

 

[storm6436]

Honestly, there are very few things I prioritize higher than default under normal circumstances.  Plants, outhouses before I swap to real plumbing, etc.  The "new" rolled-back priority system was pretty damn good and would have been perfect if the AI could optimize job tasking like I outlined above.  Any reasonable fix is likely to include some level of "cost" analysis in terms of time.  After all, your Dig:25 miner will spend far less time mining out a given task group than your Dig:2 guy, and treating them identically in calculating optimal tasking is a losing proposition.