Announcement

Collapse
No announcement yet.

Pathfinding for large crowds

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

  • [PLUGIN] Pathfinding for large crowds

    I am currently working on a code plugin that enables pathfinding for a large number of units (even on large maps with dynamically changing environment).
    I basically implemented the "Flow Field" approach from Supreme Commander 2 (plus some custom enhancements and modifications).

    The plugin is not yet complete, but would anyone be interested in test-driving it?
    If you are interested you can also tell me which feature you want to see in the final plugin and I will see if it can be added

    Currently working:
    * initialize surface cost data from textures
    * tile-based merging A* search
    * flowfield generation
    * steering an actor based on the flowfield
    * dynamically moving target
    * adding and removing actors for pathfinding
    * visualize flowfield and generated paths
    * Optionally create smoother flow fields by computing a sector ahead for each field

    Still to do:
    * Support multiple targets per agent (e.g. for zombies chasing more than one hero)
    * Add multithreading support, so flow fields can be generated in a separate thread
    * [Optional] Automatically generate surface data from navmeshes
    * [Optional] Automatically generate surface data from geometry

    Source:
    Last edited by Cultrarius; 01-09-2018, 04:43 PM.
    Particle Editor Extension: Marketplace Page | Documentation
    Code plugin which extends your particle effect toolbox with new possibilities.


    SVG Importer Plugin: Marketplace Page | Gumroad Page
    Import SVG (scalable vector graphics) files as rasterized rendering or as multi-channel signed distance field.

  • #2
    sounds interesting. Im making a TPS zombie game, so I will probably pick this up.

    Comment


    • #3
      Originally posted by Vathusmoure View Post
      sounds interesting. Im making a TPS zombie game, so I will probably pick this up.
      Nice
      If you want to beta-test the plugin just send me a PM.


      I also have some WIP screenshots:
      Particle Editor Extension: Marketplace Page | Documentation
      Code plugin which extends your particle effect toolbox with new possibilities.


      SVG Importer Plugin: Marketplace Page | Gumroad Page
      Import SVG (scalable vector graphics) files as rasterized rendering or as multi-channel signed distance field.

      Comment


      • #4
        To answer some questions I have been getting: you should be able to combine the plugin with any other UE4 technology like AI behavior, navmeshes, networking, physics, etc.

        The plugin itself is implemented in C++ and exposes a very simple interface for C++ and blueprints. If you want you can use the plugin for any pathfinding purpose, e.g. to move sprites on a 2D area; all you have to do is initialize it with the surface data and implement the interface for your moving parts. I implemented a custom actor component that can be attached to any pawn and uses the plugin's interface for the navigation.

        My pawn component just relays the pawn location and target to the plugin once per tick and retrieves a direction vector as result. This vector is then applied as input vector to the pawn (similar to keyboard or mouse input from a user) and does not directly move the pawn. The pawn is still deciding if and how it wants to move in the given direction, do collision checks, network replication, etc.
        Particle Editor Extension: Marketplace Page | Documentation
        Code plugin which extends your particle effect toolbox with new possibilities.


        SVG Importer Plugin: Marketplace Page | Gumroad Page
        Import SVG (scalable vector graphics) files as rasterized rendering or as multi-channel signed distance field.

        Comment


        • #5
          Let me know when this plugin goes live

          Comment


          • #6
            Is the vector/flow field generated on top of the navmesh or all geometry?

            Comment


            • #7
              Originally posted by HeadClot View Post
              Let me know when this plugin goes live
              Gladly
              Originally posted by jonimake View Post
              Is the vector/flow field generated on top of the navmesh or all geometry?
              Currently, you have to supply a 2D surface cost array for the calculation. Each individual cell can have a traversal cost between 1 and 254 or be blocked completely.
              This data is not generated automatically from the navmeshes or geometry, but it is not very hard to do that yourself. Maybe I will add the automatic generation from navmesh at a later point.
              I already added the option to initialize the surface data from a texture, so if you have a top-down view of your map you can use it to paint the walls or hard to traverse areas to the texture.
              In the original paper they said that they used a blur filter on the textures to reduce hard edges and create a "buffer zone" around blocking tiles.

              ---

              I also added an option to improve the quality of the generated flowfields by including data from the next few tiles. The drawback is that the calculation takes longer and a tile update could now invalidate the flowmaps of adjacent tiles.
              Here is a video demonstrating the effect:

              Particle Editor Extension: Marketplace Page | Documentation
              Code plugin which extends your particle effect toolbox with new possibilities.


              SVG Importer Plugin: Marketplace Page | Gumroad Page
              Import SVG (scalable vector graphics) files as rasterized rendering or as multi-channel signed distance field.

              Comment


              • #8
                Are there plans to add this to non 2d surfaces? as like with Supreme commander I would find this ideal if it worked on a sphere, or is it possible to have a non Z up version where 6 planes could be made into a cube?
                Last edited by Smartay; 01-12-2018, 06:56 AM.

                Comment


                • #9
                  if you later want to move groups (and the essence of this system is to apply the same flow map for moving multiple units for saving performance), imo the "better flow map" will be worse, because the units will move to a similar path instead of spreading across the whole area.
                  "Age of Total Heroes" - RTS Pathfinding and Movement System for UE4
                  RTS Camera C++ Tutorial

                  Comment


                  • #10
                    Originally posted by Smartay View Post
                    Are there plans to add this to non 2d surfaces? as like with Supreme commander I would find this ideal if it worked on a sphere, or is it possible to have a non Z up version where 6 planes could be made into a cube?
                    No, I will not add a third dimension to it, but if I am not entirely mistaken you can still use it on a sphere if you "skin" the sphere correctly. You can of course also have multiple instances of the flow path plugin running in parallel, each with a different "view" of the level (be it different planes or for different types of units).
                    Originally posted by sivan View Post
                    if you later want to move groups (and the essence of this system is to apply the same flow map for moving multiple units for saving performance), imo the "better flow map" will be worse, because the units will move to a similar path instead of spreading across the whole area.
                    Maybe, that remains to be seen (but it is one reason I added an option to disable it). I plan to add a grid-based collision detection for the crowd movement, so units don't block each other when moving but spread around instead.
                    I also plan to add a few group controls to it, so you can have something like group cohesion where units in front of a group slow down and units at the back speed up (when too far away). In my opinion, these flocking-like behaviors are always fun to play with, because they look somewhat natural. Another thing I want to explore are formations, but I am still thinking on how best to implement them.

                    By the way, I had a look at your RTS plugin - really nice work!
                    Particle Editor Extension: Marketplace Page | Documentation
                    Code plugin which extends your particle effect toolbox with new possibilities.


                    SVG Importer Plugin: Marketplace Page | Gumroad Page
                    Import SVG (scalable vector graphics) files as rasterized rendering or as multi-channel signed distance field.

                    Comment


                    • #11
                      thanks, it is a really long work indeed
                      to be honest, movement and especially group movement are the hardest things not pathfinding... collision detection and resolving also a performance sensitive thing, so an avoidance by flocking rules could be nice, but it is not as easy to integrate into a tile pathfinder...
                      "Age of Total Heroes" - RTS Pathfinding and Movement System for UE4
                      RTS Camera C++ Tutorial

                      Comment

                      Working...
                      X