Formations with flow fields

Formations with flow fields

Discuss the source code and development of Spring Engine in general from a technical point of view. Patches go here too.

Moderator: Moderators

Post Reply
jdtec
Posts: 2
Joined: 18 Jul 2019, 10:14

Formations with flow fields

Post by jdtec » 18 Jul 2019, 10:20

Hi,

I hope this is an ok place to post this as it's more an educational question on my part for my own RTS engine rather than a suggestion about the Spring engine.

Do any of you know techniques for implementing unit formations with flow field pathfinding?

What I've managed so far is have the units move into formation at the final movement destination but I'm struggling with getting them to stay in formation when they manoeuvre around obstacles in the map.

If any of you have experience of this then any ideas or pointers would be very much appreciated!

Thanks
0 x

User avatar
PicassoCT
Journeywar Developer & Mapper
Posts: 10238
Joined: 24 Jan 2006, 21:12

Re: Formations with flow fields

Post by PicassoCT » 20 Jul 2019, 08:10

I think that kleat (kloot) is your men.

https://www.youtube.com/watch?v=6578hTKM1jE

The thing was lifely discussed and implemented back in the SupCom2 day

https://www.youtube.com/watch?v=bovlsENv1g4

Its optional, meaning its deactivated by default, but you can activate it in a spring games configuration.


[quote = VanSmoothenStein]IIRC kloot said in a recent thread the flow field stuff was too expensive.[/quote]

viewtopic.php?f=73&t=24723&p=461066&hil ... ot#p461066

Adding the variable

Code: Select all

flowMapping = true 
to a units movedef might be able to activate the behaviour.

Keep in mind, this was just a quick search- i may be wrong
1 x

User avatar
Forboding Angel
Evolution RTS Developer
Posts: 14601
Joined: 17 Nov 2005, 02:43

Re: Formations with flow fields

Post by Forboding Angel » 20 Jul 2019, 09:54

it's actually in the movedef classes where you would need to add it:

https://github.com/spring/spring/blob/b ... ler.h#L150

edit: I just verified that it does work and it IS awesome.

That said, 300 of my Zaal Swarmers brought me down to 23 fps. Interestingly enough, when I disabled flowmapping and tried the exact same test with the name numbers of units, because of collisions I was dropped to 15 fps.

It may be the case that flowmappings efficiency causes it's overhead to be offset by the amount of collisions it prevents. We would need kloot to weigh in for an authoritative answer.
0 x

User avatar
PicassoCT
Journeywar Developer & Mapper
Posts: 10238
Joined: 24 Jan 2006, 21:12

Re: Formations with flow fields

Post by PicassoCT » 20 Jul 2019, 10:35

Shalle we provoke him to react? Okay..


Somebody should add this flowfield tech to the engine. It should be easily doable, as the engine is currently refactored anyway. If the engine devs where not so lazy..

That should do it, im off to greener pastures.
1 x

User avatar
Forboding Angel
Evolution RTS Developer
Posts: 14601
Joined: 17 Nov 2005, 02:43

Re: Formations with flow fields

Post by Forboding Angel » 20 Jul 2019, 11:18

Well another possibility is that flowfield might have continual upkeep costs that regular doesn't have.

I didn't mess with flowmod. I assume it's some sort of tuning mechanism for how sweaty the avoidance is. I'm fairly certain that at large numbers of units it can drag performance down, but in my mind I'm thinking a normal evo game where we have supply limits that effectively control unit counts. It's still quite a few, but nowhere near a BA 4v4 dsd no nukes 10 minutes kek game.

I'll do some real world testing soon and see if I can come up with any sort of tangible data that is worthwhile.
0 x

jdtec
Posts: 2
Joined: 18 Jul 2019, 10:14

Re: Formations with flow fields

Post by jdtec » 26 Jul 2019, 22:57

Thanks for the information guys.

Those videos look like they're showing what may be continiuum crowds or an advanced flow field avoidance algorithm that looks at units position and direction? It looks to be an additional/separate feature to flow field / vector field path finding.

It makes me wonder if Spring uses flow field path finding at all by default or does it just use optimised versions of A* for each unit?
0 x

User avatar
zwzsg
Kernel Panic Co-Developer
Posts: 7017
Joined: 16 Nov 2004, 13:08

Re: Formations with flow fields

Post by zwzsg » 28 Jul 2019, 14:46

jdtec wrote:
26 Jul 2019, 22:57
It makes me wonder if Spring uses flow field path finding at all by default or does it just use optimised versions of A* for each unit?
PicassoCT wrote:
20 Jul 2019, 08:10
Its optional, meaning its deactivated by default, but you can activate it in a spring games configuration.
Technically, it's the opposite:

ModRules configuration, in its [MOVEMENT] section, has a tag:
useClassicGroundMoveType=0;// Use the old movement code: 0 for disabled.

By experience, I can tell you the tricky bit is finding the correct heat parameters for each MoveInfo class:
HeatMapping=1;
HeatProduced=10;
HeatMod=0.10;

I enabled this flowfield pathfinding for Kernel Panic.

Have you tried it? Would you like to contribute to better heat settings?

Image
Attachments
Kernel_Panic_has_flowfields.gif
(2.58 MiB) Not downloaded yet
0 x

User avatar
PicassoCT
Journeywar Developer & Mapper
Posts: 10238
Joined: 24 Jan 2006, 21:12

Re: Formations with flow fields

Post by PicassoCT » 11 Aug 2019, 09:31

Unrelated, but patching general.. Do we use this?

https://news.ycombinator.com/item?id=20663355
Contraction hierarchies[0] are a nice extension over which A* works even better and I believe these are used in osrm. I read a paper by Microsoft Research where they optimized the setting to enable shortest path routing in average of 5 memory reads, or something ridiculously unbelievable like that. [1]

0: https://en.wikipedia.org/wiki/Contraction_hierarchies

1: https://www.microsoft.com/en-us/
0 x

User avatar
Forboding Angel
Evolution RTS Developer
Posts: 14601
Joined: 17 Nov 2005, 02:43

Re: Formations with flow fields

Post by Forboding Angel » 11 Aug 2019, 11:43

I've been using it in evo for a while and seems a-ok there.
0 x

User avatar
Forboding Angel
Evolution RTS Developer
Posts: 14601
Joined: 17 Nov 2005, 02:43

Re: Formations with flow fields

Post by Forboding Angel » 12 Aug 2019, 10:38

Made a little video that demonstrates it nicely with 200 fast units

https://youtu.be/aF6KfJdlbrY
1 x

User avatar
FLOZi
MC: Legacy & Spring 1944 Developer
Posts: 6109
Joined: 29 Apr 2005, 01:14

Re: Formations with flow fields

Post by FLOZi » 29 Aug 2019, 12:07

flow tags were not put in changelog so I never docced on the wiki :(

Looks like https://springrts.com/wiki/Movedefs.lua needs some updating!

also, its enabled by default for a moveclass in 104.0:

https://github.com/spring/spring/blob/1 ... r.cpp#L252

So 'adding' the tag is meaningless unless you had

Code: Select all

flowMapping = false
previously, unless it changed in more recent builds.
0 x

User avatar
zwzsg
Kernel Panic Co-Developer
Posts: 7017
Joined: 16 Nov 2004, 13:08

Re: Formations with flow fields

Post by zwzsg » 29 Aug 2019, 23:53

Do you mean I confused heat map and flowfield?

Just how many kind of pathfindings are available in Spring?
0 x

User avatar
FLOZi
MC: Legacy & Spring 1944 Developer
Posts: 6109
Joined: 29 Apr 2005, 01:14

Re: Formations with flow fields

Post by FLOZi » 30 Aug 2019, 14:12

Heat mapping and flow field are different yes. But I think you can have both enabled simultaneously. jK said that if he recalls flowfield wasn't fully implemented / didn't do everything it was meant to, or such.
0 x

Post Reply

Return to “Engine”

cron