// // SuperTuxKart - a fun racing game with go-kart // Copyright (C) 2018 Joerg Henrichs // // This program is free software; you can redistribute it and/or // modify it under the terms of the GNU General Public License // as published by the Free Software Foundation; either version 3 // of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. #include "items/network_item_manager.hpp" #include "karts/abstract_kart.hpp" #include "modes/world.hpp" #include "network/network_config.hpp" #include "network/network_string.hpp" #include "network/protocols/game_protocol.hpp" #include "network/rewind_manager.hpp" #include "network/stk_host.hpp" #include "network/stk_peer.hpp" bool NetworkItemManager::m_network_item_debugging = false; // ============================================================================ /** Creates a new instance of the item manager. This is done at startup * of each race. * We must save the item state first (so that it is restored first), otherwise * state updates for a kart could be overwritten by e.g. simulating the item * collection later (which resets bubblegum counter), so a rewinder uid of * "I" which is less than "Kx" (kart rewinder with id x) */ NetworkItemManager::NetworkItemManager() : Rewinder({RN_ITEM_MANAGER}), ItemManager() { m_confirmed_switch_ticks = -1; m_last_confirmed_item_ticks.clear(); initServer(); } // NetworkItemManager //----------------------------------------------------------------------------- /** If this is a server, initializing the peers in game */ void NetworkItemManager::initServer() { if (NetworkConfig::get()->isServer()) { auto peers = STKHost::get()->getPeers(); for (auto& p : peers) { if (!p->isValidated() || p->isWaitingForGame()) continue; m_last_confirmed_item_ticks[p] = 0; } } } // initServer //----------------------------------------------------------------------------- /** Destructor. Cleans up all items and meshes stored. */ NetworkItemManager::~NetworkItemManager() { for (ItemState* is : m_confirmed_state) { delete is; } } // ~NetworkItemManager //----------------------------------------------------------------------------- void NetworkItemManager::reset() { m_confirmed_switch_ticks = -1; ItemManager::reset(); } // reset //----------------------------------------------------------------------------- /** Called when a kart collects an item. In network games only the server * acts on this event. * \param item The item that was collected. * \param kart The kart that collected the item. */ void NetworkItemManager::collectedItem(ItemState *item, AbstractKart *kart) { if (m_network_item_debugging) Log::info("NIM", "collectedItem at %d index %d type %d ttr %d", World::getWorld()->getTicksSinceStart(), item->getItemId(), item->getType(), item->getTicksTillReturn()); if(NetworkConfig::get()->isServer()) { ItemManager::collectedItem(item, kart); // The server saves the collected item as item event info m_item_events.lock(); m_item_events.getData().emplace_back(World::getWorld()->getTicksSinceStart(), item->getItemId(), kart->getWorldKartId(), item->getTicksTillReturn()); m_item_events.unlock(); } else { // The client predicts item collection: ItemManager::collectedItem(item, kart); } } // collectedItem // ---------------------------------------------------------------------------- /** Called when a switch is activated. On the server adds this information to * the item state so it can be sent to all clients. */ void NetworkItemManager::switchItems() { if (NetworkConfig::get()->isServer()) { // The server saves the collected item as item event info m_item_events.lock(); // Create a switch event - the constructor called determines // the type of the event automatically. m_item_events.getData() .emplace_back(World::getWorld()->getTicksSinceStart()); m_item_events.unlock(); } ItemManager::switchItems(); } // switchItems // ---------------------------------------------------------------------------- /** Called when a new item is created, e.g. bubble gum. * \param type Type of the item. * \param kart In case of a dropped item used to avoid that a kart * is affected by its own items. * \param server_xyz In case of rewind the server's position of this item. * \param server_normal In case of rewind the server's normal of this item. */ Item* NetworkItemManager::dropNewItem(ItemState::ItemType type, const AbstractKart *kart, const Vec3 *server_xyz, const Vec3 *server_normal) { Item *item = ItemManager::dropNewItem(type, kart, server_xyz, server_normal); if(!item) return NULL; // Nothing else to do for client if (NetworkConfig::get()->isClient()) return item; assert(!server_xyz); // Server: store the data for this event: m_item_events.lock(); m_item_events.getData().emplace_back(World::getWorld()->getTicksSinceStart(), type, item->getItemId(), kart->getWorldKartId(), item->getXYZ(), item->getNormal()); m_item_events.unlock(); return item; } // dropNewItem // ---------------------------------------------------------------------------- /** Called by the GameProtocol when a confirmation for an item event is * received by the server. Once all hosts have confirmed an event, it can be * deleted and won't be sent to any clients again. * \param peer Peer confirming the latest event time received. * \param ticks Time at which the last event was received. */ void NetworkItemManager::setItemConfirmationTime(std::weak_ptr peer, int ticks) { assert(NetworkConfig::get()->isServer()); std::unique_lock ul(m_live_players_mutex); // Peer may get removed earlier if peer request to go back to lobby if (m_last_confirmed_item_ticks.find(peer) != m_last_confirmed_item_ticks.end() && ticks > m_last_confirmed_item_ticks.at(peer)) m_last_confirmed_item_ticks.at(peer) = ticks; // Now discard unneeded events and expired (disconnected) peer, i.e. all // events that have been confirmed by all clients: int min_time = std::numeric_limits::max(); for (auto it = m_last_confirmed_item_ticks.begin(); it != m_last_confirmed_item_ticks.end();) { if (it->first.expired()) { it = m_last_confirmed_item_ticks.erase(it); } else { if (it->second < min_time) min_time = it->second; it++; } } ul.unlock(); // Find the last entry before the minimal confirmed time. // Since the event list is sorted, all events up to this // entry can be deleted. m_item_events.lock(); auto p = m_item_events.getData().begin(); while (p != m_item_events.getData().end() && p->getTicks() < min_time) p++; m_item_events.getData().erase(m_item_events.getData().begin(), p); m_item_events.unlock(); } // setItemConfirmationTime //----------------------------------------------------------------------------- /** Saves the state of all items. This is done by using a state that has * been confirmed by all clients as a base, and then only adding any * changes applied to that state later. As clients keep on confirming events * the confirmed event will be moved forward in time, and older events can * be deleted (and not sent to the clients anymore). * This function is also called on the client in the first frame of a race * to save the initial state, which is the first confirmed state by all * clients. */ BareNetworkString* NetworkItemManager::saveState(std::vector* ru) { ru->push_back(getUniqueIdentity()); // On the server: // ============== m_item_events.lock(); uint16_t n = (uint16_t)m_item_events.getData().size(); if(n==0) { BareNetworkString *s = new BareNetworkString(); m_item_events.unlock(); return s; } BareNetworkString *s = new BareNetworkString(n * ( sizeof(int) + sizeof(uint16_t) + sizeof(uint8_t) ) ); for (auto p : m_item_events.getData()) { p.saveState(s); } m_item_events.unlock(); return s; } // saveState //----------------------------------------------------------------------------- /** Progresses the time for all item by the given number of ticks. Used * when computing a new state from a confirmed state. * \param ticks Number of ticks that need to be simulated. */ void NetworkItemManager::forwardTime(int ticks) { int new_ticks = World::getWorld()->getTicksSinceStart() + ticks; World::getWorld()->setTicksForRewind(new_ticks); for(auto &i : m_confirmed_state) { if (i) i->update(ticks); } // for m_all_items if(m_switch_ticks>ticks) m_switch_ticks -= ticks; else if (m_switch_ticks >= 0) { switchItemsInternal(m_confirmed_state); m_switch_ticks = -1; } } // forwardTime //----------------------------------------------------------------------------- /** Restores the state of the items to the current world time. It takes the * last saved confirmed state, applies any updates from the server, and * then syncs up the confirmed state to the in-race items. * It uses exactly 'count' bytes of the message. * \param buffer the state content. * \param count Number of bytes used for this state. */ void NetworkItemManager::restoreState(BareNetworkString *buffer, int count) { assert(NetworkConfig::get()->isClient()); // The state at World::getTicksSinceStart() needs to be restored. The // confirmed state saved here was taken at m_confirmed_state_time // (which is before getTicksSinceStart()). So first forward the confirmed // state to the time we need to rewind to (i.e. getTicksSinceStart()). // Then copy the new confirmed state to the current items. Any new // items (dropped bubblegums) that have been predicted on a client // and not been confirmed by the server data will be removed automatically // at this stage. In more detail: // // 1) Apply all events included in this state to the confirmed state. // It is possible that the server inludes events that have happened // before the confirmed time on this client (the server keeps on // sending all event updates till all clients have confirmed that // that they have received them!!) - which will simply be ignored/ // This phase will only act on the confirmed ItemState in the // NetworkItemManager, nothing in the ItemManager will be changed. // a) When a collection event is found, adjust the confirmed item state // only (this state will later be copied to the current items). // It still call collected() in the item, which will update e.g. // the previous owner, use up counter etc. for that item. // b) When a new item is created, create an ItemState instance for // this item, and put it in the confirmed state. Make sure the // same index position is used. // c) If a switch is used, this will be recorded in // m_confirmed_switch_ticks. // // 2) Inform the server that those item events have been received. // Once the server has received confirmation from all clients // for events, they will not be resent anymore. // // 3) Once all new events have been applied to the confirmed state the // time must be <= world time. Forward the confirmed state to // world time (i.e. all confirmed items will get their ticksTillReturn // value updated), and update m_confirmed_state_time to the world time. // // 4) Finally update the ItemManager state from the confirmed state: // Any items that exist in both data structures will be updated. // If an item exist in the ItemManager but not in the confirmed state // of the NetworkItemManager, the item in the item manager will be // delete - it was a predict item, which has not been confirmed by // the server (e.g. a kart drops a bubble gum, and either the server // has not received that event yet to confirm it, or perhaps the // server detects that the kart did not even have a bubble gum). // Similary, if an item is not in the confirmed state anymore, // but in the ItemManager, it can mean that an item was collected // on the server, which was not predicted. The item in the ItemManager // will be deleted (if a kart has collected this item, the kart state // will include the changed state information for the kart, so no need // to update the kart for this). // // From here the replay can happen. // 1) Apply all events to current confirmed state: // ----------------------------------------------- World *world = World::getWorld(); // The world clock was set by the RewindManager to be the time // of the state we are rewinding to. But the confirmed state of // the network manager is before this (we are replaying item events // since the last confirmed state in order to get a new confirmed state). // So we need to reset the clock to the time of the confirmed state, // and then forward this time accordingly. Getting the world time right // during forwarding the item state is important since e.g. the bubble // gum torque depends on the time. If the world time would be incorrect // at the time the collection event happens, the torque would be // predicted incorrectly, resulting in stuttering. int current_time = m_confirmed_state_time; // Reset the ItemManager's switch ticks to the value it had a the // confirmed time: m_switch_ticks = m_confirmed_switch_ticks; int rewind_to_time = world->getTicksSinceStart(); // Save time we rewind to world->setTicksForRewind(current_time); bool has_state = count > 0; // Note that the actual ItemManager states must NOT be changed here, only // the confirmed states in the Network manager are allowed to be modified. // They will all be copied to the ItemManager states after the loop. while(count > 0) { // 1.1) Decode the event in the message // ------------------------------------ ItemEventInfo iei(buffer, &count); if(m_network_item_debugging) Log::info("NIM", "Rewindto %d current %d iei.index %d iei tick %d iei.coll %d iei.new %d iei.ttr %d confirmed %lx", rewind_to_time, current_time, iei.getIndex(), iei.getTicks(), iei.isItemCollection(), iei.isNewItem(), iei.getTicksTillReturn(), iei.getIndex() < (int)m_confirmed_state.size() && iei.getIndex() != -1 ? m_confirmed_state[iei.getIndex()] : NULL); // 1.2) If the event needs to be applied, forward // the time to the time of this event: // ---------------------------------------------- int dt = iei.getTicks() - current_time; // Skip any events that are 'in the past' (i.e. have been sent again by // the server because it has not yet received confirmation from all // clients). if(dt<0) continue; // Forward the saved state: if (dt>0) forwardTime(dt); if(iei.isItemCollection()) { int index = iei.getIndex(); // An item on the track was collected: AbstractKart *kart = world->getKart(iei.getKartId()); assert(m_confirmed_state[index] != NULL); m_confirmed_state[index]->collected(kart); // Collect item // Reset till ticks return from state (required for eating banana with bomb) int ttr = iei.getTicksTillReturn(); m_confirmed_state[index]->setTicksTillReturn(ttr); if (m_confirmed_state[index]->isUsedUp()) { delete m_confirmed_state[index]; m_confirmed_state[index] = NULL; } } else if(iei.isNewItem()) { AbstractKart *kart = world->getKart(iei.getKartId()); ItemState *is = new ItemState(iei.getNewItemType(), kart, iei.getIndex() ); is->initItem(iei.getNewItemType(), iei.getXYZ(), iei.getNormal()); if (m_switch_ticks >= 0) { ItemState::ItemType new_type = m_switch_to[is->getType()]; is->switchTo(new_type); } // A new confirmed item must either be inserted at the end of all // items, or in an existing unused entry. if (m_confirmed_state.size() <= is->getItemId()) { // In case that the server should send items in the wrong // order, e.g. it sends an item for index n+2, then the item // for index n -> we might need to add NULL item states // into the state array to make sure the indices are correct. while(m_confirmed_state.size()getItemId()) m_confirmed_state.push_back(NULL); m_confirmed_state.push_back(is); } else { // If the new item has an already existing index, // the slot in the confirmed state array must be free assert(m_confirmed_state[is->getItemId()] == NULL); m_confirmed_state[is->getItemId()] = is; } } else if(iei.isSwitch()) { // Switch all confirmed items: ItemManager::switchItemsInternal(m_confirmed_state); } else { Log::error("NetworkItemManager", "Received unknown event type at %d", iei.getTicks()); } current_time = iei.getTicks(); } // while count >0 // 2. Update Server // ================ // Inform the server which events have been received (if there has // been any updates - no need to send messages if nothing has changed) if (has_state) { if (auto gp = GameProtocol::lock()) gp->sendItemEventConfirmation(world->getTicksSinceStart()); } // 3. Forward the confirmed item state to the world time // ===================================================== int dt = rewind_to_time - current_time; if(dt>0) forwardTime(dt); // 4. Copy the confirmed state to the current item state // ====================================================== // We need to test all items - and confirmed or all_items could // be the larger group (confirmed: when a new item was dropped // by a remote kart; all_items: if an item is predicted on // the client, but not yet confirmed). So size_t max_index = std::max(m_confirmed_state.size(), m_all_items.size() ); m_all_items.resize(max_index, NULL); for(unsigned int i=0; i create new item Vec3 xyz = is->getXYZ(); Vec3 normal = is->getNormal(); Item *item_new = dropNewItem(is->getType(), is->getPreviousOwner(), &xyz, &normal ); *((ItemState*)item_new) = *is; m_all_items[i] = item_new; insertItemInQuad(item_new); } else if (!is && item) { deleteItemInQuad(item); delete item; m_all_items[i] = NULL; } } // for i < max_index // Clean up the rest m_all_items.resize(m_confirmed_state.size()); // Now set the clock back to the 'rewindto' time: world->setTicksForRewind(rewind_to_time); // Save the current local time as confirmed time m_confirmed_state_time = world->getTicksSinceStart(); m_confirmed_switch_ticks = m_switch_ticks; } // restoreState //----------------------------------------------------------------------------- /** Save all current items at current ticks in server for live join */ void NetworkItemManager::saveCompleteState(BareNetworkString* buffer) const { const uint32_t all_items = (uint32_t)m_all_items.size(); buffer->addUInt32(World::getWorld()->getTicksSinceStart()) .addUInt32(m_switch_ticks).addUInt32(all_items); for (unsigned i = 0; i < all_items; i++) { if (m_all_items[i]) { buffer->addUInt8(1); m_all_items[i]->saveCompleteState(buffer); } else buffer->addUInt8(0); } } // saveCompleteState //----------------------------------------------------------------------------- /** Restore all current items at current ticks in client for live join * or at the start of a race. */ void NetworkItemManager::restoreCompleteState(const BareNetworkString& buffer) { m_confirmed_state_time = buffer.getUInt32(); m_confirmed_switch_ticks = buffer.getUInt32(); uint32_t all_items = buffer.getUInt32(); for (ItemState* is : m_confirmed_state) { delete is; } m_confirmed_state.clear(); for (unsigned i = 0; i < all_items; i++) { const bool has_item = buffer.getUInt8() == 1; if (has_item) { ItemState* is = new ItemState(buffer); m_confirmed_state.push_back(is); } else m_confirmed_state.push_back(NULL); } } // restoreCompleteState