Dynamic group reordering

[Lewin]

Krom and I talked about doing this a long time ago but never got around to it, until last night when I was looking for something to do and I thought "why not?". Basically the idea is that soldiers in a group should not have fixed positions that they will always stand in, they should swap positions if it involves less walking/messing up. This is especially noticable if you change the formation or rotate your group 180 degrees. Because each solider has a fixed position he that he MUST stand in they will end up pushing each other around for a few minutes before reaching their final positions. Under the new system each soldier will be assigned a new position in such a way that there is minimal walking/reordering required.

Thankfully there are mathematical solutions to solve this problem, the most notable of which is called The Hungarian Solution. It involves assigning a cost for each soldier to walk to each available position (the distance he has to walk), then trying to match the soldiers to the positions in such a way that the total cost is minimal.

I found a nice open source Hungarian algorithm written in C# and translated it to Pascal then made groups use it to reorder themselves before walking/rearranging. The results are quite impressive. It's hard to explain or show with images so I made a quick video:
http://www.youtube.com/watch?v=LqG5Tr2kz1c

What do you think?
Lewin.

[Jeronimo]

I will say that Harold Kuhn did a good work.
From all the variants you show in the video, the most shocking (in my opinion) is the comparison between 0:37 and 1:47.

Are you also working on the multi-ordering?
Pressing SHIFT you would queue movements from groups (this feature is seen in almost every modern RTS).

[ChrisEggII]

Hey, it's great. Looks a bit funny for me, but I think this is because I'm accustomed to old style. Will you do something with soldier with a flag, or will he work like in this video?
And one more question: What is it a message with feather?

[Nissarin]

Very nice, are there any side effects, like higher CPU usage, especially with huge number of troops on battlefield ?

BTW: regarding Shift key - using it to add units to group would also be nice, e.g. Shift-3 will merge currently selected banner with units from group 3 (oppan Starcraft style).

[Lewin]

Are you also working on the multi-ordering?
Pressing SHIFT you would queue movements from groups (this feature is seen in almost every modern RTS).

Not yet, but I think it's planned.

Hey, it's great. Looks a bit funny for me, but I think this is because I'm accustomed to old style. Will you do something with soldier with a flag, or will he work like in this video?

We don't plan on changing it. It would look really odd if the flag "jumped" from one soldier to another, so I think he has to always have the flag.

And one more question: What is it a message with feather?

A new notification system we're trialing to make it easier to manage message spam (house not occupied, troops hungry, etc.). We'll post more details about it later.

Very nice, are there any side effects, like higher CPU usage, especially with huge number of troops on battlefield ?

I don't think it will make any noticable difference on CPU usage, the algorithm is quite efficient. I did some performances tests on it and it's so far down the list that there are hundreds of other things that could be optimized before we'd worry about it. The only time it could become more noticeable is if you have a REALLY big group, since the complexity is O(n^3) or O(n^4) (I'm not exactly sure since I didn't design the algorithm myself). So if you had a group with 200 soldiers it could use more CPU, but it probably still wouldn't be noticeable. And with a group that size you'd already have a lot more CPU usage with all of the pathfinding and unit interaction so it shouldn't matter at all.
In fact, this change could reduce CPU usage because the units are interacting and walking less (less unit movement/interaction = less CPU usage)

BTW: regarding Shift key - using it to add units to group would also be nice, e.g. Shift-3 will merge currently selected banner with units from group 3 (oppan Starcraft style).

Good suggestion, I've added it to the todo list

[The Dark Lord]

Oh wow, that's so much better.

[Lewin]

Someone on Youtube pointed out that it will mess up your formation if you have e.g. 1 row of crossbowmen with 1 row of bowmen behind (and you want to keep the crossbowmen at the front). We probably need to make it so the order of unit types is not changed, only rearrange units within their own type. What do you think about this?

[pawel95]

I have read this comment on youtube,too

For me it is a good decision like you have said it Lewin. There are tousands of reasons why someone wants to have Milita before swordmen(Rushing / Towers) or xbow before bowmen( Xbow has more defense/lifepoints).

[Jeronimo]

Lewin, will you add the "Dismiss Citizen" feature for next test version?
So we can try this and see how affects the gameplay.

If I remember correctly, the citizen will walk towards School and dissapear.
It's simple and many will find it useful... even those who complain.

[T*AnTi-V!RuZz]

Lewin, will you add the "Dismiss Citizen" feature for next test version?
So we can try this and see how affects the gameplay.

If I remember correctly, the citizen will walk towards School and dissapear.

I can't recall this idea being approved..

[Menszu]

First of all, hello everybody, my first post

Improvement looks great, in a game of tactical maneuvering like KaM it's very important. And how for example behave units standing one over another, or passing through? Is there any impact on those matters with these changes?

And offtopic, about that 'Dismiss Citizen', let's hope it wouldn't be approved. I already see all those 10 fisherman's rushing to catch all the fishes and vannishing in the school right after it's done. Same with miners. Town building wouldn't be no longer that much about city planning, but about quickest overexploitation - without any food problem backslash later.

[Jeronimo]

First of all, hello everybody, my first post

Improvement looks great, in a game of tactical maneuvering like KaM it's very important. And how for example behave units standing one over another, or passing through? Is there any impact on those matters with these changes?

And offtopic, about that 'Dismiss Citizen', let's hope it wouldn't be approved. I already see all those 10 fisherman's rushing to catch all the fishes and vannishing in the school right after it's done. Same with miners. Town building wouldn't be no longer that much about city planning, but about quickest overexploitation - without any food problem backslash later.

There is another possibility... retraining a Citizen into an automatic Serf.
In this version, he will walk into a School and use 1 chest for re-educating the Worker into a humble Serf.

You have still a mouth to feed, and uses 1 chest for the process.
As aside effect, you cannot choose to exchange that worker for a recruit.

If a School has no chests when he enters, he goes out immediatly (as when was recently trained).
So player should destroy the building where he was, so he doesnt walk again towards there.

When using the Retrain function, be sure your nearest school has at least 2-3 chests.
Yes, let's add that behaviour... Citizen walks towards nearest OPEN school.
If you close a school, the citizen will ignore it and move towards next nearest school (in order to be retrained).

-----------------------
Anyway, is this idea still viable for developers?
Retraining feature sounds more realistic than Dismissing.

[Lewin]

First of all, hello everybody, my first post

Improvement looks great, in a game of tactical maneuvering like KaM it's very important. And how for example behave units standing one over another, or passing through? Is there any impact on those matters with these changes?

And offtopic, about that 'Dismiss Citizen', let's hope it wouldn't be approved. I already see all those 10 fisherman's rushing to catch all the fishes and vannishing in the school right after it's done. Same with miners. Town building wouldn't be no longer that much about city planning, but about quickest overexploitation - without any food problem backslash later.

Welcome to the forums

I'm not sure what you mean "And how for example behave units standing one over another, or passing through?". Can you explain it in more detail?

Dismissing citizens has not been accepted mainly because of the reasons you gave. Retraining instead of dismissing doesn't solve the problem. I don't think it's an important feature so we haven't put much thought into it. Feel free to start a new topic if you want to discuss it, but lets keep this one on topic please.

[Menszu]

I meant : is there any difference in units behavior when unit of 12 soldiers passes through the unit of another 12. Are they more efficient and do it quicker? Or the changes are noticeable only in movement within single unit?

[Krom]

No, other unit interactions are unchanged. Only group ordering change is optimized.