Turn based strategy system

Community Showcase Game Development
1

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

https://www…com/watch?v=dQnNc-Wclak

2

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

3

Interesting, are you planning to release this system?

4

[=QBert;175637]
Awesome work man! Definitely is in need this blueprint :slight_smile:
Thank you for showing us, keep us up to date :slight_smile:
[/]

Thank you, I will :slight_smile:

[=Nesjett;175637]
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.

5

Looking forward to seeing what you accomplish! :slight_smile:

6

[=;175816]
Looking forward to seeing what you accomplish! :slight_smile:
[/]

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.

7

[=;175835]
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! :slight_smile:

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.

8

[=;175869]
Maintaining the workload can definitely be tough, so good luck keeping that energy level up! :slight_smile:

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.

ba800a450318d6defdda57ba75cbdc0718ee438e.jpeg
ba800a450318d6defdda57ba75cbdc0718ee438e.jpeg1132×837 157 KB

9

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

10

[=oasf;177951]
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.

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.

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?

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.

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.

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.

16

[=;182265]
Good to hear instanced meshes work that well. And that is when all meshes are visible in the viewport at once, right?
[/]

Yeah zoomed all the way out it gets choppy, but zoomed in it is much better. But that is with tens of thousands of tree meshes that I am currently over producing(by say 37 times). I might have 100K meshes on a map with 20K instanced tiles.

[=;182265]
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.
[/]

I was talking with a friend of mine who recently took some kind of logic architecture class and he was telling me that when you search for an index in an array it starts at the beginning of the array looks at everything down the line until it finds the index you want. So in my case that could be tens of thousands of indexes in before it gets to the named index. He was basically saying that it would be better to do a few pieces of math rather than do a single array check which would have to spend time accessing memory.

I think you could test this by making a map with say 20K+ tiles(or at least that many indexes in the arrays), but then walling off a small section that would have all your actors. That way you could run the same test you have been doing but the only thing that would change would be the size of the arrays being checked.

[=;182265]
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.
[/]

This is the old default loop limit or the new one that you can set to 2 billion?

17

[=;182864]
Yeah zoomed all the way out it gets choppy, but zoomed in it is much better. But that is with tens of thousands of tree meshes that I am currently over producing(by say 37 times). I might have 100K meshes on a map with 20K instanced tiles.
[/]

Ok, good. Does it seem like the amount of tiles have almost no impact, as long as they are off screen, or is the effect just less pronounced? How is the framerate when zoomed all tne way out compared to having say 20*20 tiles in view?

I’m planning on making huge, procedural worlds, and these sorts of things will determine how I go about doing that. Worst case I have the world stored in arrays, and only spawn the tiles just before they enter view, deleting them as they leave. I can check this out myself, of course, but I suspect you have taken more time perfecting your tile spawning algorithm.

[=;182864]
I was talking with a friend of mine who recently took some kind of logic architecture class and he was telling me that when you search for an index in an array it starts at the beginning of the array looks at everything down the line until it finds the index you want. So in my case that could be tens of thousands of indexes in before it gets to the named index. He was basically saying that it would be better to do a few pieces of math rather than do a single array check which would have to spend time accessing memory.
I think you could test this by making a map with say 20K+ tiles(or at least that many indexes in the arrays), but then walling off a small section that would have all your actors. That way you could run the same test you have been doing but the only thing that would change would be the size of the arrays being checked.
[/]

What you are describing sounds like the difference between using the search function in an array as compared to the get function. Using search is comparable to opening every file in a file cabinet until you find the one you’re looking for, while using get is comparable to just checking a single, specific file at an index.

This is the reason why I use get functions almost exclusively, and I suspect this is the reason why my algorithm is reasonably efficient. Still, I will try to compare pathfinding on a small grid to pathfinding on a large grid in a sealed off area and report the results.

[=;182864]
This is the old default loop limit or the new one that you can set to 2 billion?
[/]

This is with the old loop limit. Increasing the loop limit is of course not that big of a problem. However, when getting close to hitting even the old loop limit, the game freezes noticeably for about a second. For generating a map at the beginning of the game, this might be unproblematic, but for something that will be called several times during the game it is quite jarring. So the loop limit isn’t really the problem here.

As it stands, I think my system is perfect for anything between the scales of King’s Bounty and XCOM, but for games lime Civ I think it is too slow at the moment. Perhaps not for player movement, but calculating all AI movement between turns is where I think my blueprint would start freezing up the game for a long time. I know of some ways to cheat by making the algorithm much quicker, but less precise, for long distances, so that’s one possible solution.

I’ll try to be as much help as I can when you get to making your own pathfinding, but I suspect you might wantto delve into C++ for something on the scale of Civ.

18

[=;182940]
Ok, good. Does it seem like the amount of tiles have almost no impact, as long as they are off screen, or is the effect just less pronounced? How is the framerate when zoomed all tne way out compared to having say 20*20 tiles in view?

I’m planning on making huge, procedural worlds, and these sorts of things will determine how I go about doing that. Worst case I have the world stored in arrays, and only spawn the tiles just before they enter view, deleting them as they leave. I can check this out myself, of course, but I suspect you have taken more time perfecting your tile spawning algorithm.

[/]

I haven’t messed with the graphical performance since I know I need to fix a few things before worrying about it. Maybe tomorrow I will take a closer look at it to see the different with and without trees, FPS changes at zoom, etc.

[=;182940]
What you are describing sounds like the difference between using the search function in an array as compared to the get function. Using search is comparable to opening every file in a file cabinet until you find the one you’re looking for, while using get is comparable to just checking a single, specific file at an index.

This is the reason why I use get functions almost exclusively, and I suspect this is the reason why my algorithm is reasonably efficient. Still, I will try to compare pathfinding on a small grid to pathfinding on a large grid in a sealed off area and report the results.
[/]

Yeah I use Get as well, and that was how I figured it worked. The person I was talking to does not work with UE4 so he may not have completely understood what I was talking about. I don’t know enough about how things work under the hood to say either way.

[=;182940]
This is with the old loop limit. Increasing the loop limit is of course not that big of a problem. However, when getting close to hitting even the old loop limit, the game freezes noticeably for about a second. For generating a map at the beginning of the game, this might be unproblematic, but for something that will be called several times during the game it is quite jarring. So the loop limit isn’t really the problem here.
[/]

Yeah I was afraid of that. Though, in a turn based game you don’t need to calculate dozens of paths at once so perhaps it can be parsed in a way that is seamless. Alternatively, I would love for a good method of pushing functions into other threads from blueprint. Use half the cores on the CPU to generate paths all day long while the rest handle generic stuff like UI and other simple logic.

[=;182940]
As it stands, I think my system is perfect for anything between the scales of King’s Bounty and XCOM, but for games lime Civ I think it is too slow at the moment. Perhaps not for player movement, but calculating all AI movement between turns is where I think my blueprint would start freezing up the game for a long time. I know of some ways to cheat by making the algorithm much quicker, but less precise, for long distances, so that’s one possible solution.

I’ll try to be as much help as I can when you get to making your own pathfinding, but I suspect you might wantto delve into C++ for something on the scale of Civ.
[/]

I think there is a way to calculate portions of the path at a time, pause, calculate some more portions, etc. Something using tick(framerate dependency?) and forloops I think. People kept telling me I should do that for the map generation, when really that is something I want to complete as soon as possible without care of a general freeze because I can still update some loading bars and shift some images in front of the player while they wait for the map to generate. Pahfinding could benefit from those suggestions though so I will have to research it some more when I get to that point.

Also I think there are quite a few ways to reduce some of the pathfinding load such as checking to see if both units are on the same continent before pathfinding the whole thing only to find you need a boat anyway. Also, I think there are ways to save commonly used paths, though that would take some serious work to get working properly I think.

In the end though, I think pathfinding will go into C++ no matter how fast I can get it working in blueprint just because either way it will be near the top in resource usage.

19

[=;182969]
I haven’t messed with the graphical performance since I know I need to fix a few things before worrying about it. Maybe tomorrow I will take a closer look at it to see the different with and without trees, FPS changes at zoom, etc.
[/]

No rush. Just asked in case you had checked already. As I said, I can always check it out myself, though I have a very simple tile grid at the moment.

[=;182969]
Yeah I use Get as well, and that was how I figured it worked. The person I was talking to does not work with UE4 so he may not have completely understood what I was talking about. I don’t know enough about how things work under the hood to say either way.
[/]

Yeah, if that’s not the case I don’t really see the point of having a get-function. Did your friend explain what sort of math one would have to do to get around it? I can’t really imagine what that would be. I guess if it turns out that large arrays does slow down the algorithm, you could ask him to explain it in more depth.

[=;182969]
Yeah I was afraid of that. Though, in a turn based game you don’t need to calculate dozens of paths at once so perhaps it can be parsed in a way that is seamless. Alternatively, I would love for a good method of pushing functions into other threads from blueprint. Use half the cores on the CPU to generate paths all day long while the rest handle generic stuff like UI and other simple logic.
I think there is a way to calculate portions of the path at a time, pause, calculate some more portions, etc. Something using tick(framerate dependency?) and forloops I think. People kept telling me I should do that for the map generation, when really that is something I want to complete as soon as possible without care of a general freeze because I can still update some loading bars and shift some images in front of the player while they wait for the map to generate. Pahfinding could benefit from those suggestions though so I will have to research it some more when I get to that point.

Also I think there are quite a few ways to reduce some of the pathfinding load such as checking to see if both units are on the same continent before pathfinding the whole thing only to find you need a boat anyway. Also, I think there are ways to save commonly used paths, though that would take some serious work to get working properly I think.

In the end though, I think pathfinding will go into C++ no matter how fast I can get it working in blueprint just because either way it will be near the top in resource usage.
[/]

Having multi threading I blueprint would be incredibly useful, though I have my doubts it will be implemented any time soon. Slowing down the algorithm to run over several frames is no problem at all, however. If you tried out the old A* blueprint I shared on these forums, you may have seen that you could play a visualized A* in slow motion that I used for debugging. There was no upper limit to the size of paths that can be generated like this, and that should be the case also for much, much faster loops.

As long as you’re willing to wait there are no limits, but for games of the complexity of Civ, this translates to very long waits between turns. This is already a pretty big problem in Civ V, and I imagine they have highly optimized pathfinding code written in C++. There are, and you mention some, many way to “cheat” and make quicker search algorithms, and you need all the help you can get in a huge game like Civ, but that probably includes C++

20

Ran some 20K tile maps without trees and it was pretty good. Hard to say how much lag there is because at high altitudes moving around is naturally slow, but definitely better than it was with trees. Trees might add 50-100K meshes to my scene. I am thinking under 30-50K meshes is manageable, but that is also going to depend on what texture resolution, how complex the meshes, etc.

The math we were talking about is really on my end since I could Get from an array or do 3 steps of math to get the same value. He said that the math would be more efficient since it could stay on the CPU and not access memory, in addition to it trawling the length of the array.

I think you should be able to process some pathfinding information in the background between everything else by using a tick function to space it out based on performance. Then anything leftover could be worked out at the end of the turn. I don’t know exactly how that would be done, but from other discussions it seems the way to go, perhaps even in C++.