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

[SirVer]

This patch was send to me by fk who has difficulties accessing launchpad.

I did some changes to make it compile, but I did not review nor test the changes. So I do not fully know what the code actually does, but it has something to do with better selection of soldiers on attack.

[TiborB (tiborb95)]

Just note that this is based on seafaring-ai branch. So if you merge this...

And one comment about seafaring - few days ago I left seafaring game overnight (big map, had to use speed 1x) and it crashed.

It was not under gdb and it forgot about possibility to load savegame...

So some further testing will be needed.

If somebody wants to help with this...

[SirVer (sirver)]

> Just note that this is based on seafaring-ai branch. So if you merge this...

My bad. Fixed by rebasing on trunk and push --overwriting.

[SirVer (sirver)]

I looked at this now. I think sort_soldiers should just be a std::sort with a custom comparator - the current version is fragile. That will make this patch very small.

Is somebody interested in picking up this branch? I think fk does not want to work on it anymore.

review: Needs Fixing

[Martin Schmidt (martinschmidt)]

Can I just push to this branch or should I use a new one?
I did not change the semnatics but rather replace the sorting by
stable_sort or partial_sort (which returns the k smallest elements but is unstable)

However, I am not sure whether an unstable sorting algorithm can cause desyncts, since the
implementation may change the result. Doing a source code search it seems that Widelands uses both, std::sort and std::stable_sort.

At the moment we need the SoldierPriority structure to distribute the attacking soldiers evenly over all military sites (in case of equal abilities)
I think the most elegant solution would be to enforce the soldiers being sorted by ability in the militarysite itself and allow a soldier to query its position.
This would allow to sort Soldiers instead of SoldierPriority and would solve all kinds of sorting problems:
- find soldiers for attacking/defending/healing (default: strongest)
- drop least suited soldier for upgrading (default: weakest)
- kicking out any soldier (by the player or for replacement/training)

And at least the above operations does not destroy the sorting.
Only new arriving soldiers would need to be inserted.
Possible replacements for std::vector<Soldier>:
- std::deque

However, this would requiere a larger modification of the source code and needs more discussing.

[fk (fredkuijper)]

@SirVer
Actually I am sorry for introducing this code snippet in this way, I understand that I should have done the merge, testing etcetera myself.

"sort_soldiers should just be a std::sort with a custom comparator"

Indeed, I am new to STL and haven't found a good manual about it yet. It shouldn't take that many lines as in my code.

"I think fk does not want to work on it anymore."

In a certain way you are right, I'm not really the most suitable person to do so. Actually it surprises me that no one has done this before, for an experienced programmer (with STL) it should take half an hour at most, and it is really fun to play the game this way. It is a game changer with benefits for both sides, both human and AI, that gives a more polished game experience. And even with the code in this primitive state it would already function well, I am after all an experienced programmer (but not with STL), there is not much that could go wrong and the test were promising. If I only know how to download the involved branch than I would like do the tests.

[fk (fredkuijper)]

@Martin
"sorted by ability in the militarysite itself"

That makes sense, for know I could say that both appproaches (mine and yours) will not collide.

[Martin Schmidt (martinschmidt)]

Your patch was really useful, I just changed the sorting to stl and that's it. I also tried a short game and it really makes a difference seeing soldiers coming from all military builings in range to attack instead of weaking one building totally.
Here is the patch:

=== modified file 'src/logic/player.cc'
--- src/logic/player.cc 2014-12-20 22:03:47 +0000
+++ src/logic/player.cc 2015-02-16 14:32:33 +0000
@@ -100,31 +100,26 @@
  int priority; // (strength + 1) * health - position in building.
 };

+/**
+* Find the strongest players with highest priority
+*/
+bool compare_soldiers(const SoldierPriority& a, const SoldierPriority& b) {
+ return a.priority > b.priority;
+}
+
 void sort_soldiers(std::vector<SoldierPriority>* soldiers,
- uint32_t max = std::numeric_limits<uint32_t>::max()) {
- std::vector<SoldierPriority> temp;
- SoldierPriority soldier;
- uint32_t left = soldiers->size();
-
- while (left) {
- int32_t maxlevel = -1;
- uint32_t pos = 0;
- uint32_t maxpos = 0;
- for (const SoldierPriority& soldier_priority : *soldiers) {
- const int32_t level = soldier_priority.priority;
- if (level > maxlevel) {
- maxlevel = level;
- maxpos = pos;
- soldier.soldier = soldier_priority.soldier;
- soldier.priority = level;
- }
- pos++;
- }
- temp.push_back(soldier);
- soldiers->erase(soldiers->begin() + maxpos);
- left--;
+ uint32_t max = std::numeric_limits<uint32_t>::max()) {
+ if (max >= soldiers->size()) {
+ return;
  }
- soldiers->insert(soldiers->end(), temp.begin(), temp.begin() + std::min<int>(max, temp.size()));
+
+ std::stable_sort(soldiers->begin(), soldiers->end(), compare_soldiers);
+ // Can an unstable sorting algorithm cause desyncts or are the implementations
+ // of std algorithms guaranteed to return the same (possibly non-stable)
+ // sorting? If yes, partial_sort may be favourable
+ // std::partial_sort(soldiers->begin(), soldiers->begin() + max,
+ // soldiers->end(), compare_soldiers);
+ soldiers->resize(max);
 }

 }

[SirVer (sirver)]

Mars, could you just push and reuse this branch please?

On my phone, will have a closer look from home or tomorrow.

> Am 16.02.2015 um 15:33 schrieb Martin Schmidt <email address hidden>:
>
> Your patch was really useful, I just changed the sorting to stl and that's it. I also tried a short game and it really makes a difference seeing soldiers coming from all military builings in range to attack instead of weaking one building totally.
> Here is the patch:
>
> === modified file 'src/logic/player.cc'
> --- src/logic/player.cc 2014-12-20 22:03:47 +0000
> +++ src/logic/player.cc 2015-02-16 14:32:33 +0000
> @@ -100,31 +100,26 @@
> int priority; // (strength + 1) * health - position in building.
> };
>
> +/**
> +* Find the strongest players with highest priority
> +*/
> +bool compare_soldiers(const SoldierPriority& a, const SoldierPriority& b) {
> + return a.priority > b.priority;
> +}
> +
> void sort_soldiers(std::vector<SoldierPriority>* soldiers,
> - uint32_t max = std::numeric_limits<uint32_t>::max()) {
> - std::vector<SoldierPriority> temp;
> - SoldierPriority soldier;
> - uint32_t left = soldiers->size();
> -
> - while (left) {
> - int32_t maxlevel = -1;
> - uint32_t pos = 0;
> - uint32_t maxpos = 0;
> - for (const SoldierPriority& soldier_priority : *soldiers) {
> - const int32_t level = soldier_priority.priority;
> - if (level > maxlevel) {
> - maxlevel = level;
> - maxpos = pos;
> - soldier.soldier = soldier_priority.soldier;
> - soldier.priority = level;
> - }
> - pos++;
> - }
> - temp.push_back(soldier);
> - soldiers->erase(soldiers->begin() + maxpos);
> - left--;
> + uint32_t max = std::numeric_limits<uint32_t>::max()) {
> + if (max >= soldiers->size()) {
> + return;
> }
> - soldiers->insert(soldiers->end(), temp.begin(), temp.begin() + std::min<int>(max, temp.size()));
> +
> + std::stable_sort(soldiers->begin(), soldiers->end(), compare_soldiers);
> + // Can an unstable sorting algorithm cause desyncts or are the implementations
> + // of std algorithms guaranteed to return the same (possibly non-stable)
> + // sorting? If yes, partial_sort may be favourable
> + // std::partial_sort(soldiers->begin(), soldiers->begin() + max,
> + // soldiers->end(), compare_soldiers);
> + soldiers->resize(max);
> }
>
> }
>
>
> --
> https://code.launchpad.net/~widelands-dev/widelands/find_attack_soldiers/+merge/245276
> You proposed lp:~widelands-dev/widelands/find_attack_soldiers for merging.

[Martin Schmidt (martinschmidt)]

What is the best way to proceed for establishing the invariant that soldiers in the military building have to be sorted:
- create a bug report / wishlist,
- create a blue print or
- start coding and propose a merge request ?

[TiborB (tiborb95)]

Generally:

- create a bug report (optional but I recommend this :) )
- start coding and create own branch
- propose merging

2015-02-18 18:09 GMT+01:00 Martin Schmidt <email address hidden>:

> What is the best way to proceed for establishing the invariant that
> soldiers in the military building have to be sorted:
> - create a bug report / wishlist,
> - create a blue print or
> - start coding and propose a merge request ?
> --
>
> https://code.launchpad.net/~widelands-dev/widelands/find_attack_soldiers/+merge/245276
> Your team Widelands Developers is subscribed to branch
> lp:~widelands-dev/widelands/find_attack_soldiers.
>
> _______________________________________________
> Mailing list: https://launchpad.net/~widelands-dev
> Post to : <email address hidden>
> Unsubscribe : https://launchpad.net/~widelands-dev
> More help : https://help.launchpad.net/ListHelp
>

[SirVer (sirver)]

martin, please ping this merge request when you feel it is ready. Launchpad is not sending notifications for new commits.

[Martin Schmidt (martinschmidt)]

ok, basic functionality is implemented, but still, a few things have to be done, e.g.
- update military site window when the user changes the soldier preference
(at the moment you have to close and open the window again to see the soldiers in the right ordering)
- make sure healthy soldiers defend when the preference is set for rookies (instead of wounded ones who have lower power and are therefore prefered)

nice to have: when upgrading soldiers/occupying a building send the best soldiers available (according to the preference set)

keeping the soldiers sorted permanently is more difficult than I expected, the soldiercontrol interface does not offer a unified way of storing them, so for military sites they are upcasted from workers each time.

[SirVer (sirver)]

> - update military site window when the user changes the soldier preference
(at the moment you have to close and open the window again to see the soldiers in the right ordering)

use a Boost::signal for that - i.e. the militarysite has one, and the ui can connect to it to update it whenever something is changed.

> - make sure healthy soldiers defend when the preference is set for rookies (instead of wounded ones who have lower power and are therefore prefered)

How do you want to deal with that? It sounds like you want a different sorting for this.

> nice to have: when upgrading soldiers/occupying a building send the best soldiers available (according to the preference set)

Actually that has been discussed before. It makes for an interesting strategic element when new buildings are not immediately manned with an invincible army. It gives the other player an opportunity to strike. I think this is cool and more dynamic than immediately having the best soldiers at the front.

> keeping the soldiers sorted permanently is more difficult than I expected, the soldiercontrol interface does not offer a unified way of storing them, so for military sites they are upcasted from workers each time.

Why not change that? Remove the soldier control interface and instead make a HasSoldier container that can be owned by a building and handles all soldiers in the building. This gets rid of some inheritance which is usually bad and will solve your case. Just a suggestion of course.

Is this branch ready for review/merging now or do you still want to work on it?

[TiborB (tiborb95)]

I second SirVer's question: Is this branch ready for review/merging now or do you still want to work on it?

It seems there is some work to do here yet.

[Martin Schmidt (martinschmidt)]

I guess it is ready to merge.
What is implemented:
 - defend with "strongest", attack with "strongest"
 - drop "weakest", but only unwounded soldiers (because wounded soldiers will heal)
I am quite happy with how it works and feels playing with this branch.

What is missing:
 - the list of soldiers in a militarysite is not updated until the windows of the militarysite is
   closed and opened again (this is neccessary when new soldiers arrive, soldiers return from battle,
   soldiers are drop or the priority (weakest/strongest) for a militarysite is changed.
I tried to implement this, however I have no idea how to do this and give up on this.
But you are right, I should have responeded earlier.

"weak" and "strong" refers to the chosen priority.
For priority weak, weak soldiers are "strong".

[TiborB (tiborb95)]

" the list of soldiers in a militarysite is not updated until the windows of the militarysite is..." - this would be very useful, but personally I am not able to help with this :(

[GunChleoc (gunchleoc)]

Can you create a bug report for this, so we can take care of it in a separate branch? I have worked with signals before on the UI and might be able to figure it out, so I would put it on my todo-list.

[Martin Schmidt (martinschmidt)]

I will create a bug report as soon as this branch is merged.

[TiborB (tiborb95)]

I looked at the code and run some AI-only game - no problems. I think it can go.

review: Approve

[TiborB (tiborb95)]

Is this waiting only for a volunteer who would merge it to trunk? I can do it....

[GunChleoc (gunchleoc)]

We still have a reviewer saying "Needs fixing", which is why I didn't merge it yet. Let's wait for SirVer to get back.

[SirVer (sirver)]

sorry - did not see that.

review: Approve

[GunChleoc (gunchleoc)]

I just found that this breaks the regression tests. The problem is with test/maps/lua_testsuite.wmf/scripting/test_lua_in_game.lua. The failing test is function militarysite_tests:test_no_space().

review: Needs Fixing

[Martin Schmidt (martinschmidt)]

ok, thanks, I will look into this

[bunnybot (widelandsofficial)]

Hi, I am bunnybot (https://github.com/widelands/bunnybot).

I am keeping the source branch lp:~widelands-dev/widelands/find_attack_soldiers mirrored to
  https://github.com/widelands/widelands/tree/_widelands_dev_widelands_find_attack_soldiers

The latest continuous integration build can always be found here:
  https://travis-ci.org/widelands/widelands/branches
Please do not merge without making sure that it passes.

You can give me commands by starting a line with @bunnybot <command>. I understand:
 merge: Merges the source branch into the target branch, closing the pull request.

[bunnybot (widelandsofficial)]

Travis build 126 has changed state to: failed. Details: https://travis-ci.org/widelands/widelands/builds/99797556.

[bunnybot (widelandsofficial)]

Travis build 126 has changed state to: failed. Details: https://travis-ci.org/widelands/widelands/builds/99797556.

[bunnybot (widelandsofficial)]

Travis build 126 has changed state to: failed. Details: https://travis-ci.org/widelands/widelands/builds/99797556.

[SirVer (sirver)]

I do not feel like going over this and clean it up. I do not understand most of the intentions.

Martin, are you still interested to work on this? Otherwise I will drop this branch in a few days.

[bunnybot (widelandsofficial)]

Bunnybot encountered an error while working on this merge proposal:

<urlopen error [Errno -2] Name or service not known>

[bunnybot (widelandsofficial)]

Bunnybot encountered an error while working on this merge proposal:

<urlopen error [Errno -2] Name or service not known>

[bunnybot (widelandsofficial)]

Bunnybot encountered an error while working on this merge proposal:

<urlopen error [Errno -2] Name or service not known>

[bunnybot (widelandsofficial)]

Bunnybot encountered an error while working on this merge proposal:

<urlopen error [Errno -2] Name or service not known>

[Martin Schmidt (martinschmidt)]

> I do not feel like going over this and clean it up. I do not understand most
> of the intentions.
>
> Martin, are you still interested to work on this? Otherwise I will drop this
> branch in a few days.

You can delete this branch, I had too much trouble with it.

[SirVer (sirver)]

Abandoning this then.

=== modified file 'src/ai/defaultai.cc'
--- src/ai/defaultai.cc	2016-01-18 19:35:25 +0000
+++ src/ai/defaultai.cc	2016-01-24 08:32:15 +0000
@@ -4342,9 +4342,9 @@
 		if (ms->economy().warehouses().size()) {
 			uint32_t const j = ms->soldier_capacity();
 
-			if (MilitarySite::kPrefersRookies != ms->get_soldier_preference()) {
+			if (Soldier::kPrefersRookies != ms->get_soldier_preference()) {
 				game().send_player_militarysite_set_soldier_preference(
-				   *ms, MilitarySite::kPrefersRookies);
+				   *ms, Soldier::kPrefersRookies);
 			} else if (j > 1) {
 				game().send_player_change_soldier_capacity(*ms, (j > 2) ? -2 : -1);
 			}
@@ -4400,9 +4400,9 @@
 			changed = true;
 
 			// and also set preference to Heroes
-			if (MilitarySite::kPrefersHeroes != ms->get_soldier_preference()) {
+			if (Soldier::kPrefersHeroes != ms->get_soldier_preference()) {
 				game().send_player_militarysite_set_soldier_preference(
-				   *ms, MilitarySite::kPrefersHeroes);
+				   *ms, Soldier::kPrefersHeroes);
 				changed = true;
 			}
 
@@ -4411,9 +4411,9 @@
 		} else {  // otherwise decrease soldiers
 			uint32_t const j = ms->soldier_capacity();
 
-			if (MilitarySite::kPrefersRookies != ms->get_soldier_preference()) {
+			if (Soldier::kPrefersRookies != ms->get_soldier_preference()) {
 				game().send_player_militarysite_set_soldier_preference(
-				   *ms, MilitarySite::kPrefersRookies);
+				   *ms, Soldier::kPrefersRookies);
 			} else if (j > 1) {
 				game().send_player_change_soldier_capacity(*ms, (j > 2) ? -2 : -1);
 			}
 
=== modified file 'src/logic/map_objects/tribes/militarysite.cc'
--- src/logic/map_objects/tribes/militarysite.cc	2016-01-06 19:11:20 +0000
+++ src/logic/map_objects/tribes/militarysite.cc	2016-01-24 08:32:15 +0000
@@ -19,6 +19,7 @@
 
 #include "logic/map_objects/tribes/militarysite.h"
 
+#include <algorithm>
 #include <clocale>
 #include <cstdio>
 #include <memory>
@@ -88,26 +89,22 @@
 =============================
 */
 
-MilitarySite::MilitarySite(const MilitarySiteDescr & ms_descr) :
+MilitarySite::MilitarySite(const MilitarySiteDescr& ms_descr) :
 Building(ms_descr),
-m_didconquer  (false),
-m_capacity    (ms_descr.get_max_number_of_soldiers()),
-m_nexthealtime(0),
-m_soldier_preference(ms_descr.m_prefers_heroes_at_start ? kPrefersHeroes : kPrefersRookies),
+m_didconquer(false),
+m_capacity(ms_descr.get_max_number_of_soldiers()),
+m_soldier_preference(ms_descr.m_prefers_heroes_at_start ? Soldier::kPrefersHeroes : Soldier::kPrefersRookies),
+m_next_swap_soldiers_time(0),
 m_soldier_upgrade_try(false),
 m_doing_upgrade_request(false)
 {
-	m_next_swap_soldiers_time = 0;
 }
 
-
-MilitarySite::~MilitarySite()
-{
+MilitarySite::~MilitarySite() {
 	assert(!m_normal_soldier_request);
 	assert(!m_upgrade_soldier_request);
 }
 
-
 /**
 ===============
 Display number of soldiers.
@@ -275,34 +272,33 @@
 	return 0;
 }
 
-
 /*
- * Returns the least wanted soldier -- If player prefers zero-level guys,
- * the most trained soldier is the "weakest guy".
+ * Returns the least wanted soldier that is fully healed
+ * Wounded soldiers are ignored since they are supposed to be healed
+ * If player prefers rookies guys, the most trained soldier is the "weakest guy".
  */
-
-Soldier *
-MilitarySite::find_least_suited_soldier()
-{
-	const std::vector<Soldier *> present = present_soldiers();
-	const int32_t multiplier = kPrefersHeroes == m_soldier_preference ? -1 : 1;
-	int worst_soldier_level = INT_MIN;
-	Soldier * worst_soldier = nullptr;
-	for (Soldier* sld : present) {
-		int this_soldier_level = multiplier * static_cast<int> (sld->get_level(atrTotal));
-		if (this_soldier_level > worst_soldier_level)
-		{
-			worst_soldier_level = this_soldier_level;
-			worst_soldier = sld;
+Soldier* MilitarySite::find_least_suited_soldier() {
+
+	const std::vector<Soldier*> present = present_soldiers();
+	if (present.empty()) {
+		return nullptr;
+	}
+
+	for (auto rit = present.rbegin(); rit != present.rend(); ++rit) {
+		Soldier* s = (*rit);
+		if (s->get_current_hitpoints() == s->get_max_hitpoints()) {
+			return s;
 		}
 	}
-	return worst_soldier;
+
+	// if no fully healed soldier is found, return the last soldier
+	// this is the most wounded one
+	return present.back();
 }
 
-
 /*
- * Kicks out the least wanted soldier -- If player prefers zero-level guys,
- * the most trained soldier is the "weakest guy".
+ * Kicks out the least wanted soldier -- If player prefers rookies,
+ * the most trained soldier is the least suited guy.
  *
  * Returns false, if there is only one soldier (won't drop last soldier)
  * or the new guy is not better than the weakest one present, in which case
@@ -314,40 +310,26 @@
  * arrives.
  */
 
-bool
-MilitarySite::drop_least_suited_soldier(bool new_soldier_has_arrived, Soldier * newguy)
-{
-	const std::vector<Soldier *> present = present_soldiers();
-
-	// If I have only one soldier, and the  new guy is not here yet, I can't release.
-	if (new_soldier_has_arrived || 1 < present.size())
-	{
-		Soldier * kickoutCandidate = find_least_suited_soldier();
-
-		// If the arriving guy is worse than worst present, I wont't release.
-		if (nullptr != newguy && nullptr != kickoutCandidate)
-		{
-			int32_t old_level = kickoutCandidate->get_level(atrTotal);
-			int32_t new_level = newguy->get_level(atrTotal);
-			if (kPrefersHeroes == m_soldier_preference && old_level >= new_level)
-			{
-				return false;
-			}
-			else
-			if (kPrefersRookies == m_soldier_preference && old_level <= new_level)
-			{
-				return false;
-			}
-		}
-
-		// Now I know that the new guy is worthy.
-		if (nullptr != kickoutCandidate)
-		{
-			Game & game = dynamic_cast<Game&>(owner().egbase());
-			kickoutCandidate->reset_tasks(game);
-			kickoutCandidate->start_task_leavebuilding(game, true);
-			return true;
-		}
+bool MilitarySite::drop_least_suited_soldier(bool new_soldier_has_arrived, Soldier* newguy) {
+
+	std::vector<Soldier*> present = present_soldiers();
+
+	// respect the minimal soldier capacity
+	if (!new_soldier_has_arrived && present.size() <= min_soldier_capacity()) {
+		return false;
+	}
+
+	Soldier* kickoutCandidate = find_least_suited_soldier();
+
+	// If the arriving guy is worse than worst present, do not drop a soldier
+	if (kickoutCandidate != nullptr &&
+	    (newguy == nullptr ||
+	     Soldier::CompareSoldier(m_soldier_preference)(newguy, kickoutCandidate))) {
+
+		Game& game = dynamic_cast<Game&>(owner().egbase());
+		kickoutCandidate->reset_tasks(game);
+		kickoutCandidate->start_task_leavebuilding(game, true);
+		return true;
 	}
 	return false;
 }
@@ -677,7 +659,6 @@
 	return false;
 }
 
-
 /**
  * \return \c true if the soldier is currently present and idle in the building.
  */
@@ -689,7 +670,6 @@
 		soldier.get_position() == get_position();
 }
 
-// TODO(sirver): This method should probably return a const reference.
 std::vector<Soldier *> MilitarySite::present_soldiers() const
 {
 	std::vector<Soldier *> soldiers;
@@ -701,10 +681,11 @@
 			}
 		}
 	}
+
+	std::sort(soldiers.begin(), soldiers.end(), Soldier::CompareSoldier(m_soldier_preference));
 	return soldiers;
 }
 
-// TODO(sirver): This method should probably return a const reference.
 std::vector<Soldier *> MilitarySite::stationed_soldiers() const
 {
 	std::vector<Soldier *> soldiers;
@@ -934,7 +915,7 @@
 
 	// feature request 1247384 in launchpad bugs: Conquered buildings tend to
 	// be in a hostile area; typically players want heroes there.
-	set_soldier_preference(kPrefersHeroes);
+	set_soldier_preference(Soldier::kPrefersHeroes);
 }
 
 /// Calculates whether the military presence is still kept and \returns true if.
@@ -1056,31 +1037,32 @@
  * The routine returns true if upgrade request thresholds have changed. This information could be
  * used to decide whether the soldier-Request should be upgraded.
  */
-bool
-MilitarySite::update_upgrade_requirements()
-{
+bool MilitarySite::update_upgrade_requirements() {
 	int32_t soldier_upgrade_required_min = m_soldier_upgrade_requirements.get_min();
 	int32_t soldier_upgrade_required_max = m_soldier_upgrade_requirements.get_max();
 
-	if (kPrefersHeroes != m_soldier_preference && kPrefersRookies != m_soldier_preference)
-	{
-		log("MilitarySite::swapSoldiers: error: Unknown player preference %d.\n", m_soldier_preference);
+	if (Soldier::kPrefersHeroes != m_soldier_preference &&
+	    Soldier::kPrefersRookies != m_soldier_preference) {
+		log("MilitarySite::swapSoldiers: error: Unknown player preference %d.\n",
+		    m_soldier_preference);
 		m_soldier_upgrade_try = false;
 		return false;
 	}
 
-	// Find the level of the soldier that is currently least-suited.
-	Soldier * worst_guy = find_least_suited_soldier();
+	// make sure worst_guy is defined
+	Soldier* worst_guy = find_least_suited_soldier();
+
 	if (worst_guy == nullptr) {
-		// There could be no soldier in the militarysite right now. No reason to freak out.
+		// There could be no soldier in the militarysite right now
 		return false;
 	}
+
 	int32_t wg_level = worst_guy->get_level(atrTotal);
 
 	// Micro-optimization: I assume that the majority of military sites have only level-zero
 	// soldiers and prefer rookies. Handle them separately.
 	m_soldier_upgrade_try = true;
-	if (kPrefersRookies == m_soldier_preference) {
+	if (Soldier::kPrefersRookies == m_soldier_preference) {
 		if (0 == wg_level)
 			{
 				m_soldier_upgrade_try = false;
@@ -1089,8 +1071,10 @@
 	}
 
 	// Now I actually build the new requirements.
-	int32_t reqmin = kPrefersHeroes == m_soldier_preference ? 1 + wg_level : 0;
-	int32_t reqmax = kPrefersHeroes == m_soldier_preference ? SHRT_MAX : wg_level - 1;
+	int32_t reqmin =
+	   Soldier::kPrefersHeroes == m_soldier_preference ? 1 + wg_level : 0;
+	int32_t reqmax =
+	   Soldier::kPrefersHeroes == m_soldier_preference ? SHRT_MAX : wg_level - 1;
 
 	bool maxchanged = reqmax != soldier_upgrade_required_max;
 	bool minchanged = reqmin != soldier_upgrade_required_min;
@@ -1111,12 +1095,10 @@
 
 // setters
 
-void
-MilitarySite::set_soldier_preference(MilitarySite::SoldierPreference p)
-{
-	assert(kPrefersHeroes == p || kPrefersRookies == p);
+void MilitarySite::set_soldier_preference(Soldier::SoldierPreference p) {
+	assert(Soldier::kPrefersHeroes == p ||
+	       Soldier::kPrefersRookies == p);
 	m_soldier_preference = p;
 	m_next_swap_soldiers_time = 0;
 }
-
 }
 
=== modified file 'src/logic/map_objects/tribes/militarysite.h'
--- src/logic/map_objects/tribes/militarysite.h	2016-01-06 19:11:20 +0000
+++ src/logic/map_objects/tribes/militarysite.h	2016-01-24 08:32:15 +0000
@@ -27,6 +27,7 @@
 #include "logic/map_objects/attackable.h"
 #include "logic/map_objects/tribes/building.h"
 #include "logic/map_objects/tribes/requirements.h"
+#include "logic/map_objects/tribes/soldier.h"
 #include "logic/map_objects/tribes/soldiercontrol.h"
 #include "scripting/lua_table.h"
 
@@ -34,6 +35,7 @@
 
 class Soldier;
 class World;
+class MilitarySite;
 
 class MilitarySiteDescr : public BuildingDescr {
 public:
@@ -72,13 +74,6 @@
 	MO_DESCR(MilitarySiteDescr)
 
 public:
-	// I assume elsewhere, that enum SoldierPreference fits to uint8_t.
-	enum SoldierPreference  : uint8_t {
-		kNoPreference,
-		kPrefersRookies,
-		kPrefersHeroes,
-	};
-
 	MilitarySite(const MilitarySiteDescr &);
 	virtual ~MilitarySite();
 
@@ -122,8 +117,8 @@
 
 	void update_soldier_request(bool i = false);
 
-	void set_soldier_preference(SoldierPreference);
-	SoldierPreference get_soldier_preference() const {
+	void set_soldier_preference(Soldier::SoldierPreference);
+	Soldier::SoldierPreference get_soldier_preference() const {
 			return m_soldier_preference;
 	}
 
@@ -149,7 +144,7 @@
 	void update_normal_soldier_request();
 	void update_upgrade_soldier_request();
 	bool incorporate_upgraded_soldier(EditorGameBase & game, Soldier & s);
-	Soldier * find_least_suited_soldier();
+	Soldier* find_least_suited_soldier();
 	bool drop_least_suited_soldier(bool new_has_arrived, Soldier * s);
 
 
@@ -172,7 +167,7 @@
 		bool        stayhome;
 	};
 	std::vector<SoldierJob> m_soldierjobs;
-	SoldierPreference m_soldier_preference;
+	Soldier::SoldierPreference m_soldier_preference;
 	int32_t m_next_swap_soldiers_time;
 	bool m_soldier_upgrade_try; // optimization -- if everybody is zero-level, do not downgrade
 	bool m_doing_upgrade_request;
 
=== modified file 'src/logic/map_objects/tribes/production_program.cc'
--- src/logic/map_objects/tribes/production_program.cc	2016-01-24 07:45:11 +0000
+++ src/logic/map_objects/tribes/production_program.cc	2016-01-24 08:32:15 +0000
@@ -1467,9 +1467,8 @@
 	(Game & game, ProductionSite & ps) const
 {
 	SoldierControl & ctrl = dynamic_cast<SoldierControl &>(ps);
-	const std::vector<Soldier *> soldiers = ctrl.present_soldiers();
-	const std::vector<Soldier *>::const_iterator soldiers_end =
-		soldiers.end();
+	const std::vector<Soldier*> soldiers = ctrl.present_soldiers();
+	const std::vector<Soldier*>::const_iterator soldiers_end = soldiers.end();
 	std::vector<Soldier *>::const_iterator it = soldiers.begin();
 
 	ps.molog
 
=== modified file 'src/logic/map_objects/tribes/soldier.cc'
--- src/logic/map_objects/tribes/soldier.cc	2016-01-18 05:12:51 +0000
+++ src/logic/map_objects/tribes/soldier.cc	2016-01-24 08:32:15 +0000
@@ -1605,6 +1605,12 @@
 	schedule_destroy(game);
 }
 
+float Soldier::compute_power() const {
+	// (MaxAttack+MinAttack)/2)*(100/(100-Defense))*(100/(100-Evade))*CurHP
+	return ((get_max_attack() + get_max_attack()) / 2.0) * (100.0 / (100.0 - get_defense())) *
+	       (100.0 / (100.0 - get_evade())) * get_current_hitpoints();
+}
+
 /**
  * Accept a Bob if it is a Soldier, is not dead and is running taskAttack or
  * taskDefense.
 
=== modified file 'src/logic/map_objects/tribes/soldier.h'
--- src/logic/map_objects/tribes/soldier.h	2016-01-06 19:11:20 +0000
+++ src/logic/map_objects/tribes/soldier.h	2016-01-24 08:32:15 +0000
@@ -30,10 +30,6 @@
 
 namespace Widelands {
 
-// Constants used to launch attacks
-#define WEAKEST   0
-#define STRONGEST 1
-
 class EditorGameBase;
 class Battle;
 
@@ -159,7 +155,63 @@
 	MO_DESCR(SoldierDescr)
 
 public:
-	Soldier(const SoldierDescr &);
+	Soldier(const SoldierDescr&);
+
+	enum SoldierPreference : uint8_t {
+		kNoPreference,  // useful if no ordering is prefered -> ordered by serial
+		kPrefersRookies,
+		kPrefersHeroes,
+	};
+
+	struct CompareSoldier {
+
+		CompareSoldier(const SoldierPreference preference = kPrefersHeroes)
+		   : m_preference(preference) {
+		}
+
+		bool operator()(const Soldier* s, const Soldier* t) {
+
+			Serial serial_s = s->serial();
+			Serial serial_t = t->serial();
+
+			if (m_preference == kNoPreference) {
+				return s->serial() < t->serial();
+			}
+
+			// independent of preference, prefer healthy soldiers
+			// percentage of health s > percentage of health t
+			// a1 / a2 > b1 / b2 iff a1*b2 > b1*a2
+			uint32_t health_s = s->get_current_hitpoints() * t->get_max_hitpoints();
+			uint32_t health_t = t->get_current_hitpoints() * s->get_max_hitpoints();
+
+			if (health_s > health_t) {
+				return true;
+			}
+			if (health_t > health_s) {
+				return false;
+			}
+
+			// the serial is added to have some "randomness" in the ordering
+			// in case of equal power, they seem to be selected at random
+			// effect: attacking soldiers are distributed to military sites in range
+			float power_s = s->compute_power() + (serial_s % 5);
+			float power_t = t->compute_power() + (serial_t % 5);
+
+			if (power_s - power_t < 1e-5) {
+				return m_preference == kPrefersRookies;
+			}
+
+			if (power_t - power_s < 1e-5) {
+				return m_preference == kPrefersHeroes;
+			}
+
+			return s->serial() < t->serial();
+		}
+
+	private:
+		const SoldierPreference m_preference;
+	};
+
 
 	void init(EditorGameBase &) override;
 	void cleanup(EditorGameBase &) override;
@@ -245,6 +297,7 @@
 	void move_in_battle_update(Game &, State &);
 	void die_update(Game &, State &);
 	void die_pop(Game &, State &);
+	float compute_power() const;
 
 	void send_space_signals(Game &);
 	bool stay_home();
 
=== modified file 'src/logic/map_objects/tribes/trainingsite.cc'
--- src/logic/map_objects/tribes/trainingsite.cc	2016-01-18 19:35:25 +0000
+++ src/logic/map_objects/tribes/trainingsite.cc	2016-01-24 08:32:15 +0000
@@ -408,14 +408,11 @@
 	return 0;
 }
 
-
-std::vector<Soldier *> TrainingSite::present_soldiers() const
-{
+std::vector<Soldier*> TrainingSite::present_soldiers() const {
 	return m_soldiers;
 }
 
-std::vector<Soldier *> TrainingSite::stationed_soldiers() const
-{
+std::vector<Soldier*> TrainingSite::stationed_soldiers() const {
 	return m_soldiers;
 }
 
 
=== modified file 'src/logic/map_objects/tribes/warehouse.cc'
--- src/logic/map_objects/tribes/warehouse.cc	2016-01-08 21:00:39 +0000
+++ src/logic/map_objects/tribes/warehouse.cc	2016-01-24 08:32:15 +0000
@@ -1435,9 +1435,8 @@
 /*
  * SoldierControl implementations
  */
-std::vector<Soldier *> Warehouse::present_soldiers() const
-{
-	std::vector<Soldier *> rv;
+std::vector<Soldier*> Warehouse::present_soldiers() const {
+	std::vector<Soldier*> rv;
 
 	DescriptionIndex const soldier_index = owner().tribe().soldier();
 	IncorporatedWorkers::const_iterator sidx = m_incorporated_workers.find(soldier_index);
 
=== modified file 'src/logic/player.cc'
--- src/logic/player.cc	2016-01-17 09:54:31 +0000
+++ src/logic/player.cc	2016-01-24 08:32:15 +0000
@@ -19,6 +19,7 @@
 
 #include "logic/player.h"
 
+#include <algorithm>
 #include <memory>
 
 #include <boost/bind.hpp>
@@ -54,6 +55,7 @@
 #include "sound/sound_handler.h"
 #include "wui/interactive_player.h"
 
+namespace Widelands {
 
 namespace {
 
@@ -88,12 +90,8 @@
 	}
 }
 
-
-
 }
 
-namespace Widelands {
-
 const RGBColor Player::Colors[MAX_PLAYERS] = {
 	RGBColor(2,     2, 198),  // blue
 	RGBColor(255,  41,   0),  // red
@@ -717,7 +715,7 @@
 {
 	if (&imm.owner() == this)
 		if (upcast(MilitarySite, milsite, &imm))
-			milsite->set_soldier_preference(static_cast<MilitarySite::SoldierPreference>(m_soldier_preference));
+			milsite->set_soldier_preference(static_cast<Soldier::SoldierPreference>(m_soldier_preference));
 }
 
 
@@ -891,57 +889,66 @@
 */
 
 /**
- * Get a list of soldiers that this player can use to attack the
- * building at the given flag.
- *
- * The default attack should just take the first N soldiers of the
- * returned array.
- */
-// TODO(unknown): Perform a meaningful sort on the soldiers array.
-uint32_t Player::find_attack_soldiers
-	(Flag & flag, std::vector<Soldier *> * soldiers, uint32_t nr_wanted)
-{
-	uint32_t count = 0;
+* Return the number of soldiers that can attack the building at the
+* given flag, limited to \param nr_wanted.
+*
+* If \param soldiers != NULL it will be filled with soldiers selected
+* on health and strength while trying to select the soldiers from
+* multiple buildings.
+*/
+uint32_t
+Player::find_attack_soldiers(Flag& flag, std::vector<Soldier*>* soldiers, uint32_t nr_wanted) {
+	std::vector<Soldier*> attackers_all;
+	uint32_t nr_available = 0;
 
 	if (soldiers)
 		soldiers->clear();
 
-	Map & map = egbase().map();
-	std::vector<BaseImmovable *> flags;
+	Map& map = egbase().map();
+	std::vector<BaseImmovable*> flags;
 
-	map.find_reachable_immovables_unique
-		(Area<FCoords>(map.get_fcoords(flag.get_position()), 25),
-		 flags,
-		 CheckStepDefault(MOVECAPS_WALK),
-		 FindFlagOf(FindImmovablePlayerMilitarySite(*this)));
+	map.find_reachable_immovables_unique(Area<FCoords>(map.get_fcoords(flag.get_position()), 25),
+	                                     flags,
+	                                     CheckStepDefault(MOVECAPS_WALK),
+	                                     FindFlagOf(FindImmovablePlayerMilitarySite(*this)));
 
 	if (flags.empty())
 		return 0;
 
-	for (BaseImmovable * temp_flag : flags) {
-		upcast(Flag, attackerflag, temp_flag);
-		upcast(MilitarySite, ms, attackerflag->get_building());
-		std::vector<Soldier *> const present = ms->present_soldiers();
-		uint32_t const nr_staying = ms->min_soldier_capacity();
-		uint32_t const nr_present = present.size();
+	// Count (and if necessary collect) available soldiers.
+	for (const BaseImmovable* base_immovable : flags) {
+		const Flag* attackerflag = static_cast<const Flag*>(base_immovable);
+		const MilitarySite* ms = static_cast<MilitarySite*>(attackerflag->get_building());
+		std::vector<Soldier*> present = ms->present_soldiers();
+		const uint32_t nr_staying = ms->min_soldier_capacity();
+		const uint32_t nr_present = present.size();
 		if (nr_staying < nr_present) {
-			uint32_t const nr_taken =
-				std::min(nr_wanted, nr_present - nr_staying);
-			if (soldiers)
-				soldiers->insert
-					(soldiers->end(),
-					 present.begin(), present.begin() + nr_taken);
-			count     += nr_taken;
-			nr_wanted -= nr_taken;
-			if (!nr_wanted)
-				break;
+			const uint32_t nr_taken = nr_present - nr_staying;
+
+			if (soldiers) {
+				std::copy_n(present.begin(), nr_taken, std::back_inserter(attackers_all));
+			}
+
+			nr_available += nr_taken;
 		}
 	}
+	const uint32_t count = std::min(nr_available, nr_wanted);
+	if (soldiers) {
+		// Sort soldiers and remove surplus.
+		soldiers->reserve(count);
+		std::vector<Soldier*>::iterator pos = std::next(attackers_all.begin(), count);
+		// Even if weak soldiers are prefered, strong soldiers should attack
+		// otherwise, wounded soldiers would be send first
+		std::partial_sort(attackers_all.begin(),
+		                  pos,
+		                  attackers_all.end(),
+		                  Soldier::CompareSoldier(Soldier::SoldierPreference::kPrefersHeroes));
+		std::copy(attackers_all.begin(), pos, std::back_inserter(*soldiers));
+	}
 
 	return count;
 }
 
-
 // TODO(unknown): Clean this mess up. The only action we really have right now is
 // to attack, so pretending we have more types is pointless.
 void Player::enemyflagaction
 
=== modified file 'src/map_io/map_buildingdata_packet.cc'
--- src/map_io/map_buildingdata_packet.cc	2016-01-18 19:35:25 +0000
+++ src/map_io/map_buildingdata_packet.cc	2016-01-24 08:32:15 +0000
@@ -563,7 +563,7 @@
 			uint16_t reqmin = fr.unsigned_16();
 			uint16_t reqmax = fr.unsigned_16();
 			militarysite.m_soldier_upgrade_requirements = RequireAttribute(atrTotal, reqmin, reqmax);
-			militarysite.m_soldier_preference = static_cast<MilitarySite::SoldierPreference>(fr.unsigned_8());
+			militarysite.m_soldier_preference = static_cast<Soldier::SoldierPreference>(fr.unsigned_8());
 			militarysite.m_next_swap_soldiers_time = fr.signed_32();
 			militarysite.m_soldier_upgrade_try = 0 != fr.unsigned_8() ? true : false;
 			militarysite.m_doing_upgrade_request = 0 != fr.unsigned_8() ? true : false;
 
=== modified file 'src/wui/soldierlist.cc'
--- src/wui/soldierlist.cc	2016-01-17 08:29:59 +0000
+++ src/wui/soldierlist.cc	2016-01-24 08:32:15 +0000
@@ -427,12 +427,12 @@
 		}
 
 		m_soldier_preference.set_state(0);
-		if (ms->get_soldier_preference() == Widelands::MilitarySite::kPrefersHeroes) {
+		if (ms->get_soldier_preference() == Widelands::Soldier::kPrefersHeroes) {
 			m_soldier_preference.set_state(1);
 		}
 		if (can_act) {
-			m_soldier_preference.changedto.connect
-				(boost::bind(&SoldierList::set_soldier_preference, this, _1));
+			m_soldier_preference.changedto.connect(
+			   boost::bind(&SoldierList::set_soldier_preference, this, _1));
 		} else {
 			m_soldier_preference.set_enabled(false);
 		}
@@ -458,13 +458,13 @@
 	}
 	if (upcast(Widelands::MilitarySite, ms, &m_building)) {
 		switch (ms->get_soldier_preference()) {
-			case Widelands::MilitarySite::kPrefersRookies:
+			case Widelands::Soldier::kPrefersRookies:
 				m_soldier_preference.set_state(0);
 				break;
-			case Widelands::MilitarySite::kPrefersHeroes:
+			case Widelands::Soldier::kPrefersHeroes:
 				m_soldier_preference.set_state(1);
 				break;
-			case Widelands::MilitarySite::kNoPreference:
+			case Widelands::Soldier::kNoPreference:
 				m_soldier_preference.set_state(-1);
 				break;
 		}
@@ -506,8 +506,8 @@
 #endif
 	m_igb.game().send_player_militarysite_set_soldier_preference
 		(m_building, changed_to == 0 ?
-			Widelands::MilitarySite::kPrefersRookies:
-			Widelands::MilitarySite::kPrefersHeroes);
+			Widelands::Soldier::kPrefersRookies:
+			Widelands::Soldier::kPrefersHeroes);
 }
 
 UI::Panel * create_soldier_list