Better distribution based on time remaining when training troops

[rodsmar]

How about an automatic better distribuition of troops among barracks based on time remaining when we put the troops to rebuild??

 

[Navalis]

I think I get what you saying here. Like if you loose a handful of Riflemen & one Cannon it ques the cannon behind the evenly distributed riflemen. You would think it would put the cannon in one barracks and split the riflemen between the other two. Seems logical to me and I have also always found it annoying that it doesn't work this way already. My guess is they want you to spend Crowns!

 

[rodsmar]

Yes Navalis. This is that I'm saying. I think it would be easy for the developers to implement this.

 

[Tsamu]

I would like to see this too

 

[Eddie F1]

The retrain has been borked ever since they did it. Originally it was even worse and was removed, this is the new improved version. Still wrong.

I don't know where BHG get their programmers from but this a standard algorithm for stacking boxes in containers or cutting bars of metal. It's trivial stuff, yet they continually screw it up.

As they can't program very well, they should take the easy route and just add up the total time for troop rebuild and spread it over the working barracks, then one solitary artillery would be around 5 minutes on each of 3 barracks instead of 15 minutes in one barrack.

And it screws up even more when an 'event building' gets added that can train troops too.

 

[Radzeer]

Im not really defending the programmers on this, but the algorithm is not trivial as you are suggesting.

https://en.wikipedia.org/wiki/Multiprocessor_scheduling

This algorithm is NP-Hard optimization problem, meaning with increasing number of troops the computational time increases exponentially.
The LPT algorithm mentioned on the wiki could not be used (this was the first version, which needed to be recalled) because the bug for enormous training time for the first troop in queue is still not solved.

The solution would be to create distribution table for all possible troop combinations for 2 and 3 barracks, which would not be that huge.

 

[Eddie F1]

That's the wrong problem.

https://en.wikipedia.org/wiki/Cutting_stock_problem is what you need, and it really is trivial, I've done it a couple of times. Also known as 1D Cutting or Bar Cutting, instead of metres we have seconds.

Troop training is even easier because their is no material wastage or cutting blade thickness to deal with.

The only major difference is when cutting bars you have fixed lengths so the object is to get all your various size pieces out of the minimum number of bars - troop training, we have 3 bars which grow longer so the optimisation is to get all the pieces out of the three shortest bars

 

[Radzeer]

Sorry to contradict, Eddie, but both problems are NP-Hard. I don't see the parallel of the Cutting Stock Problem to barracks and troops, because we are not minimizing the waste here. The multiprocessor scheduling is exactly our problem, as we are having 3 processors (barracks) and the number of jobs is equal to number of troops we want to run (build) on them.
if you can tell me now by any algorithm what is the best distribution of 5 tanks, 5 howitzers, 2 healers, 18 rifles and 2 machine guns, here with it please.

 

[Eddie F1]

All we are interested in how many seconds to train each troop type, tanks are 350 seconds, howitzers = 960, truck=900, rifles=50 - machine guns are in the factory so same but separate, so I've changed them to 8 footies at 35 seconds

Seconds or millimetres, it doesn't matter. It is NP-Hard but we are only talking of 148 troops max if you're Roman, not millions, and multi-processor scheduling probably involves the outcome of one affecting the results in another - this is just taking one long array of values and chopping it into 3 and trying to get them all the same length i.e. the minimum time to train your army.

It is so simple I knocked it up in javascript in around 5 minutes, quicker than explaining it in English - edit the troop array to whatever and run it

https://jsfiddle.net/ozpv11eu/58/

 

[Radzeer]

Great stuff Eddie, but still the algorithm will not give the correct distribution for my combo (do not add the 8 infantry, do it without).
Edited your entry and run the script (without the 35s) The longest time was 3110. (51:50)
https://jsfiddle.net/ozpv11eu/61/#&togetherjs=caMHvyhdwG

The best distribution is done with 3100:
Barrack 1: 350,350,350,350,350,900,50,50,50,50,50,50,50,50,50 = 3100 = 51:40
Barrack 2: 960,960,960, 50,50,50,50 = 3080 = 51:20
Barrack 3: 960,960,900,50,50,50,50,50 = 3070 = 51:10

 

[Eddie F1]

I tried it without the 8 footies and got
var troops = new Array(960, 960, 960, 960, 960, 900, 900, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50,350, 350, 350, 350, 350);

Barracks 1 = 960,960,350,350,350,50,50 = 51:10
Barracks 2 = 960,960,350,350,50,50,50,50,50,50,50,50,50 = 51:10
Barracks 3 = 960,900,900,50,50,50,50,50,50,50 = 51:50

Maybe too early and not enough coffee yet but with the fastest unit being 50 secs and the difference between 51:50 and 51:10 being 40 secs, struggling to see where to improve it.
Frequently the BHG version has 2 barracks finished and still a howitzer and 10 rifles queued in the remaining one.

If it was my game, I'd have simply just divided the total time by number of working barracks, so a single howitzer would be 320 in each barrack

 

[Navalis]

Even though I know next to zero about programming I am very much enjoying this thread guys. My only hope is Nexon/BHG skims through here from time to time…

 

[Navalis]

Is it just me or does it seem like training times/stacking have actually been distributed somewhat more evenly as of late? I could just be lucky or I have found the magic troop count...

 

[Ravenlord]

It's definitely better imo. Occassionally l get a single troop stuck at 1:45hrs or - the worst one - 5hrs for a footman - but that's another story .....

 

[rodsmar]

They improved it in the last update of the game. It is better now.