Announcement

Collapse
No announcement yet.

Turn based strategy system

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

    Turn based strategy system

    Edit: I've made lots of improvements since this first post. See the last page of the thread or the video below for the latest version.

    I'm finally getting around to making use of my blueprint A* pathfinding algorithm. My long term goal is to make a turn based, tile based, procedurally generated dungeon crawler, but that dream is still far into the future. For the moment I am laying the basis, and that is creating an efficient, flexible turn based strategy system in blueprint. At the moment the system can generate paths for labyrynthine grids of more than 5000 tiles, and move an animated character through them. I have also implemented Dijkstra's algorithm in blueprint for calculating and showing what tiles a character can move to, dependent on the characters "speed" attribute. The functionality is very simple so far, but I'm hoping I'll make rapid progress.



    My next planned step is adding more characters and the ability to attack. I'll keep this thread updated as I make improvements.

    Edit: Added video showcasing the latest features

    Last edited by Monokkel; 12-30-2014, 11:33 AM.
    The Advanced Turn Based Tile Toolkit (Marketplace page - Feedback thread)

    #2
    Awesome work man! Definitely is in need this blueprint
    Thank you for showing us, keep us up to date

    Comment


      #3
      Interesting, are you planning to release this system?
      [MARKETPLACE] The forest like gameplay system | building/crafting game
      Dark Souls 2 fighting system style
      Drivable Space Ship
      Run Knight Run | 48h game made
      Unreal Travel | 48h game made

      Comment


        #4
        Originally posted by QBert View Post
        Awesome work man! Definitely is in need this blueprint
        Thank you for showing us, keep us up to date
        Thank you, I will

        Originally posted by Nesjett View Post
        Interesting, are you planning to release this system?
        My A*-pathfinding system is already freely availible, and at the moment I don't mind sharing my files with anyone who might be interested. However, the bluprints are probably very difficult to understand for anyone but myself at the moment. If there is enough interest I might take the time to clean up everything, make it more intuitive, and maybe release it on the marketplace.
        The Advanced Turn Based Tile Toolkit (Marketplace page - Feedback thread)

        Comment


          #5
          Looking forward to seeing what you accomplish!
          Map Generator 1.0
          Map Generator 2.0
          Map Generator 3.0

          Comment


            #6
            Originally posted by Zeustiak View Post
            Looking forward to seeing what you accomplish!
            Thanks, Zeus! If I can maintain a fraction of your workload, this should og smoothly. This sort of system should be perfect for Civ-style games as well.
            The Advanced Turn Based Tile Toolkit (Marketplace page - Feedback thread)

            Comment


              #7
              Originally posted by Monokkel View Post
              Thanks, Zeus! If I can maintain a fraction of your workload, this should og smoothly. This sort of system should be perfect for Civ-style games as well.
              Maintaining the workload can definitely be tough, so good luck keeping that energy level up!

              Pathfinding might be the next thing I work on when my generator is at a good stopping point. Like the map, it is one of those things that the entire game will rest upon so I want to start it off with a good foundation. I see it not only as a way for units to move around, but also as a way to intelligently look out onto the map and pull specific information that can then be used in all kinds of systems. Especially the AI.
              Map Generator 1.0
              Map Generator 2.0
              Map Generator 3.0

              Comment


                #8
                Originally posted by Zeustiak View Post
                Maintaining the workload can definitely be tough, so good luck keeping that energy level up!

                Pathfinding might be the next thing I work on when my generator is at a good stopping point. Like the map, it is one of those things that the entire game will rest upon so I want to start it off with a good foundation. I see it not only as a way for units to move around, but also as a way to intelligently look out onto the map and pull specific information that can then be used in all kinds of systems. Especially the AI.
                Pathfinding can certainly be used for multiple purposes. When the basics of player control is done I will start working on AI, where pathfinding will play an integral part. I'm planning to make special AI pathfinding that takes many considerations when choosing a path, including protecting their own, preferring to target weaker enemies etc.

                I have now made my system work for multiple characters. I haven't done a true stress test yet, but I seem to be able to cram way more characters onto the map than what I really need without causing any slowdown (far, far more than in the image below), so that is promising. I've also started implementing the ability to attack in melee.

                Click image for larger version

Name:	multiple.png
Views:	1
Size:	708.6 KB
ID:	1060914
                The Advanced Turn Based Tile Toolkit (Marketplace page - Feedback thread)

                Comment


                  #9
                  A* is one of the high grossing products on Unity asset store. Remember that, and maybe give us something similar on UE4 marketplace? :>

                  Comment


                    #10
                    Originally posted by oasf View Post
                    A* is one of the high grossing products on Unity asset store. Remember that, and maybe give us something similar on UE4 marketplace? :>
                    After looking at the Unity asset store I might actually consider releasing it on the UE4 marketplace when it's cleaned up and feature complete. Some of the sold assets seem to handle a lot smaller grids than what my system is able to do, which I find surprising given that they're made in C#. I'm becoming more and more impressed by the power and versatility of blueprints.
                    The Advanced Turn Based Tile Toolkit (Marketplace page - Feedback thread)

                    Comment


                      #11
                      I found a flaw in my A*-algorithm that caused it to produce subpar paths in a few rare cases. Fixing this took a lot of work, and added some more nodes to the path finding loop. I was worried that this could slow down the search algorithm more than what it was worth, so I decided to do a stress test. The path finding only had any perceivable slowdown on incredibly long paths, and all paths generated are now optimal. One small remaining annoyance is that in cases where diagonal and straight tile movement have the same cost, paths sometimes zigzag a bit. The paths are still equally efficient compared to straight paths, cost-wise, but do not always look as good. I might try to find a way of getting the algorithm to prefer straight movement if the paths are equally costly, but that's not my first priority. If I choose to use hexagonal grids or different costs for diagonal movement this problem will disappear anyway.

                      While conducting my path finding stress test I decided to check how many pawns I could have in play before I got any significant slowdown. To my surprise fps didn't dip below 60 until I had more than 270 animated pawns visible at once in a 40*40 grid, and everything still worked flawlessly. Granted, my rig is quite decent, but it's no supercomputer. I'm incredibly impressed by UE4's performance, and it's good to know that my bare bones system works way better than what I need before I start adding more features.

                      Attached Files
                      The Advanced Turn Based Tile Toolkit (Marketplace page - Feedback thread)

                      Comment


                        #12
                        Very nice.

                        I think I read something in one of Amit's pathfinding articles that very slightly skewing G or H is a good way to get rid of ties like that. Been awhile though so I might be mis-remembering things.

                        If you fill that space with random obstacles how does it affect the FPS?
                        Map Generator 1.0
                        Map Generator 2.0
                        Map Generator 3.0

                        Comment


                          #13
                          Yeah, I've also read the same thing from Amit, and I've experimented with skewing the numbers slightly. I got some weird results, though, so it needs some more mork.

                          Obstacles actually improve the pathfinding significantly. The more obstacles, the less tiles are added to the open list. Through a narrow Maze, the pathfinding can go on for huge distances before hitting the loop limit. If the obstacles are instanced static meshes they shouldn't have that high of an impact on fps, depending on vertex count and variability of obstacles, but you have much more experience than me with that sort of thing.
                          The Advanced Turn Based Tile Toolkit (Marketplace page - Feedback thread)

                          Comment


                            #14
                            Yeah that makes sense.

                            I don't start having problems until the number of instanced meshes reaches some tens of thousands of meshes.

                            Have you played with variable tile movement costs yet? My system might have to check against several arrays per tile, with array sizes that reach the tens of thousands. I wonder how the increased number of arrays and array size would affect your generations.
                            Map Generator 1.0
                            Map Generator 2.0
                            Map Generator 3.0

                            Comment


                              #15
                              Good to hear instanced meshes work that well. And that is when all meshes are visible in the viewport at once, right?

                              I have not done variable movement costs for different tiles yet, but it's pretty high on my list, and I imagine it will be really easy to do. I'll just have to store the movement costs of tiles in an array, and check it before I add the tile's movement cost for the tile. I might make a separate array, or simply change my bool array for walls into an int array, and make the walls have ridiculously high movement costs. I'm unsure of what method will be more efficient.

                              At the moment I check 5 arrays per tile, like so: wall array -> closed list array -> pawn array -> open list (if yes -> compare to old cost of tile in open list). The number of checks will vary for each tile. If the tile is "true" on the wall array, it won't bother checking to see if it's on the closed list. I might reduce the number of arrays by merging some of them. For instance, I could change the wall bool array to an enum array that includes walls, pawns and movement cost. I'm unsure how much faster bool arrays are compared to enum or int arrays, so I'll find out what is more efficient through trial and error. I suspect merging arrays is the better method, and I'll report the results when I've tried it out.

                              As for having large arrays, I actually don't think that will be a problem in most cases. In my blueprint, I never search through an entire tile array to find a tile. In almost all cases, I ask for the value at a specific index in the array, and I imagine this will be just as fast for bigger and smaller arrays. The only place where I do not use an index is when I search through the open list for the tile with the lowest predicted cost. Even here I do not use a simple find-node, but am using a binary heap to greatly reduce the number of comparisons. I also don't look through the entire tile array, but only the ones that have been added to the open list. The way I see it, the problem isn't the size of the tile array, but the length of the path. If you try to find the route to an endpoint that is impossible to reach (if it is blocked off by walls, for instance), the algorithm will keep searching though your entire tile array, which hits the loop limit at around 6000 tiles in my current blueprint. However, this is easily avoided by creating an upper limit to the amount of tiles that can be searched. This limit is high enough in my blueprint, that for anything but impossible paths the loop limit should never be reached, even for arrays of your size.
                              The Advanced Turn Based Tile Toolkit (Marketplace page - Feedback thread)

                              Comment

                              Working...
                              X