[suggestion] New Item Decay algorithm

Gesior.pl

Mega Noob&LOL 2012
Joined
Sep 18, 2007
Messages
2,025
Best answers
19
Reaction score
1,059
Location
PLand
On GitHub there are suggestions that on Real Tibia there are items that decay when player is offline:
Items in depot don’t decay · Issue #2641 · otland/forgottenserver (https://github.com/otland/forgottenserver/issues/2641)

Also items in player depot are not decaying on TFS, until you move it. It should be fixed too.

I think it's time to rewrite items decay.

My idea is to make it timestamp based. I did not benchmark it yet, but it looks like it may work as fast as current implementation.
It will also let us create items that decrease duration even when player is offline.

I wrote little prototype to demonstrate this idea:
C++:
#include <iostream>
#include <list>
#include <map>
#include <chrono>

int64_t OTSYS_TIME()
{
    return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count();
}

class Item;
void internalDecay(Item* item) {
// decays items
}

#define ITEM_ATTRIBUTE_DECAY_TO_TIMESTAMP 123

class Item
{
public:
    // for code that shows duration of item to player
    int32_t getDurationLeft()
    {
        return OTSYS_TIME() - getDecayToTimestamp();
    }

    int32_t getDuration()
    {
        return duration;
    }
    void setDuration(int32_t newDuration)
    {
        duration = newDuration;
    }

    int64_t getDecayToTimestamp()
    {
        return decayToTimestamp;
    }
    void setDecayToTimestamp(int64_t newDecayToTimestamp)
    {
        decayToTimestamp = newDecayToTimestamp;
    }

    void removeAttribute(int attributeType) {

    }
    void decrementReferenceCounter() {

    }
    void incrementReferenceCounter() {

    }
private:
    int32_t duration = 123;

    // THIS WOULD BE ITEM ATTRIBUTE, no extra RAM usage for items without decay
    // it will be savable for items 'decaying offline'
    int64_t decayToTimestamp = 0;
};

class DecayList
{
public:
    void startDecay(Item *item);
    void stopDecay(Item *item);
    void decayItems();
private:
    // inner map is HashTree C++ implementation
    std::map<int64_t, std::map<Item *, Item *>> decayMap;
};

void DecayList::startDecay(Item *item)
{
    int64_t decayToTimestamp = OTSYS_TIME() + item->getDuration();

    // required to fast remove items and calculate duration left
    item->setDecayToTimestamp(decayToTimestamp);

    auto decayItemsMap = decayMap[decayToTimestamp];
    decayItemsMap[item] = item;
    item->incrementReferenceCounter();
}

void DecayList::stopDecay(Item *item)
{
    auto decayToTimestamp = item->getDecayToTimestamp();

    auto decayItemsMap = decayMap[decayToTimestamp];
    decayItemsMap.erase(item);
    item->decrementReferenceCounter();

    auto durationLeft = item->getDurationLeft();
    item->setDuration(durationLeft);
    item->removeAttribute(ITEM_ATTRIBUTE_DECAY_TO_TIMESTAMP);
}

void DecayList::decayItems()
{
    // g_scheduler.addEvent(createSchedulerTask(50, std::bind(&DecayList::decayItems, this)));

    std::list<Item*> itemsToDecay;

    auto it = decayMap.begin(), end = decayMap.end();
    while (it != end) {
        if (it->first > OTSYS_TIME()) {
            break;
        }

        for(auto it2 : it->second) {
            itemsToDecay.push_back(it2.first);
        }
        // is it required?
        it->second.clear();

        it = decayMap.erase(it);
    }

    for(auto item : itemsToDecay) {
        internalDecay(item);
        item->decrementReferenceCounter();
    }
}
 

Yamaken

Pro OpenTibia Developer
Premium User
Joined
Jul 27, 2013
Messages
464
Best answers
3
Reaction score
334
Maybe we can keep the current system(duration) and then just add the current timestamp when the item is saved, then when the item is loaded(player equips, depot, inbox, etc) we can calculate if the item is expired with (saved timestamp + duration) - current timestamp.
 
OP
Gesior.pl

Gesior.pl

Mega Noob&LOL 2012
Joined
Sep 18, 2007
Messages
2,025
Best answers
19
Reaction score
1,059
Location
PLand
@Yamaken
I wrote 'decay offline'/'always decay' feature working with current decay algorithm:

I will rewrite it and make it store item 'timestamp' as 'duration' that is calculated on load/save.

I'm interested in changing decay algorithm, because it's last lagging (executing over 0.05 sec) thing on Kasteria.pl
I found out that there are around 175k fire field etc. items on map, that load of server start (all at once) and decay in 'one bucket', which make server freez for 0.058 sec every X seconds.
There must be some way to make it work faster and with limitable 'bucket' size.

Other thing is that items decay times are WRONG on loaded server.
Code:
void Game::checkDecay()
{
   g_scheduler.addEvent(createSchedulerTask(EVENT_DECAYINTERVAL, std::bind(&Game::checkDecay, this)));
(...)
int32_t decreaseTime = std::min<int32_t>(EVENT_DECAYINTERVAL * EVENT_DECAY_BUCKETS, duration);
duration -= decreaseTime;
These 5 lines says everything.. it execute 'checkDecay' every 1000 ms and decrease time of item by 1000 ms, but.. in real world that event is not executed every 1000 ms, more likely 1020 ms and on high loaded server with 1500 online every 1100 ms.
Which results in 21 minutes decaying life ring (instead of 20 minutes).

Timestamp based 'ordered map' looks like perfect algorithm. In most cases, we don't care about 'duration' of item. It may be interesing in case of life ring (player look at it), but in case of fire field, we only care that it decays after XXX seconds to other item.
Current algorithm decays every decayable item in game every second. A lot of useless calculations.
 
Last edited:

Yamaken

Pro OpenTibia Developer
Premium User
Joined
Jul 27, 2013
Messages
464
Best answers
3
Reaction score
334
@Yamaken
I wrote 'decay offline'/'always decay' feature working with current decay algorithm:

I will rewrite it and make it store item 'timestamp' as 'duration' that is calculated on load/save.

I'm interested in changing decay algorithm, because it's last lagging (executing over 0.05 sec) thing on Kasteria.pl
I found out that there are around 175k fire field etc. items on map, that load of server start (all at once) and decay in 'one bucket', which make server freez for 0.058 sec every X seconds.
There must be some way to make it work faster and with limitable 'bucket' size.

Other thing is that items decay times are WRONG on loaded server.
Code:
void Game::checkDecay()
{
   g_scheduler.addEvent(createSchedulerTask(EVENT_DECAYINTERVAL, std::bind(&Game::checkDecay, this)));
(...)
int32_t decreaseTime = std::min<int32_t>(EVENT_DECAYINTERVAL * EVENT_DECAY_BUCKETS, duration);
duration -= decreaseTime;
These 5 lines says everything.. it execute 'checkDecay' every 1000 ms and decrease time of item by 1000 ms, but.. in real world that event is not executed every 1000 ms, more likely 1020 ms and on high loaded server with 1500 online every 1100 ms.
Which results in 21 minutes decaying life ring (instead of 20 minutes).

Timestamp based 'ordered map' looks like perfect algorithm. In most cases, we don't care about 'duration' of item. It may be interesing in case of life ring (player look at it), but in case of fire field, we only care that it decays after XXX seconds to other item.
Current algorithm decays every decayable item in game every second. A lot of useless calculations.
True, but as far i know the current algorritm needs to have the duration property for items that can be frozen like rings, magic wand etc so you need to emulate duration anyway. I do agree with you about rewriting the decay system(which is really old) but then there is two performance problems: It uses std:lists(which performs shit) and the every time call to item->canDecay().
 
OP
Gesior.pl

Gesior.pl

Mega Noob&LOL 2012
Joined
Sep 18, 2007
Messages
2,025
Best answers
19
Reaction score
1,059
Location
PLand
Items that has duration and it's duration is stoppable (like life ring) will recalculate timestamp and duration everytime you start/stop decay. Also their duration will be calculated every save to database/player 'look'.

Offline items (decay always) will have permanent timestamp that will be changed to 'duration' on save to database. Their timestamp will be calculated again on load from database.
 
OP
Gesior.pl

Gesior.pl

Mega Noob&LOL 2012
Joined
Sep 18, 2007
Messages
2,025
Best answers
19
Reaction score
1,059
Location
PLand
OP
Gesior.pl

Gesior.pl

Mega Noob&LOL 2012
Joined
Sep 18, 2007
Messages
2,025
Best answers
19
Reaction score
1,059
Location
PLand
I found out that new algorithm does not care about item attributes ITEM_ATTRIBUTE_DURATION and ITEM_ATTRIBUTE_DECAY_TIMESTAMP.
They cannot be modified when item is decaying. I made changes in Lua to block access to these attributes and added new functions:
Code:
item:getDurationLeft()
item:setDurationLeft(timeInMiliseconds)
There is also new function to stop decaying:
Code:
item:stopDecay()
All changes you can view in branch:
gesior/forgottenserver (https://github.com/gesior/forgottenserver/commits/2641_new_decay_algorithm)

View of changes:
gesior/forgottenserver (https://github.com/gesior/forgottenserver/compare/6d71dd5ec064e9e302d2f970d9fafaaadda8e7c1..fe1d7201c1caf076fa8963940233f319dfd681e5)
 
OP
Gesior.pl

Gesior.pl

Mega Noob&LOL 2012
Joined
Sep 18, 2007
Messages
2,025
Best answers
19
Reaction score
1,059
Location
PLand
After today's commit it's possible to stop/start decaying from Lua. Now we can create Lua script to start/stop decay of depot when player walks on depot tile.
 

tetra20

DD
Joined
Jan 17, 2009
Messages
1,306
Best answers
3
Reaction score
286
Location
Egypt
#Edit
--Not Applicable--
 
Last edited:

tetra20

DD
Joined
Jan 17, 2009
Messages
1,306
Best answers
3
Reaction score
286
Location
Egypt
So I have thought of another idea that uses a little more memory,
1-We will change
Code:
std::map<Item *, int64_t> reverseItemDecayMap;
To
Code:
std::unordered_map<Item *, int64_t> reverseItemDecayMap;
So now we can have access of O(1) on average to any decaying item.
2-Here where the extra memory comes, We'll use a min-heap, Yeah I know there's a problem when we want to stop decaying an item, We won't be able to remove it from the min-heap, That's why we are just simply going to ignore it, Whenever it's time for the item to decay, We'd check in our hashMap, is this item decaying or not? If it's decaying we remove it from both game & hashmap. otherwise, we do nothing.
So the extra memory comes because we leave those items in our min-heap and remove them only when their time comes. That should guarantee you an O(1) removal on average & O(log n) insertion on the worst case.
 
Last edited:

kay

Advanced OT User
Joined
Apr 23, 2013
Messages
273
Best answers
0
Reaction score
229
In Tibia there was only one flag for decaying. It was actually called "expire" and was used by everything that's time-limited: light sources, pharaoh items, corpses, fields, magic walls, holes, even water tiles (fish respawn). Followed by expiretime and expireto (0 for disappearing).
"Timer" was basicly started/stopped upon load/save, so for player's inventory it would be on login/logout and for depot stepping on/out the depot tile (and for map - obviously loading and saving the map, houses don't matter).
If in newer versions they also added items that decay in real time, you only need to save timestamp and during load check if it hasn't expired, pretty much the same way.
 
Top