Dynamic MP algorithm

Programming
1

Background

Dynamic MP calculation wants to find out the most cost-efficient way to do all those organelle updates. It saves time for the player to arrange their changes so that they can make more and focus on surviving. It was first implemented and merged by https://github.com/Revolutionary-Games/Thrive/pull/2445.

However, even after Cleaning up and improving dynamic MP by hhyyrylainen · Pull Request #3322 · Revolutionary-Games/Thrive · GitHub, Fix broken resulting MP calculation in cell editor by Kasterisk · Pull Request #3437 · Revolutionary-Games/Thrive · GitHub, Fix dynamic MP logic a bit by 84634E1A607A · Pull Request #3641 · Revolutionary-Games/Thrive · GitHub and Corrected dynamic MP logic to prioritize ReplacesOther action by 84634E1A607A · Pull Request #4082 · Revolutionary-Games/Thrive · GitHub, I am still able to produce calculation bugs.

We first tried to compare between the initial cell layout and the current layout in https://github.com/Revolutionary-Games/Thrive/pull/2365 but seems to have failed because of the difficulty to compare between graphs (maybe?) and all the bugs.

Then we tried to combine actions to achieve lower cost in https://github.com/Revolutionary-Games/Thrive/pull/2445, in a manner lake bubble sort. This soon proves to be buggy because some combinations are not the best.

Later I turned it to always do the most rewarding way #3641, but still in a sequential manner. (i.e. the combination is performed from the earliest to the latest action. I have proved that this isn’t perfect, still.

Status

The caching system in the algorithm may not work

Think of this seneraio:

  1. You place a Thylacoid to replace the initial cytoplasm ← This should be the only action
  2. You add a Cytoplasm at (0,1)
  3. You remove that Cytoplasm

Pretty simple and clear, but after step 1 and 2, you get this in the cache:

  1. Cytoplasm moved from (0,0) to (0,1)
  2. Thylacoid placed at (0,0)

Then with this cache, step 3 results in:

  1. Cytoplasm removed at (0,0)
  2. Thylacoid placed at (0,0)

Writing to here, I realized that this is because removing a cytoplasm is not combined with placing a Thylacoid. (But a remove action doesn’t know what is removed!)

We may need to try every possibility to get the best result

To avoid local optimal situations. With organelle update implemented, action combining can be more of a headache. So just searching through anything may be the best algorithm?

CellTypes make ActionData need more information

With multicellular set up, ActionData now needs an identity to not to combine actions made to different cell type.

Discussions welcomed!

2

I suggest we add logic to make the cell type start and end modify actions act as markers to disallow certain action types being combined between them. Which was my intention from the start, but apparently it is not working or maybe I forgot to fully make that work?

I don’t like that we are in the mess that is dynamic MP, but any alternative I’ve come up so far must necessarily be as complicated or not handle all the cases that the current dynamic MP with its very complicated merging logic can handle.

At least if a bunch of unit tests (optimally dozens for each possibly tricky sequence of edits) are added this system should become conquerable by mere mortal programmers: Implement unit tests for action data combining · Issue #4078 · Revolutionary-Games/Thrive · GitHub

3

I see. However, I don’t think we have any code to deal with that in the dynamic MP logic at all though.

4

We don’t yet, but that is in concept similar to the history resetting actions, which currently has a special boolean flag added in the action history. Either a new thing could be added or we could extend that existing flag to be like an enum that specifies which category of actions are not allowed to look past that in history for combining.