Merge lp:~widelands-dev/widelands/ai_sched_speedup into lp:widelands

[TiborB]

Currently AI runs only one job per call, and this change allows up to 4 jobs per call, depending on the delay of most delayed job. Moreover, once jobs to run are identified, they are sorted by own priority, because there are dependencies between them, like check_buildable_fields should be done before construct_building and so on...

The goal is to allow AI cope better with higher speeds of game. However warnings to terminal are preserved, so it is usefull to watch for them when testing/playing...

[TiborB (tiborb95)]

oh, I found some mathematical issues here, I will push new version tonight

[GunChleoc (gunchleoc)]

Code review is in http://bazaar.launchpad.net/~widelands-dev/widelands/ai_sched_speedup/revision/7616

[TiborB (tiborb95)]

I believe all your comments were incorporated...

[GunChleoc (gunchleoc)]

Yes, go ahead and merge :)

review: Approve

=== modified file 'src/ai/ai_help_structs.h'
--- src/ai/ai_help_structs.h	2015-11-11 09:53:54 +0000
+++ src/ai/ai_help_structs.h	2015-11-21 18:26:32 +0000
@@ -44,6 +44,26 @@
 enum class ExtendedBool : uint8_t {kUnset, kTrue, kFalse};
 enum class BuildingNecessity : uint8_t
 	{kForced, kNeeded, kNotNeeded, kUnset, kNotBuildable, kAllowed, kNeededPending};
+enum class SchedulerTaskId : uint8_t {
+		kBbuildableFieldsCheck,
+		kMineableFieldsCheck,
+		kRoadCheck,
+		kUnbuildableFCheck,
+		kCheckEconomies,
+		kProductionsitesStats,
+		kConstructBuilding,
+		kCheckProductionsites,
+		kCheckShips,
+		KMarineDecisions,
+		kCheckMines,
+		kWareReview,
+		kPrintStats,
+		kCheckMilitarysites,
+		kCheckTrainingsites,
+		kCountMilitaryVacant,
+		kCheckEnemySites,
+		kUnset
+	};
 
 struct CheckStepRoadAI {
 	CheckStepRoadAI(Player* const pl, uint8_t const mc, bool const oe)
@@ -541,4 +561,23 @@
 	}
 };
 
+// this represents a scheduler task
+struct SchedulerTask {
+	uint32_t due_time;
+	Widelands::SchedulerTaskId id;
+	// used to sort jobs when AI has to perform more jobs at once
+	uint8_t priority;
+	// used only for debug purposes
+	std::string descr;
+
+	bool operator<(SchedulerTask other) const {
+		return priority > other.priority;
+	}
+
+	SchedulerTask
+		(const uint32_t time, const Widelands::SchedulerTaskId t, const uint8_t p, const char* d):
+		due_time(time), id(t), priority(p), descr(d){}
+
+};
+
 #endif  // end of include guard: WL_AI_AI_HELP_STRUCTS_H

=== modified file 'src/ai/defaultai.cc'
--- src/ai/defaultai.cc	2015-11-11 09:53:54 +0000
+++ src/ai/defaultai.cc	2015-11-21 18:26:32 +0000
@@ -86,6 +86,9 @@
 // duration of military campaign
 constexpr int kCampaignDuration = 15 * 60 * 1000;
 
+// for scheduler
+constexpr int kMaxJobs = 4;
+
 using namespace Widelands;
 
 DefaultAI::AggressiveImpl DefaultAI::aggressiveImpl;
@@ -266,136 +269,206 @@
 	// AI now thinks twice in a seccond, if the game engine allows this
 	// if too busy, the period can be many seconds.
 	next_ai_think_ = gametime + 500;
-	ScheduleTasks DueTask = ScheduleTasks::kIdle;
-	DueTask = get_oldest_task(gametime);
-	schedStat[static_cast<uint32_t>(DueTask)] += 1;
-
-	// now AI runs a job selected above to be performed in this turn
-	// (only one but some of them needs to run check_economies() to
-	// guarantee consistency)
-	// job names are selfexplanatory
-	switch (DueTask) {
-		case ScheduleTasks::kBbuildableFieldsCheck :
-			update_all_buildable_fields(gametime);
-			taskDue[ScheduleTasks::kBbuildableFieldsCheck] = gametime + kMinBFCheckInterval;
-			break;
-		case ScheduleTasks::kMineableFieldsCheck :
-			update_all_mineable_fields(gametime);
-			taskDue[ScheduleTasks::kMineableFieldsCheck] = gametime + kMinMFCheckInterval;
-			break;
-		case ScheduleTasks::kRoadCheck :
-			if (check_economies()) {  // is a must
-				return;
-			};
-			taskDue[ScheduleTasks::kRoadCheck] = gametime + 1000;
-			// testing 5 roads
-			{
-				const int32_t roads_to_check = (roads.size() + 1 < 5) ? roads.size() + 1 : 5;
-				for (int i = 0; i < roads_to_check; i += 1) {
-					// improve_roads function will test one road and rotate roads vector
-					if (improve_roads(gametime)) {
-						// if significant change takes place do not go on
-						break;
-					};
-				}
-			}
-			break;
-		case ScheduleTasks::kUnbuildableFCheck :
-			taskDue[ScheduleTasks::kUnbuildableFCheck] = gametime + 4000;
-			update_all_not_buildable_fields();
-			break;
-		case ScheduleTasks::kCheckEconomies :
-			check_economies();
-			taskDue[ScheduleTasks::kCheckEconomies] = gametime + 8000;
-			break;
-		case ScheduleTasks::kProductionsitesStats :
-			update_productionsite_stats(gametime);
-			break;
-		case ScheduleTasks::kConstructBuilding :
-			if (check_economies()) {  // economies must be consistent
-				return;
-			}
-			if (gametime < 15000) { //more frequent on the beginning of game
-				taskDue[ScheduleTasks::kConstructBuilding] = gametime + 2000;
-			} else {
-				taskDue[ScheduleTasks::kConstructBuilding] = gametime + 6000;
-			}
-			if (construct_building(gametime)) {
-				time_of_last_construction_ = gametime;
-			}
-			break;
-		case ScheduleTasks::kCheckProductionsites :
-			if (check_economies()) {  // economies must be consistent
-				return;
-			}
-			{
-				// testing 5 productionsites (if there are 5 of them)
-				int32_t ps_to_check = (productionsites.size() < 5) ? productionsites.size() : 5;
-				for (int i = 0; i < ps_to_check; i += 1) {
-					// one productionsite per one check_productionsites() call
-					if (check_productionsites(gametime)) {
-						// if significant change takes place do not go on
-						break;
-					};
-				}
-			}
-			taskDue[ScheduleTasks::kCheckProductionsites] = gametime + 15000;
-			break;
-		case ScheduleTasks::kCheckShips :
-			check_ships(gametime);
-			break;
-		case ScheduleTasks::KMarineDecisions :
-			marine_main_decisions(gametime);
-			break;
-		case ScheduleTasks::kCheckMines :
-			if (check_economies()) {  // economies must be consistent
-				return;
-			}
-			taskDue[ScheduleTasks::kCheckMines] = gametime + 15000;
-			// checking 3 mines if possible
-			{
-				int32_t mines_to_check = (mines_.size() < 5) ? mines_.size() : 5;
-				for (int i = 0; i < mines_to_check; i += 1) {
-					// every run of check_mines_() checks one mine
-					if (check_mines_(gametime)) {
-						// if significant change takes place do not go on
-						break;
-					};
-				}
-			}
-			break;
-		case ScheduleTasks::kCheckMilitarysites :
-			check_militarysites(gametime);
-			break;
-		case ScheduleTasks::kCheckTrainingsites :
-			check_trainingsites(gametime);
-			break;
-		case ScheduleTasks::kCountMilitaryVacant :
-			count_military_vacant_positions();
-			taskDue[ScheduleTasks::kCountMilitaryVacant] = gametime + 45 * 1000;
-			break;
-		case ScheduleTasks::kWareReview :
-			if (check_economies()) {  // economies must be consistent
-				return;
-			}
-			taskDue[ScheduleTasks::kWareReview] = gametime + 15 * 60 * 1000;
-			review_wares_targets(gametime);
-			break;
-		case ScheduleTasks::kPrintStats :
-			if (check_economies()) {  // economies must be consistent
-				return;
-			}
-			print_stats(gametime);
-			break;
-		case ScheduleTasks::kCheckEnemySites :
-			check_enemy_sites(gametime);
-			taskDue[ScheduleTasks::kCheckEnemySites] = gametime + 19 * 1000;
-			break;
-		case ScheduleTasks::kIdle :
-			break;
-		default:
-			;
+	SchedulerTaskId due_task = SchedulerTaskId::kUnset;
+
+	sort_task_pool();
+
+	const int32_t delay_time = gametime - taskPool.front().due_time;
+
+	// Here we decide how many jobs will be run now (none - 5)
+	// in case no job is due now, it can be zero
+	uint32_t jobs_to_run_count = (delay_time < 0) ? 0 : 1;
+
+	// Here we collect data for "too late ..." message
+	if (delay_time > 5000) {
+		scheduler_delay_counter_ += 1;
+	} else {
+		scheduler_delay_counter_ = 0;
+	}
+
+	if (jobs_to_run_count == 0) {
+		// well we have nothing to do now
+		return;
+	}
+
+	// And printing it now and resetting counter
+	if (scheduler_delay_counter_ > 10) {
+		log(" %d: AI: game speed too high, jobs are too late (now %2d seconds)\n",
+		player_number(),
+		static_cast<int32_t>(delay_time / 1000));
+		scheduler_delay_counter_ = 0;
+	}
+
+	// 400 provides that second job is run if delay time is longer then 1.6 sec
+	if (delay_time / 400 > 1) {
+		jobs_to_run_count = sqrt(static_cast<uint32_t>(delay_time / 500));
+	}
+
+	jobs_to_run_count = (jobs_to_run_count > kMaxJobs) ? kMaxJobs : jobs_to_run_count;
+	assert (jobs_to_run_count > 0 && jobs_to_run_count <= kMaxJobs);
+	assert (jobs_to_run_count < taskPool.size());
+
+	// Pool of tasks to be executed this run. In ideal situation it will consist of one task only.
+	std::vector<SchedulerTask> current_task_queue;
+	// Here we push SchedulerTask members into the temporary queue, providing that a task is due now and
+	// the limit (jobs_to_run_count) is not exceeded
+	for (uint8_t i = 0; i < jobs_to_run_count; i += 1) {
+		if (taskPool[i].due_time <= gametime) {
+			current_task_queue.push_back(taskPool[i]);
+			sort_task_pool();
+		} else {
+			break;
 		}
+	}
+
+	assert (!current_task_queue.empty() && current_task_queue.size() <= jobs_to_run_count);
+
+	// Ordering temporary queue so that higher priority (lower number) is on the beginning
+	std::sort(current_task_queue.begin(), current_task_queue.end());
+
+	// Performing tasks from temporary queue one by one
+	for (uint8_t i = 0; i < current_task_queue.size(); ++i) {
+
+		due_task = current_task_queue[i].id;
+
+		sched_stat_[static_cast<uint32_t>(due_task)] += 1;
+
+		// Now AI runs a job selected above to be performed in this turn
+		// (only one but some of them needs to run check_economies() to
+		// guarantee consistency)
+		// job names are selfexplanatory
+		switch (due_task) {
+			case SchedulerTaskId::kBbuildableFieldsCheck :
+				update_all_buildable_fields(gametime);
+				set_taskpool_task_time(gametime + kMinBFCheckInterval, SchedulerTaskId::kBbuildableFieldsCheck);
+				break;
+			case SchedulerTaskId::kMineableFieldsCheck :
+				update_all_mineable_fields(gametime);
+				set_taskpool_task_time(gametime + kMinMFCheckInterval, SchedulerTaskId::kMineableFieldsCheck);
+				break;
+			case SchedulerTaskId::kRoadCheck :
+				if (check_economies()) {  // is a must
+					return;
+				};
+				set_taskpool_task_time(gametime + 1000, SchedulerTaskId::kRoadCheck);
+				// testing 5 roads
+				{
+					const int32_t roads_to_check = (roads.size() + 1 < 5) ? roads.size() + 1 : 5;
+					for (int j = 0; j < roads_to_check; j += 1) {
+						// improve_roads function will test one road and rotate roads vector
+						if (improve_roads(gametime)) {
+							// if significant change takes place do not go on
+							break;
+						};
+					}
+				}
+				break;
+			case SchedulerTaskId::kUnbuildableFCheck :
+				set_taskpool_task_time(gametime + 4000, SchedulerTaskId::kUnbuildableFCheck);
+				update_all_not_buildable_fields();
+				break;
+			case SchedulerTaskId::kCheckEconomies :
+				check_economies();
+				set_taskpool_task_time(gametime + 8000, SchedulerTaskId::kCheckEconomies);
+				break;
+			case SchedulerTaskId::kProductionsitesStats :
+				update_productionsite_stats();
+				// Updating the stats every 10 seconds should be enough
+				set_taskpool_task_time(gametime + 10000, SchedulerTaskId::kProductionsitesStats);
+				break;
+			case SchedulerTaskId::kConstructBuilding :
+				if (check_economies()) {  // economies must be consistent
+					return;
+				}
+				if (gametime < 15000) { //more frequent on the beginning of game
+					set_taskpool_task_time(gametime + 2000, SchedulerTaskId::kConstructBuilding);
+				} else {
+					set_taskpool_task_time(gametime + 6000, SchedulerTaskId::kConstructBuilding);
+				}
+				if (construct_building(gametime)) {
+					time_of_last_construction_ = gametime;
+				}
+				break;
+			case SchedulerTaskId::kCheckProductionsites :
+				if (check_economies()) {  // economies must be consistent
+					return;
+				}
+				{
+					set_taskpool_task_time(gametime + 15000, SchedulerTaskId::kCheckProductionsites);
+					// testing 5 productionsites (if there are 5 of them)
+					int32_t ps_to_check = (productionsites.size() < 5) ? productionsites.size() : 5;
+					for (int j = 0; j < ps_to_check; j += 1) {
+						// one productionsite per one check_productionsites() call
+						if (check_productionsites(gametime)) {
+							// if significant change takes place do not go on
+							break;
+						};
+					}
+				}
+				break;
+			case SchedulerTaskId::kCheckShips :
+				set_taskpool_task_time(gametime + 3 * kShipCheckInterval, SchedulerTaskId::kCheckShips);
+				check_ships(gametime);
+				break;
+			case SchedulerTaskId::KMarineDecisions :
+				set_taskpool_task_time(gametime + kMarineDecisionInterval, SchedulerTaskId::KMarineDecisions);
+				marine_main_decisions();
+				break;
+			case SchedulerTaskId::kCheckMines :
+				if (check_economies()) {  // economies must be consistent
+					return;
+				}
+				set_taskpool_task_time(gametime + 15000, SchedulerTaskId::kCheckMines);
+				// checking 3 mines if possible
+				{
+					int32_t mines_to_check = (mines_.size() < 5) ? mines_.size() : 5;
+					for (int j = 0; j < mines_to_check; j += 1) {
+						// every run of check_mines_() checks one mine
+						if (check_mines_(gametime)) {
+							// if significant change takes place do not go on
+							break;
+						};
+					}
+				}
+				break;
+			case SchedulerTaskId::kCheckMilitarysites :
+				// just to be sure the value is reset
+				// 4 seconds is really fine
+				set_taskpool_task_time(gametime + 4 * 1000, SchedulerTaskId::kCheckMilitarysites);
+				check_militarysites(gametime);
+				break;
+			case SchedulerTaskId::kCheckTrainingsites :
+				set_taskpool_task_time(
+					gametime + kTrainingSitesCheckInterval, SchedulerTaskId::kCheckTrainingsites);
+				check_trainingsites(gametime);
+				break;
+			case SchedulerTaskId::kCountMilitaryVacant :
+				count_military_vacant_positions();
+				set_taskpool_task_time(gametime + 45 * 1000, SchedulerTaskId::kCountMilitaryVacant);
+				break;
+			case SchedulerTaskId::kWareReview :
+				if (check_economies()) {  // economies must be consistent
+					return;
+				}
+				set_taskpool_task_time(gametime + 15 * 60 * 1000, SchedulerTaskId::kWareReview);
+				review_wares_targets(gametime);
+				break;
+			case SchedulerTaskId::kPrintStats :
+				if (check_economies()) {  // economies must be consistent
+					return;
+				}
+				set_taskpool_task_time(gametime + 30 * 60 * 1000, SchedulerTaskId::kPrintStats);
+				print_stats();
+				break;
+			case SchedulerTaskId::kCheckEnemySites :
+				check_enemy_sites(gametime);
+				set_taskpool_task_time(gametime +   19 * 1000, SchedulerTaskId::kCheckEnemySites);
+				break;
+			default:
+				assert(false);
+				;
+			}
+	}
 }
 
 /**
@@ -407,6 +480,8 @@
 void DefaultAI::late_initialization() {
 	player_ = game().get_player(player_number());
 	tribe_ = &player_->tribe();
+	const uint32_t gametime = game().get_gametime();
+
 	log("ComputerPlayer(%d): initializing (%u)\n", player_number(), type_);
 
 	wares.resize(game().tribes().nrwares());
@@ -638,6 +713,42 @@
 		resource_necessity_water_needed_ = true;
 	}
 
+	// Populating taskPool with all AI jobs and their starting times
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime,              0),
+								SchedulerTaskId::kConstructBuilding,     6, "construct a building"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime,  1 *      1000),
+								SchedulerTaskId::kRoadCheck,             2, "roads check"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime, 15 *      1000),
+								SchedulerTaskId::kCheckProductionsites,  5, "productionsites check"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime, 30 *      1000),
+								SchedulerTaskId::kProductionsitesStats,  1, "productionsites statistics"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime, 30 *      1000),
+								SchedulerTaskId::kCheckMines,            5, "check mines"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime,  0 *      1000),
+								SchedulerTaskId::kCheckMilitarysites,    5, "check militarysites"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime, 30 *      1000),
+								SchedulerTaskId::kCheckShips,            5, "check ships"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime,  1 *      1000),
+								SchedulerTaskId::kCheckEconomies,        1, "check economies"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime, 30 *      1000),
+								SchedulerTaskId::KMarineDecisions,       5, "marine decisions"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime,  2 * 60 * 1000),
+								SchedulerTaskId::kCheckTrainingsites,    5, "check training sites"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime,  1 *      1000),
+								SchedulerTaskId::kBbuildableFieldsCheck, 2, "check buildable fields"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime,  1 *      1000),
+								SchedulerTaskId::kMineableFieldsCheck,   2, "check mineable fields"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime,  1 *      1000),
+								SchedulerTaskId::kUnbuildableFCheck,     1, "check unbuildable fields"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime, 15 * 60 * 1000),
+								SchedulerTaskId::kWareReview,            9, "wares review"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime, 30 * 60 * 1000),
+								SchedulerTaskId::kPrintStats,            9, "print statistics"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime,  1 * 60 * 1000),
+								SchedulerTaskId::kCountMilitaryVacant,   2, "count military vacant"));
+	taskPool.push_back(SchedulerTask(std::max<uint32_t>(gametime, 10 * 60 * 1000),
+								SchedulerTaskId::kCheckEnemySites,       6, "check enemy sites"));
+
 	Map& map = game().map();
 
 	// here we generate list of all ports and their vicinity from entire map
@@ -719,24 +830,6 @@
 		}
 	}
 
-	taskDue[ScheduleTasks::kConstructBuilding] = 0;
-	taskDue[ScheduleTasks::kRoadCheck] = 1000;
-	taskDue[ScheduleTasks::kCheckProductionsites] = 15 * 1000;
-	taskDue[ScheduleTasks::kProductionsitesStats] = 30000;
-	taskDue[ScheduleTasks::kCheckMines] = 30 * 1000;
-	taskDue[ScheduleTasks::kCheckMilitarysites] = 0;
-	taskDue[ScheduleTasks::kCheckShips] = 30 * 1000;
-	taskDue[ScheduleTasks::kCheckEconomies] = 1000;
-	taskDue[ScheduleTasks::KMarineDecisions] = 30 * 1000;
-	taskDue[ScheduleTasks::kCheckTrainingsites] = 2 * 60 * 1000;
-	taskDue[ScheduleTasks::kBbuildableFieldsCheck] = 1000;
-	taskDue[ScheduleTasks::kMineableFieldsCheck] = 1000;
-	taskDue[ScheduleTasks::kUnbuildableFCheck] = 1000;
-	taskDue[ScheduleTasks::kWareReview] = 15 * 60 * 1000;
-	taskDue[ScheduleTasks::kPrintStats] = 30 * 60 * 1000;
-	taskDue[ScheduleTasks::kCountMilitaryVacant] = 1 * 60 * 1000;
-	taskDue[ScheduleTasks::kCheckEnemySites] = 10 * 60 * 1000;
-
 	// Here the AI persistent data either exists - then they are read
 	// or does not exist, then they are created and saved
 	int16_t persistent_data_exists_ = 0;
@@ -1265,9 +1358,7 @@
 }
 
 /// Updates the production and MINE sites statistics needed for construction decision.
-void DefaultAI::update_productionsite_stats(uint32_t const gametime) {
-	// Updating the stats every 10 seconds should be enough
-	taskDue[ScheduleTasks::kProductionsitesStats] = gametime + 10000;
+void DefaultAI::update_productionsite_stats() {
 	uint16_t fishers_count = 0;  // used for atlanteans only
 
 	// Reset statistics for all buildings
@@ -3339,18 +3430,13 @@
 // and makes two decisions:
 // - build a ship
 // - start preparation for expedition
-bool DefaultAI::marine_main_decisions(uint32_t const gametime) {
-	if (gametime < taskDue[ScheduleTasks::KMarineDecisions]) {
-		return false;
-	}
+bool DefaultAI::marine_main_decisions() {
 
 	if (!seafaring_economy) {
-		taskDue[ScheduleTasks::KMarineDecisions] = std::numeric_limits<uint32_t>::max();
+		set_taskpool_task_time(std::numeric_limits<uint32_t>::max(), SchedulerTaskId::KMarineDecisions);
 		return false;
 	}
 
-	taskDue[ScheduleTasks::KMarineDecisions] = gametime + kMarineDecisionInterval;
-
 	// getting some base statistics
 	player_ = game().get_player(player_number());
 	uint16_t ports_count = 0;
@@ -3449,12 +3535,9 @@
 
 // This identifies ships that are waiting for command
 bool DefaultAI::check_ships(uint32_t const gametime) {
-	if (gametime < taskDue[ScheduleTasks::kCheckShips]) {
-		return false;
-	}
 
 	if (!seafaring_economy) {
-		taskDue[ScheduleTasks::kCheckShips] = std::numeric_limits<int32_t>::max();
+		set_taskpool_task_time(std::numeric_limits<int32_t>::max(), SchedulerTaskId::kCheckShips);
 		return false;
 	}
 
@@ -3518,11 +3601,8 @@
 	}
 
 	if (action_taken) {
-		taskDue[ScheduleTasks::kCheckShips] = gametime + kShipCheckInterval;
-	} else {
-		taskDue[ScheduleTasks::kCheckShips] = gametime + 3 * kShipCheckInterval;
+		set_taskpool_task_time(gametime + kShipCheckInterval, SchedulerTaskId::kCheckShips);
 	}
-
 	return true;
 }
 
@@ -4020,13 +4100,12 @@
 // this function only check with trainingsites
 // manipulates input queues and soldier capacity
 bool DefaultAI::check_trainingsites(uint32_t gametime) {
-	if (taskDue[ScheduleTasks::kCheckTrainingsites] > gametime) {
+	if (get_taskpool_task_time(SchedulerTaskId::kCheckTrainingsites) > gametime) {
 		return false;
 	}
-	if (!trainingsites.empty()) {
-		taskDue[ScheduleTasks::kCheckTrainingsites] = gametime + kTrainingSitesCheckInterval;
-	} else {
-		taskDue[ScheduleTasks::kCheckTrainingsites] = gametime + 2 * kTrainingSitesCheckInterval;
+	if (trainingsites.empty()) {
+		set_taskpool_task_time(
+			gametime + 2 * kTrainingSitesCheckInterval, SchedulerTaskId::kCheckTrainingsites);
 		return false;
 	}
 
@@ -4139,12 +4218,6 @@
  * \returns true if something was changed
  */
 bool DefaultAI::check_militarysites(uint32_t gametime) {
-	if (taskDue[ScheduleTasks::kCheckMilitarysites] > gametime) {
-		return false;
-	}
-
-	// just to be sure the value is reset
-	taskDue[ScheduleTasks::kCheckMilitarysites] = gametime + 4 * 1000;  // 4 seconds is really fine
 
 	// Only useable, if defaultAI owns at least one militarysite
 	if (militarysites.empty()) {
@@ -4254,7 +4327,6 @@
 	// reorder:;
 	militarysites.push_back(militarysites.front());
 	militarysites.pop_front();
-	taskDue[ScheduleTasks::kCheckMilitarysites] = gametime + 5 * 1000;  // 10 seconds is really fine
 	return changed;
 }
 
@@ -4728,8 +4800,8 @@
 			}
 		}
 
-		// Let defaultAI try to directly connect the constructionsite
-		taskDue[ScheduleTasks::kRoadCheck] = game().get_gametime();
+		set_taskpool_task_time(game().get_gametime(), SchedulerTaskId::kRoadCheck);
+
 	} else {
 		++bo.cnt_built_;
 
@@ -5430,33 +5502,39 @@
 	}
 }
 
-// run over dueTasks map and returns task with lower duetime
-DefaultAI::ScheduleTasks DefaultAI::get_oldest_task(uint32_t const gametime) {
-
-	uint32_t oldestTaskTime = gametime;            // we are looking for jobs due before now
-	ScheduleTasks DueTask = ScheduleTasks::kIdle;  // default
-	taskDue[ScheduleTasks::kIdle] = gametime;
-
-	for (std::pair<ScheduleTasks, uint32_t> task : taskDue) {
-		if (task.second < oldestTaskTime) {
-			oldestTaskTime = task.second;
-			DueTask = task.first;
-		}
-	}
-	if ((gametime - oldestTaskTime) > 5000) {
-		scheduler_delay_counter_ += 1;
-	} else {
-		scheduler_delay_counter_ = 0;
-	}
-
-	if (scheduler_delay_counter_ > 10) {
-		log(" %d: AI: game speed too high, jobs are too late (now %2d seconds)\n",
-		player_number(),
-		static_cast<int32_t>((gametime - oldestTaskTime) / 1000));
-		scheduler_delay_counter_ = 0;
-	}
-
-	return DueTask;
+// Sets due_time based on job ID
+void DefaultAI::set_taskpool_task_time(const uint32_t gametime, const Widelands::SchedulerTaskId task) {
+
+	for (auto& item : taskPool) {
+		if (item.id == task) {
+			item.due_time = gametime;
+			return;
+		}
+	}
+
+	assert(false);
+}
+
+// Retrieves due time of the task based on its ID
+uint32_t DefaultAI::get_taskpool_task_time(const Widelands::SchedulerTaskId task) {
+	for (const auto& item : taskPool) {
+		if (item.id == task) {
+			return item.due_time;
+		}
+	}
+
+	assert (false);
+}
+
+// This performs one "iteration" of sorting based on due_time
+// We by design do not need full sorting...
+void DefaultAI::sort_task_pool() {
+	assert(!taskPool.empty());
+	for (int8_t i = taskPool.size() - 1; i > 0; --i) {
+		if (taskPool[i - 1].due_time > taskPool[i].due_time) {
+			std::iter_swap(taskPool.begin() + i - 1, taskPool.begin() + i);
+		}
+	}
 }
 
 // following two functions count mines of the same type (same output,
@@ -5468,6 +5546,7 @@
 	}
 	return count;
 }
+
 uint32_t DefaultAI::mines_built() const{
 	uint32_t count = 0;
 	for (const std::pair<const int, MineTypesObserver> m : mines_per_type) {
@@ -5499,13 +5578,13 @@
 // and needs to know what resourcess are missing for which player and so on.
 // By default it is off (see kPrintStats)
 // TODO(tiborb ?): - it would be nice to have this activated by a command line switch
-void DefaultAI::print_stats(uint32_t const gametime) {
+void DefaultAI::print_stats() {
 
 	if (!kPrintStats) {
-		taskDue[ScheduleTasks::kPrintStats] = std::numeric_limits<int32_t>::max();
+		set_taskpool_task_time(std::numeric_limits<int32_t>::max(), SchedulerTaskId::kPrintStats);
 		return;
 	}
-	taskDue[ScheduleTasks::kPrintStats] = gametime + 30 * 60 * 1000;
+
 
 	PlayerNumber const pn = player_number();
 

=== modified file 'src/ai/defaultai.h'
--- src/ai/defaultai.h	2015-11-11 09:52:55 +0000
+++ src/ai/defaultai.h	2015-11-21 18:26:32 +0000
@@ -85,26 +85,7 @@
 	enum class WoodPolicy : uint8_t {kDismantleRangers, kStopRangers, kAllowRangers};
 	enum class NewShip : uint8_t {kBuilt, kFoundOnLoad};
 	enum class PerfEvaluation : uint8_t {kForConstruction, kForDismantle};
-	enum class ScheduleTasks : uint8_t {
-		kBbuildableFieldsCheck,
-		kMineableFieldsCheck,
-		kRoadCheck,
-		kUnbuildableFCheck,
-		kCheckEconomies,
-		kProductionsitesStats,
-		kConstructBuilding,
-		kCheckProductionsites,
-		kCheckShips,
-		KMarineDecisions,
-		kCheckMines,
-		kWareReview,
-		kPrintStats,
-		kIdle,
-		kCheckMilitarysites,
-		kCheckTrainingsites,
-		kCountMilitaryVacant,
-		kCheckEnemySites
-	};
+
 	enum class Tribes : uint8_t {
 		kNone,
 		kBarbarians,
@@ -161,7 +142,7 @@
 	void update_buildable_field(BuildableField&, uint16_t = 6, bool = false);
 	void update_mineable_field(MineableField&);
 
-	void update_productionsite_stats(uint32_t);
+	void update_productionsite_stats();
 
 	// for productionsites
 	Widelands::BuildingNecessity check_building_necessity
@@ -170,7 +151,10 @@
 	Widelands::BuildingNecessity check_building_necessity
 		(uint8_t, uint32_t);
 
-	ScheduleTasks get_oldest_task(uint32_t);
+	void sort_task_pool();
+	void sort_by_priority();
+	void set_taskpool_task_time(uint32_t, Widelands::SchedulerTaskId);
+	uint32_t get_taskpool_task_time(Widelands::SchedulerTaskId);
 
 	bool construct_building(uint32_t);
 
@@ -201,10 +185,10 @@
 	bool check_trainingsites(uint32_t);
 	bool check_mines_(uint32_t);
 	bool check_militarysites(uint32_t);
-	bool marine_main_decisions(uint32_t);
+	bool marine_main_decisions();
 	bool check_ships(uint32_t);
 	bool check_enemy_sites(uint32_t);
-	void print_stats(uint32_t);
+	void print_stats();
 	// return single number of strength of vector of soldiers
 	int32_t calculate_strength(const std::vector<Widelands::Soldier*>);
 	uint32_t get_stocklevel_by_hint(size_t);
@@ -256,7 +240,7 @@
 	uint8_t type_;
 
 	// collect statistics on how many times which job was run
-	uint32_t schedStat[20] = {0};
+	uint32_t sched_stat_[20] = {0};
 
 	Widelands::Player* player_;
 	Widelands::TribeDescr const* tribe_;
@@ -291,7 +275,9 @@
 	std::list<WarehouseSiteObserver> warehousesites;
 	std::list<TrainingSiteObserver> trainingsites;
 	std::list<ShipObserver> allships;
-	std::map<ScheduleTasks, uint32_t> taskDue;
+	// This is a vector that is filled up on initiatlization
+	// and no items are added/removed afterwards
+	std::vector<SchedulerTask> taskPool;
 	std::map<uint32_t, EnemySiteObserver> enemy_sites;
 	// it will map mined material to observer
 	std::map<int32_t, MineTypesObserver> mines_per_type;