better progress bar estimates for meat

[erosson]

Time estimates are linear - cost / production. (The code calls production "velocity" in some places.) This means estimates are exact for energy/larvae/territory, but usually too low for everything in the meat tab, where units-producing-units means production's always increasing. So, until estimates for meat units are improved, we punt and put "less than" before any estimate dependent on meat.

Implement nonlinear estimates: make meat estimates more accurate, remove the "less than" from estimates. Newton's method should work; requires giving unit.velocity() a time-since-reified parameter.

[erosson]

This is ...not really "blocking", but interfering with #303 and #277 - progress bars with exact timing

[Shoelace]

maybe this library would help http://subprotocol.com/system/genetic-js.html

but it maybe overkill since you can calculate now, now+1 and now+2 .. which means you can caluculcate a basic a'

[erosson]

https://en.wikipedia.org/wiki/Root-finding_algorithm

https://en.wikipedia.org/wiki/Root-finding_algorithm#Bracketing_methods

Newton's method probably runs faster, but bisection ought to be easier to implement.

and yet it STILL doesn't work correctly argh, it's close but decimal.js is so fussy about precision. try again tomorrow.

[erosson]

alternate method: http://www.kongregate.com/forums/4545-swarm-simulator/topics/473244-time-remaining-suggestion?page=1#posts-8985615

[lstrzebinczyk]

@erosson Do you have that newton method code somewhere? I'd like to take a look at it, maybe I'll be able to help.

[lstrzebinczyk]

@erosson

alternate method: http://www.kongregate.com/forums/4545-swarm-simulator/topics/473244-time-remaining-suggestion?page=1#posts-8985615

I don't think formula presented in there is correct at all. It does not account for amount of content possessed at the moment of population, and it messes up the production multipliers.

Lets say, that:

1. D_n(0) is amount of tier n element at the moment of calculation. So D_0(0) is meat, D_1(0) is drones etc.
2. Lets say that P_n is amount of content generated at tier n element per one element. So P_1 = 2 means drones generate 2 meat per second.
3. D_n(t) is amount of element tier n at moment t. Basically, what we want to find out.

Formula for meat calculation, based on everything else would look like this:

D_0(t) = D_0(0) + D_1(0) * P_1 * t + D_2(0) * P_2 * P_1 * t^2/2! + D_3(0) * P_3 * P_2 * P_1 * t^3/3! + ...

where '...' continues in the same manner.

Formula for any higher tier element is identical, only switch the n param:

D_1(t) = D_1(0) + D_2(0) * P_2 * t + D_3(0) * P_3 + P_2 * t^2/2! + ...

Also, this doesn't have to be calculated every tick. This moment of time should be possible to be calculated once amd the result should be valid as long, as the params doesn't change (for example, someone buys more units).

Newton method probably failed because you tried to integrate the wrong function : ).

I would love to share how I received this formula. If you want, ill write it all down tomorrow, after I rest a little bit.

[erosson]

The formula you listed is actually exactly how offline progress works today - given some amount-of-time-passed t, find the current count D_0(t), and it works wonderfully. Estimates are a different problem - given a desired count D_0(t), find the amount of time needed t, and unfortunately that's harder to solve (unless I've forgotten something from my calc classes?). You can get an exact solution for linear/quadratic/cubic, but beyond that I think you have to start guessing and iterating - and swarmsim's polynomials can get as high as degree 20-something today iirc. That link has a way to estimate that, while still wrong, is less wrong than what's being used today and doesn't require iterating.

Also, this doesn't have to be calculated every tick.

I think it's already cached, and only calculated once per second - could technically be less often as you said, but periodic recalculating works better with today's laughably incorrect estimates.

Newton method probably failed because you tried to integrate the wrong function : ).

Nope, when it came up with a result the result was good. Problem is, my bignumber library - https://mikemcl.github.io/decimal.js - is very picky about precision, and iterative methods like Newton's need more precision with every iteration which makes decimal.js upset, so very often it'd throw an error instead of give a result. You can "fix" that with rounding, etc., but doing that without interfering with other unrelated code was getting hairy. I could turn off decimal.js's errors which would make it shut up about precision, but its other errors are useful and I don't want to turn them off.

I don't think I ever pushed that code, it's only on my computer. (Bad programmer. Bad, bad. I know better than that.) Will push it to a new branch soon

Thanks for contributing!

[Shoelace]

can you breifly say why you chose decimal.js over the other arbitrary precision libraries out there..

i though math.js could do this and you are already using that?

edit: oops actually.. just noticed that math.js bignumber ispowered by decimal.js.. http://mathjs.org/docs/datatypes/bignumbers.html

so are you using deciaml.js directly in places so you dont have to make math.js bignumber be default?

[erosson]

sure, earliest bignumber implementation actually used math.js - it was super slow. Second implementation used decimal.js because I saw someone else on /r/incremental_games had success with it - it was super slow too. decimal.js only became usable after other performance optimizations that probably would've worked just as well for math.js, but I happened to do the optimizations to the branch that had the decimal.js changes, so that was that.

fwiw, math.js actually uses decimal.js for its bignumbers, so it would've had the same problem here - http://mathjs.org/docs/datatypes/bignumbers.html

[Shoelace]

would there be any value in removing the direct references to decimal.js and using math.js only?

[erosson]

my earlier attempt in its own branch: https://github.com/erosson/swarm/tree/bisect

it's actually using bisection method, not newton's, but the iterative approach is similar (and would conflict with decimal.js in a similar way): https://en.wikipedia.org/wiki/Root-finding_algorithm#Bracketing_methods

for what it's worth, better estimates are quickly becoming the most important/urgent thing on my to-do list, so I'll be attacking this again soon - like, hopefully tomorrow

[erosson]

would there be any value in removing the direct references to decimal.js and using math.js only?

It'd make the game's download slightly smaller, I suppose - math.js includes decimal.js inline, not as a bower dependency. Other than that, I don't think so, unless I've missed something. Not really worth switching imo.

[erosson]

Also, this doesn't have to be calculated every tick.

I think it's already cached, and only calculated once per second -

Nope! Thought I was doing this, but the periodic caching was for something related to this ("can we afford this upgrade yet?") but not for estimates. Good catch, thanks. Now doing this.

[erosson]

This took quite a few more changelists that I neglected to tag properly, but check the changelists near the one I did tag above.

Bisection method works, and returns all estimates with 0.1-second precision. It's limited to a maximum estimate of two years (past that point I think the estimate stops mattering). The one-degree-estimate technique's also implemented, but not used (it was useful for testing, and it's faster if people complain about bisection's speed). Estimates are cached, cache is cleared after you can afford the next upgrade or after buying a unit, whichever comes first.

[lstrzebinczyk]

Good job!: )