Announcement

Collapse
No announcement yet.

Group walk

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

    Group walk

    I am developing a RTS game. One of the features of RTS game is the group walk - when you select many characters and tell them to go somewhere and instead of walking alone separately, they group together and walk to their destination together and they can avoid obstacles

    I am trying to think about this group walk algorithm and I can not think of a proper one.
    First I thought that I should bring the characters together and tell them to walk to their new destination (I find each one of the new positions at the destination) but when I have tried that each one of the characters walks in small difference speed and it is can be noticed for a far distance.
    Also this algorithm does not work well when there are obstacles blocking the way because of the turns that the character have to do.

    Click image for larger version

Name:	fxRkvN5.png
Views:	1
Size:	4.5 KB
ID:	1160425

    The right algorithm need to make each character know about each other so they will keep the right distance all the time and know what to do on turns, what each character do to turn and keep the order of the group.
    Is there any UE4 function that I can use which can help me?
    How can I accomplish this properly?
    Last edited by Darkstorm1997; 08-30-2015, 12:35 PM.

    #2
    interesting problem. have you tried using destination offsets?

    at group start, you get the point in the middle of the group. then you calculate each actor's offset to that point.

    when you set a target point, this is the new point in the middle of the group when it arrives. so each actor gets a new destination: target point + individual offset.

    stage 2 of the algorithm would be to choose a leader actor. the offsets move with the leader actor. if one of the followers has to move around a rock or anything, they speed up to reach their old position next to the leader.

    edit: "stage 2" should work for turns.
    Unreal Meetup Franken - Unreal Engine 4 Meetup
    Hands for VR - Space HDRI [Marketplace]

    Comment


      #3
      I can only relate to this tutorial:

      Open for contracted work | C++/BP (incl. Multiplayer) | Tutoring | VR

      My UE4 Blog/Page with Tutorials and more: Hit me for ALL the things!
      (Including 100+ Pages Multiplayer Network Compendium to get you started.)

      Comment


        #4
        hi,
        some years ago I posted a relatively simple and short C++ sample at Esenthel engine forum in "code snippets" section, using navmesh similarly to UE4, so it could help if you find it.
        basically, its operation was:
        - assign a leader, and set row and column offset for the others,
        - set group direction to leader's actual angle,
        - all the follower units should do very short pathfinding in every frame to their desired positions (can be spread over more frames for better performance), calculated easily according to leader position, their r/c offset, and group direction,
        - when the group receives a new target, the pathfinding is done by the leader,
        - when leader starts to move, followers follow him within a frame,
        - by checking the leader's path step positions when path is got, it is easy to define group direction for each step, and store it in an array,
        - when leader is going towards a new path step, group direction is updated, so the group moves nicely,
        - additionally I stored arrival direction too, which was possible to set by holding down right mouse button instead of clicking, and the difference vector of press and release positions gave the desired direction,
        as I remember it was not more than 200 lines, probably easy to port even to Blueprints.

        but in my personal opinion navmesh is not really fine for RTS, especially when you have many troops, and you want to see nicely collision avoiding units, with correct collision resolution if it finally happens. for example the above mentioned sample project handled crossing groups and collisions very badly (I used PhysX characters), and I also found the built in UE4 crowd AI behaving very badly in this situation (maybe it is possible to use effectively, and only I did something wrong, don't know...). so finally I made my own hierarchical tile+area pathfinder, currently porting to UE4 C++.

        p.s.
        if followers would also get path to next step of boss with r/c offset (instead of the frame by frame very short path updates), because of the non-consistent distribution of the navmesh it would break the formation, units would move according to navmesh edges following each other on a few tracks. it is avoided in case of a tile map, where the grid is consistent (and in general everything can be estimated easier).
        Last edited by eXi; 08-31-2015, 06:11 AM. Reason: Doublepost
        Edge of Chaos RTS
        "Age of Total Heroes" - RTS Pathfinding and Movement System for UE4
        RTS Camera C++ Tutorial

        Comment


          #5
          Originally posted by sivan View Post
          hi,
          some years ago I posted a relatively simple and short C++ sample at Esenthel engine forum in "code snippets" section, using navmesh similarly to UE4, so it could help if you find it.
          basically, its operation was:
          - assign a leader, and set row and column offset for the others,
          - set group direction to leader's actual angle,
          - all the follower units should do very short pathfinding in every frame to their desired positions (can be spread over more frames for better performance), calculated easily according to leader position, their r/c offset, and group direction,
          - when the group receives a new target, the pathfinding is done by the leader,
          - when leader starts to move, followers follow him within a frame,
          - by checking the leader's path step positions when path is got, it is easy to define group direction for each step, and store it in an array,
          - when leader is going towards a new path step, group direction is updated, so the group moves nicely,
          - additionally I stored arrival direction too, which was possible to set by holding down right mouse button instead of clicking, and the difference vector of press and release positions gave the desired direction,
          as I remember it was not more than 200 lines, probably easy to port even to Blueprints.

          but in my personal opinion navmesh is not really fine for RTS, especially when you have many troops, and you want to see nicely collision avoiding units, with correct collision resolution if it finally happens. for example the above mentioned sample project handled crossing groups and collisions very badly (I used PhysX characters), and I also found the built in UE4 crowd AI behaving very badly in this situation (maybe it is possible to use effectively, and only I did something wrong, don't know...). so finally I made my own hierarchical tile+area pathfinder, currently porting to UE4 C++.

          p.s.
          if followers would also get path to next step of boss with r/c offset (instead of the frame by frame very short path updates), because of the non-consistent distribution of the navmesh it would break the formation, units would move according to navmesh edges following each other on a few tracks. it is avoided in case of a tile map, where the grid is consistent (and in general everything can be estimated easier).
          Hey, telling the charachers each frame to go to new destination is not very effective. Is'nt there a way to do it without it? maybe relate to all character as one object and move it?

          Comment


            #6
            yes, it is not optimal at all.

            There could be a solution by using an invisible group leader actor (should be pawn or character without collision), that does the pathfinding and movement along the long path to be followed by units.
            Group member units should update their target within a couple of frames to decrease performance cost, and to improve obstacle avoidance, while keeping more or less the formation shape (formation facing direction also can be updated by setting similar to the invisible actor's direction, to calculate the offsets of unit target positions).
            If units lag behind a lot because of e.g. collisions with another group, the invisible actor should slow down or stop until units get closer.
            Moreover, groups could avoid each other if the invisible leaders could manage it e.g. by setting their size as large as group width (they could collide with each other), and some movement prediction could also help.
            I think it would not be very complicated to implement, and must work much better than my example described above
            Last edited by sivan; 09-01-2015, 07:00 AM.
            Edge of Chaos RTS
            "Age of Total Heroes" - RTS Pathfinding and Movement System for UE4
            RTS Camera C++ Tutorial

            Comment


              #7
              Originally posted by sivan View Post
              yes, it is not optimal at all.

              There could be a solution by using an invisible group leader actor (should be pawn or character without collision), that does the pathfinding and movement along the long path to be followed by units.
              Group member units should update their target within a couple of frames to decrease performance cost, and to improve obstacle avoidance, while keeping more or less the formation shape (formation facing direction also can be updated by setting similar to the invisible actor's direction, to calculate the offsets of unit target positions).
              If units lag behind a lot because of e.g. collisions with another group, the invisible actor should slow down or stop until units get closer.
              Moreover, groups could avoid each other if the invisible leaders could manage it e.g. by setting their size as large as group width (they could collide with each other), and some movement prediction could also help.
              I think it would not be very complicated to implement, and must work much better than my example described above
              Thank you I did not think about invisible actor!

              Comment


                #8
                I use this trick in my custom pathfinder too. Maybe once I will get in a mood to make it with navmesh... Earlier I made some tests, if the units have a target approx 5m far (probably can be increased), and the navmesh is dense enough, they keep the formation fine.


                moreover, the problems you can face when using navmesh for RTS:

                - handling different unit sizes: in theory it requires separate navmeshes to avoid large units getting stuck or colliding too much
                + a workaround: due to my tests, in Age of Empires 3 all the units had a similar infantry sized collision, but tried to keep distance afterwards

                - handling different capabilities: if different types of units can pass different areas (e.g. a tank can break through small walls or vegetation), in theory it would also require separate navmeshes with different settings
                + a workaround: Rama made navmesh movement filtering blueprints (you can find it in the forum), it requires to place invisible navmesh modifier blocks (probably it can be attached to actors as component/volume)

                - ship movement: I don't know how to set up navmesh for them
                + you are lucky if don't use ships
                Edge of Chaos RTS
                "Age of Total Heroes" - RTS Pathfinding and Movement System for UE4
                RTS Camera C++ Tutorial

                Comment


                  #9
                  Hey Sivan, do you have any examples you could share of custom pathfinding in UE4? I've been studying how to do movement in an RTS game for a few weeks now and I am finding the navmesh a bit hard to work with.

                  I did some searching and I did find your post. I haven't read it yet but figured I'd share.

                  http://www.esenthel.com/forum/showthread.php?tid=5233
                  Last edited by Heoki; 10-29-2015, 09:36 PM.

                  Comment


                    #10
                    My custom pathfinder is nearly similar to the system of Company of Heroes 1, what you can see here (requires a free registration): http://aigamedev.com/premium/present...h-destruction/ Of course a bit different, because based on mixing other references, but similarly features tiles, clusters, clearance maps for different capabilities, static terrain and stationary/dynamic data updating caused by destruction, unit group and formation system etc. It is not fully ported to UE4, currently only the static map decomposition is ready (the whole system works fine in 3DGamestudio, where I can add and test new features faster).

                    That code snippet made with Esenthel engine is a very simple example using navmesh, without unit-unit avoidance and collision resolution. Group leaders do the pathfinding, while others are following him, aligning to the desired position in each tick, based on their formation place according to leader position and group direction, which is based on the actual and next path step positions. So not a game ready stuff at all.

                    By the way RTS games can differ a lot, and can require very different systems. If you want to use a few tens or 1-2 hundreds of units you may use navmesh and UE4 characters, but if want more, a complex and highly optimized system is necessary... I know because I have spent and will spend a lot of time with it
                    Edge of Chaos RTS
                    "Age of Total Heroes" - RTS Pathfinding and Movement System for UE4
                    RTS Camera C++ Tutorial

                    Comment

                    Working...
                    X