File: cmd_queue.h

package info (click to toggle)
widelands 1:19+repack-3
  • links: PTS, VCS
  • area: main
  • in suites:
  • size: 370,608 kB
  • ctags: 20,609
  • sloc: cpp: 108,404; ansic: 18,695; python: 5,155; sh: 487; xml: 460; makefile: 233
file content (157 lines) | stat: -rw-r--r-- 4,842 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
/*
 * Copyright (C) 2002-2004, 2006-2009, 2015 by the Widelands Development Team
 *
 * 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 2
 * 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., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 *
 */

#ifndef WL_LOGIC_CMD_QUEUE_H
#define WL_LOGIC_CMD_QUEUE_H

#include <memory>
#include <queue>
#include <stdint.h>

#include <stdint.h>

#include "logic/queue_cmd_ids.h"
#include <stdint.h>

class FileRead;
class FileWrite;

namespace Widelands {

class EditorGameBase;
class Game;
class MapObjectLoader;
struct MapObjectSaver;

constexpr uint32_t kCommandQueueBucketSize = 65536;  // Make this a power of two, so that % is fast

// This is the command queue. It is fully widelands specific,
// it needs to know nearly all modules.
//
// It used to be implemented as a priority_queue sorted by execution_time,
// serial and type of commands. This proved to be a performance bottleneck on
// big games. I then changed this to use a constant size hash_map[gametime] of
// priority_queues. This allows for ~O(1) access by time and in my analyses,
// practically all buckets were used, so there is not much memory overhead.
// This removed the bottleneck for big games.
//
// I first tried with boost::unordered_map, but as expected, it grew beyond all
// limits when accessed with gametime. Therefore I reverted back to a simple
// vector.
//
// The price we pay is that when saving, we also have to traverse till we no
// longer find any new command to write. This could theoretically take forever
// but in my tests it was not noticeable.

/**
 * A command that is supposed to be executed at a certain gametime.
 *
 * Unlike \ref GameLogicCommand objects, base Command object may be used to
 * orchestrate network synchronization and other things that are outside the
 * game simulation itself.
 *
 * Therefore, base Commands are not saved in savegames and do not need to be
 * the same for all parallel simulation.
 */
struct Command {
	Command(const uint32_t init_duetime) : duetime_(init_duetime) {
	}
	virtual ~Command();

	virtual void execute(Game&) = 0;
	virtual QueueCommandTypes id() const = 0;

	uint32_t duetime() const {
		return duetime_;
	}
	void set_duetime(uint32_t const t) {
		duetime_ = t;
	}

private:
	uint32_t duetime_;
};

/**
 * All commands that affect the game simulation (e.g. acting of \ref Bob
 * objects), players' commands, etc. must be derived from this class.
 *
 * GameLogicCommands are stored in savegames, and they must run in parallel
 * for all instances of a game to ensure parallel simulation.
 */
struct GameLogicCommand : public Command {
	GameLogicCommand(uint32_t const init_duetime) : Command(init_duetime) {
	}

	// Write these commands to a file (for savegames)
	virtual void write(FileWrite&, EditorGameBase&, MapObjectSaver&);
	virtual void read(FileRead&, EditorGameBase&, MapObjectLoader&);
};

class CmdQueue {
	friend struct GameCmdQueuePacket;

	enum { cat_nongamelogic = 0, cat_gamelogic, cat_playercommand };

	struct CmdItem {
		Command* cmd;

		/**
		 * category and serial are used to sort commands such that
		 * commands will be executed in the same order on all systems
		 * independent of details of the priority_queue implementation.
		 */
		int32_t category;
		uint32_t serial;

		bool operator<(const CmdItem& c) const {
			if (cmd->duetime() != c.cmd->duetime())
				return cmd->duetime() > c.cmd->duetime();
			else if (category != c.category)
				return category > c.category;
			else
				return serial > c.serial;
		}
	};

public:
	CmdQueue(Game&);
	~CmdQueue();

	/// Add a command to the queue. Takes ownership.
	void enqueue(Command*);

	// Run all commands scheduled for the next interval milliseconds, and update
	// the internal time as well. the game_time_var represents the current game
	// time, which we update and with which we must mess around (to run all
	// queued cmd.s) and which we update (add the interval)
	void run_queue(int32_t interval, uint32_t& game_time_var);

	void flush();  // delete all commands in the queue now

private:
	Game& game_;
	uint32_t nextserial_;
	uint32_t ncmds_;
	using CommandsContainer = std::vector<std::priority_queue<CmdItem>>;
	CommandsContainer cmds_;
};
}

#endif  // end of include guard: WL_LOGIC_CMD_QUEUE_H