How movement / pathfinding of stacked up units could be improved

[tomreyn]

When I played 3.5.2 today i had an idea about how to tackle one of the major issues the game has when you have many units:
When you have many units, you often position them in a group, so that they fill adjacent fields, forming a rectangle. Then you select this group and order them to walk / attack somewhere at the same time. This means all these stacked up units try to walk to the same destination at the same time, and every single of them tries to find a good path by itself.

This is tough on the pathfinder, and while units which are in the row close to the destination will easily find a route there, the rows in the back actually have to calculate complex paths, and usually turn to the opposite direction at first. This makes surprise / hit and run attacks more difficult, since your units will take a while until they arrive, since they keep blocking each other at the beginning.

Thre's two ways to solve this I can think of:

1. Walk in formation
2. Walk 'row by row'

Ad 1:
One way to solve this would be moving in formation. This would mean that either the most central or only the outermost units should do pathfinding. Obviously this only works when all units have the same movement speed and do not run into obstacles along the way. So while this would be nice on the first thought, on second thought it may have a lot of problematic side effects.

Ad 2:
The second option is to make those units which are not as close as others to the destination wait one frame before they start to search for a path and before they start to walk.
I.e. the 'front row' starts path finding and walking first, then the second row, then the third etc. 'Rows' would be calculated as follows:
(a) Determine the unit (or any one of the units, if multiple) which has the shortest path to the destination. This unit is in row zero.
(b) For every other unit, calculate the distance between this unit and the unit determined in (a). The result is their row number.
Now when this group is moved to a given destination, each row starts path finding and walking with a delay which equals its row number. I.e. row zero starts immediately, row 1 starts one frame later, row two starts another frame later etc.

I think this would give us much more smooth movements, and put less load on the path finder

Softcoder already said on IRC that the problem and solution are far more complex than this. So I hope my and Coldfusionstorm's suggestions will lead to a fruitful discussion.

[Coldfusionstorm]

I agree with tomreyn's suggestions, however i have a couple of addtions the way i see it the pathfinder is very strict as it is now, my suggestions is to let unit's be able to "nugded" a _LITTLE_ so that the pathfinder have a easier time finding a path, this _TOGETHER_, with a pathfinder that work in smaller groups, would properly ease the pathfinder up ALOT, and hopefully lead to better performance in larger games.

Another idea in hang with the "grouped pathfinder idea"

Pathfinder idea 2.
When a order is issued for a large group the pathfinder should _first_ find space for all the units. if it does not find space for the units it only moves a part of the group, this selection should then be of the closest units to the destination.

[will]

Q: should units of differing speeds move at the speed of the slowest?

[Coldfusionstorm]

A: no, this is a micro "issue". the player should control all of his units, and take care that slow seige units are in back, and fast hit'n'run units should be managed too as such.

[softcoder]

I am working on a mult-part solution for this. I will 'group' units which issue commans together as a first step, then give 'grouped' command units priority FIRST for pathfinding. Each group will then have the closest unit to the target calc the path first, and so on. In addition to this I will look into allowing units to wait a few frames when blocked by a moving unit in the same team.

*UPDATE: Try svn rev 2438, it tries to have 'groups' of units pathfind together when they are given the same command at the same time (for starters), both human and AI are supported in this code, feedback is appreciated from people who test on svn.

[Coldfusionstorm]

i have tried this, and it seemed to work very well, i played agasinst a ultra (1) CPU. a 1v1 map, with narrow cannouns, me and the CPU had one large battle with around, 30 units, all moving at the same time.

[ultifd]

Sounds cool, I'll have to try this out! Secret new feature!

[tomreyn]

Nice, it looks like group movements are better now, though I was hoping this would make even more of a difference... Anyway, it's a nice improvement.

[Ishmaru]

Does movement like this makes units move smoother when in groups instead of scatter randomly? And does it make render speed faster?

[tomreyn]

Does movement like this makes units move smoother when in groups instead of scatter randomly?

Yes, that's the idea, and the change softcoder made improved on this.

And does it make render speed faster?

I assume it does, properly testing this is not easy, though.

[Coldfusionstorm]

the _POINT_ of the change was to improve FPS when large groups of units were onscreen and moving, because of the exstreme calculations made on the CPU the FPS would die on older CPU's.

[will]

super article on speeding up grid path finding: http://harablog.wordpress.com/2011/08/26/fast-pathfinding-via-symmetry-breaking/