Dynamic group reordering

[dicsoupcan]

i cannot wait for this, it will make army management easier

[Ben]

Oh my gosh! When I saw the video, I couldn't help but smile and get a "warm-fuzzy feeling" I love it so much! It reminds me of changing formations of soldiers in games like Total War or other more modern games. Very good work. Another great addition to the Remake.

Additionally, I'd like to add that I like these "upgrades" that are being included in the Remake. More of these upgrades and less "additions" such as new units and such are what I, personally, like to see.

[FeyBart]

See, this is why I really love the Remake so much. The great eye for detail. It seems like a little thing, but all those things stacked, make a fucking awesome game. I'm sorry for swearing, but I can't help it. Enthusiasm takes over again.

[Ben]

He swore!

Although I completely understand his enthusiasm!

[Lewin]

Okay, we have a bit of a problem: Dynamic group reordering uses the Hungarian Algorithm, which is O(n^3). What this basically means is it becomes very slow with large group sizes, because it grows according to N^3 (where N is the number of group members): So if it takes 1ms to compute with 10 group members, then with 20 group members it will take 8ms, with 30 it will take 27ms, with 50 it will take 125ms, with 100 it will takes 1000ms and so on.

This means we are going to need to disable it for large group sizes, because at the moment if you have a group with 100+ units it can freeze the game for a few seconds when you move them because it is very slow to calculate their optimal positions. It looks like 30 is about the most we can allow, in my tests it takes 1-5ms to complete with 30 units on my fairly modern CPU (consider that on 3x speed we only have 33ms per tick, and with x10 speed only 10ms, and that must be shared with rendering/all other game logic).

So my question is: What's the maximum group size that you regularly use in KaM? Are groups of 30+ soldiers common for you?
Cheers,
Lewin.

[sado1]

So, you want to implement a dumber algorithm for >30 units groups? That might have a side effect of encouraging people to divide their armies - it's a good practice, maybe some of them will notice how easier and more effective it is to navigate with a smaller group. Anyway, to answer your question, groups larger than 30 units are quite common, but I think that I don't usually produce enough soldiers to use such groups on a regular basis.

[Ben]

Groups larger than 30 are very, very common. Even 50 units can be seen regularly in beginner/unskilled games.
This is a very sad conundrum. I think that the reordering either needs to be more efficient (don't ask me: I have no ideas) or just needs to be taken out completely imo, because I think that it would be very weird to have everything change just because you have one more unit in a group. I can already imagine myself stressing out about trying to take one or two units out of a group so I'm below the overload...

[dicsoupcan]

Well it all depends on what kind of base i make. If i make a rushbase i often have groups of 50+ when they come out of the barracks, that i later organize in groups of 20-30. If i go for a big base with massive weaponproduction i often start with groups of 15-20 that can end up in multiple groups of 40 or something.

[sado1]

Couldn't you somehow cheat and kind of divide the big groups for smaller ones to reorder using the new algorithm, then merge all the smaller groups using a less CPU-hungry algorithm?

[Lewin]

Thanks for the feedback.

Groups larger than 30 are very, very common. Even 50 units can be seen regularly in beginner/unskilled games.
This is a very sad conundrum. I think that the reordering either needs to be more efficient (don't ask me: I have no ideas) or just needs to be taken out completely imo, because I think that it would be very weird to have everything change just because you have one more unit in a group. I can already imagine myself stressing out about trying to take one or two units out of a group so I'm below the overload...

Don't worry. Today I designed and wrote an alternative algorithm which reorders the groups if there are more than 25 members. It's works almost as well as the other one, I doubt you will notice the difference between the way they reorder with 25 and 26 units, except if you are looking very closely. The Hungarian algorithm is guaranteed to give the perfect, most mathematically efficient way to assign the members to locations. The "Lewin Algorithm" gives a "near enough is good enough" assignment, often it gives the same or very similar result as the Hungarian solution anyway. It's certainly a million times better than it was before we did any group reordering

Couldn't you somehow cheat and kind of divide the big groups for smaller ones to reorder using the new algorithm, then merge all the smaller groups using a less CPU-hungry algorithm?

You could, but that would often give poor results. For example if you process the left and right sides of a group separately then merged them, if you tell your group to turn 180 degrees then the left and right sides would want to swap (even though each side would choose the most efficient ordering) Often the kind of reordering that is required is for every member to take 1 step in order to change the shape of the group, that's something which is hard to divide up into separate pieces.

[Galahad]

Im in love with this change!

Especially with the Lewin Algorithm ^^

From my very short testing it looks exactly 1 million times better then the old system. Will try and find problems with it as i go on.