Turn based strategy system

Community Showcase Game Development
81

Yeah just needs plugins for various things through blueprint. If there aren’t any ways to manipulate EQS using blueprint maybe we can get that added before they wrap up development on it. I am not even sure if it is exposed to the editor or if that is coming in 4.7 or later.

Of course, documentation would be nice too. I am trying to see how exposed the navmesh really is, but the entire system is pretty opaque from a blueprint standpoint. It was obviously designed to run in 3D enviroments with walls, floors, and enemies and that is about it. If there are ways to specify grids, grid point costs, path destination points, etc from blueprint then it isn’t immediately obvious how that is supposed to be done. The only documentation I could find was all about the in editor/viewport navmesh.

82

[=;203698]
I’m using quite a few 2d arrays through the entire blueprint (or, really, modified 1d arrays). As everything is grid-based I don’t see how I can be more efficient by not using arrays, as they are the most grid-like data structure.
[/]

You’ll obviously need a grid based data structure at the core, but this is the only data structure you should need and everything else should be obtainable using queries across that data structure - the exception to that is perhaps when you want to find a path, in which case you’d want an ordered array to retain the found path. For things like visibility and such, it should be possible to simply query each node in the graph in turn to determine if it is visible, no storage of which are visible and which are not should be necessary :slight_smile:

[=;203698]
However, rendering the visible area takes less than a tenth of the time compared to calculating what tiles are visible, so if I am to have any large performance improvements from using a render target it would have to do more than just rendering… Could you give me a quick step-by-step explanation of how you would go about generating visibility with a render target?
[/]

I’d really just use it for rendering. It is possible to read back data from render targets, but I’m pretty sure it’d be quite a lot slower than using your arrays.

83

[=;204257]
Yeah just needs plugins for various things through blueprint. If there aren’t any ways to manipulate EQS using blueprint maybe we can get that added before they wrap up development on it. I am not even sure if it is exposed to the editor or if that is coming in 4.7 or later.

Of course, documentation would be nice too. I am trying to see how exposed the navmesh really is, but the entire system is pretty opaque from a blueprint standpoint. It was obviously designed to run in 3D enviroments with walls, floors, and enemies and that is about it. If there are ways to specify grids, grid point costs, path destination points, etc from blueprint then it isn’t immediately obvious how that is supposed to be done. The only documentation I could find was all about the in editor/viewport navmesh.
[/]

If the navmesh is A*-based (and I think it is) there might be a grid, but it’s possible they represent the environment with some other sort of graph. In that case one would have to force the navmesh to render as a grid. Since Ian already tried and failed to convert the navmesh to a grid it’s probably not a trivial undertaking. Have you begun looking at the source code?

Should we perhaps try to get in contact with Epic and ask if they can make EQS as exposed to blueprint as possible, now that they are in the middle of working on it?

[=;204410]
You’ll obviously need a grid based data structure at the core, but this is the only data structure you should need and everything else should be obtainable using queries across that data structure - the exception to that is perhaps when you want to find a path, in which case you’d want an ordered array to retain the found path. For things like visibility and such, it should be possible to simply query each node in the graph in turn to determine if it is visible, no storage of which are visible and which are not should be necessary :slight_smile:

I’d really just use it for rendering. It is possible to read back data from render targets, but I’m pretty sure it’d be quite a lot slower than using your arrays.
[/]

Ok, thanks for the explanation :slight_smile: So when you said that using a lot of arrays is inefficient, emphasis was on the a lot part. I am trying to keep the arrays as few as possible. At the same time I try to keep the arrays simple, as I believe this might increase processing speed, but I might be mistaken here. For instance I have a boolean array for walkability as well as an enum array for different sorts of pawns (enemies and allies), both as large as the entire grid. In some cases I want to be checking an index of just one of these arrays, while other times I will be checking both. Are you saying that it’s probably faster overall to keep a single array of structs that holds all of the information, even though you would often have to split the structs to get the relevant information?

Being able to store what tiles are visible is actually quite useful. You can for instance store all tiles that are visible and within range of player pawns, and the AI can then choose to approach or avoid these nodes on their turn. This could be done in advance on the player’s pawn’s turns. If I am to instead generate visibility for every player pawn on the map every time the AI wants to decide where to move, it would probably cause a bit of slowdown on the AI’s turns.

84

I’ve made a new preview video of the blueprint running on a hex map, with a combination of visible and invisible tiles. I’m not much of a modeler yet, so I’ve made it it a clean, simple low poly look. Somethin along these lines will be used as an example level for the marketplace release.

https://.com/watch?v=SicrglnZzEY

85

[=;204420]
For instance I have a boolean array for walkability as well as an enum array for different sorts of pawns (enemies and allies), both as large as the entire grid. In some cases I want to be checking an index of just one of these arrays, while other times I will be checking both. Are you saying that it’s probably faster overall to keep a single array of structs that holds all of the information, even though you would often have to split the structs to get the relevant information?
[/]

I’d have used a single array encapsulating the data I need; I don’t see any advantage to maintaining two. Breaking a struct isn’t exactly an intensive operation, so I’d never worry about that.

[=;204420]
Being able to store what tiles are visible is actually quite useful. You can for instance store all tiles that are visible and within range of player pawns, and the AI can then choose to approach or avoid these nodes on their turn. This could be done in advance on the player’s pawn’s turns. If I am to instead generate visibility for every player pawn on the map every time the AI wants to decide where to move, it would probably cause a bit of slowdown on the AI’s turns.
[/]

I can see some use there, but to be honest I’d still not do it; I’d work on the presumption that the AI can query tiles in range and dismiss / score them appropriately. Storing all tiles that are visible to given pawns could mean storing an increasingly large amount of data the more you increase the number of pawns you have!

86

[=;204938]
I’d have used a single array encapsulating the data I need; I don’t see any advantage to maintaining two. Breaking a struct isn’t exactly an intensive operation, so I’d never worry about that.
[/]

So instead of accessing 3-4 separate arrays, each of which could be thousands of members long, you would instead access 1 array and grab all the relevant data from the struct for whatever operation you are about to run. Makes sense When I go into cleanup phase on the generator I will test the gen time before and after switching everything to structs and see if there is any noticeable improvement.

87

[=;204938]
I’d have used a single array encapsulating the data I need; I don’t see any advantage to maintaining two. Breaking a struct isn’t exactly an intensive operation, so I’d never worry about that.
[/]

For simple get-operations you’re probably right, though I wonder if breaking structs will have an impact if it is done multiple times within a loop. I believe it might become more of a problem when you want to change a single element in a struct. Then you would have to both break the struct, change the relevant variable and make a new struct before setting the new struct into the array array. How inefficient this would be is of course an empirical question, and I’ll try to simulate it before changing my blueprint. If it is at least equally fast as my old method I’ll probably og with your suggestion and change to having a single array, as it will probably be cleaner and simpler to work with.

[=;204938]
I can see some use there, but to be honest I’d still not do it; I’d work on the presumption that the AI can query tiles in range and dismiss / score them appropriately. Storing all tiles that are visible to given pawns could mean storing an increasingly large amount of data the more you increase the number of pawns you have!
[/]

That depends how you store it. I would use a single array the size of the map to store the visible tiles of all pawns instead of having a separate array for each pawn, if I understood you correctly in how you persumed I store my data.

[=;204983]
So instead of accessing 3-4 separate arrays, each of which could be thousands of members long, you would instead access 1 array and grab all the relevant data from the struct for whatever operation you are about to run. Makes sense When I go into cleanup phase on the generator I will test the gen time before and after switching everything to structs and see if there is any noticeable improvement.
[/]

Please let us know if you find it to be quicker. I’ll get around to checking it myself, but I probably won’t be able to for the next few days due to work.

88

[=;204992]
For simple get-operations you’re probably right, though I wonder if breaking structs will have an impact if it is done multiple times within a loop. I believe it might become more of a problem when you want to change a single element in a struct. Then you would have to both break the struct, change the relevant variable and make a new struct before setting the new struct into the array array. How inefficient this would be is of course an empirical question, and I’ll try to simulate it before changing my blueprint. If it is at least equally fast as my old method I’ll probably og with your suggestion and change to having a single array, as it will probably be cleaner and simpler to work with.
[/]

Remember that Blueprint compiles down to byte-code, so what you see does not necessarily represent what you get. Non-coincidentally, that byte code is pretty similar to that used by Unrealscript. Accessing, making and breaking structs should compile down to something very inexpensive. If using a struct will clean-up your blueprints, it’s probably worth doing. I suspect there’s little to no observable performance difference between the two. I’d imagine a single array may well be quicker than multiple arrays, but I can’t say I’ve ever tested that theory…

[=;204992]
That depends how you store it. I would use a single array the size of the map to store the visible tiles of all pawns instead of having a separate array for each pawn, if I understood you correctly in how you persumed I store my data.
[/]

Whilst this is certainly possible, it’s still not great; you have an array the size of the entire map and you’re dumping a lot of data into it at frequent intervals. Using a notion of relevancy, it could potentially be better to use an array per-pawn than one incorporating the entire map, as only a small number of pawns are going to be relevant to another given pawn - it’s also more flexible, as you can prioritise line of sight to some pawns over others. Either way, I’d still just ditch the arrays and use a query to find an appropriate tile (to move to or whatever) and not store any data at all; you’re probably doing all the groundwork required to do that already anyway in order build that big data structure and when you use it, only when using queries and relevance you only work with the smaller subset of tiles you need to. Does that make sense?

89

[=;204992]
Please let us know if you find it to be quicker. I’ll get around to checking it myself, but I probably won’t be able to for the next few days due to work.
[/]

Oh it may be some months before I do anything like that, so if you get to it first I would love to see the results. :slight_smile:

90

[=;205025]
Whilst this is certainly possible, it’s still not great; you have an array the size of the entire map and you’re dumping a lot of data into it at frequent intervals. Using a notion of relevancy, it could potentially be better to use an array per-pawn than one incorporating the entire map, as only a small number of pawns are going to be relevant to another given pawn - it’s also more flexible, as you can prioritise line of sight to some pawns over others. Either way, I’d still just ditch the arrays and use a query to find an appropriate tile (to move to or whatever) and not store any data at all; you’re probably doing all the groundwork required to do that already anyway in order build that big data structure and when you use it, only when using queries and relevance you only work with the smaller subset of tiles you need to. Does that make sense?
[/]

An advantage when using a map-wide result container, in the case that only one pawn needs path finding accessible at a time, is that you don’t need to need to reallocate new data arrays all the time and can just reuse the already allocated map size array. If you need multiple exploration results at the same time though memory usage, would be really bad the larger the map becomes.

[]
So instead of accessing 3-4 separate arrays, each of which could be thousands of members long, you would instead access 1 array and grab all the relevant data from the struct for whatever operation you are about to run.
[/]

This is what I do. Not for performance reasons though, but for reuse of the getter code. I have a function GetTileData(X, Y) that returns the struct data (or a default struct if X,Y is invalid… structs can’t be NULL) and I just split it and read whatever I need. I assume though that when you need multiple data from that struct, accessing is as a struct is faster than doing gets from multiple arrays, since data from a single struct is aligned in memory. I have no numbers though, but like I assume the difference to be hardly noticeable.

91

Ok, I’ve done a quick simulation in blueprint. The performance difference seems to be small, though not entirely insignificant. The simulations in the blueprint depicted below looped through arrays of 100k elements. Setting all items in the int array took on average 51.5 milliseconds, while it was 55 milliseconds for the struct array. This was on the slower of my two desktops, which is about three years old. This is a difficult result, as its almost, but not quite small enough to ignore. For most blueprints it will of course make no difference, but for things like pathfinding and procedural generation it might be enough to take into consideration. If you need to get multiple items from the array at the same time, using a struct array will probably be quicker, as Nisshoku pointed out, so speed will probably depend on the usage.

StructSpeed.png
StructSpeed.png1087×487 85.5 KB

Edit: Ok, tried out getting multiple values from the same index in a single array versus two separate ones. Getting from a single array took around 41 ms for arrays of 100000 items, while it took around 42 ms for two arrays. Still a difference, but a much smaller one. The difference would of course keep increasing if you wanted even more info at the same time, though that is rare in my blueprint. Image of the blueprint I used for this simulation:

GetSet.png
GetSet.png1196×511 107 KB

92

If I’m going to be honest, the idea of performance profiling and talking about ms difference when you’re using blueprints, seems a bit silly to me anyway :stuck_out_tongue:

93

[=;205466]
If I’m going to be honest, the idea of performance profiling and talking about ms difference when you’re using blueprints, seems a bit silly to me anyway :stuck_out_tongue:
[/]

Yeah, I can see where you’re coming from. If you want great performance you should just use C++ instead. However, in my case I’m going to release this on the marketplace, and at the moment it’s not possible to submit C++ code. With this constraint it becomes more relevant to test. Even though we’re talking pretty small differences here, in my experience with huge blueprints, all these little delays tend to add up.

I did only check this out because of your suggestion that using a single array would be significantly more efficient than using multiple arrays. The results seem to show that it will be about equally efficient, which means it becomes more a matter of taste how you want to structure your blueprint. I think these sorts of discussions on the forums might be useful even when disregarding the marketplace submission constraints, as there are many UE4 users that work exclusively in blueprint (whether they should is another discussion) who might find this sort of information on the forums handy.

I still see why you find it silly, though. It’s a bit like discussing what grooves on the wheels of your bike would make it go slightly faster when you should probably just take your car :stuck_out_tongue:

94

Is this how easy to convert the pathfinding to a 2D project using your template? Or should it better to try build one from scratch?

95

[=;205629]
Is this how easy to convert the pathfinding to a 2D project using your template? Or should it better to try build one from scratch?
[/]

It should be very easy. Everything is driven by 2D arrays, so the system is basically 2D at the moment. The only reason it is 3D in the previews is that I’ve chosen to use 3D meshes to represent the pawns and the terrain. Admittedly I haven’t tried it out myself yet, but I see no reason why it shouldn’t work.

Edit: That being said, building it on your own can be a really fun challenge if it’s your kind of thing, though it took me a long time to make this.

96

Okay, thanks. Well i think i do other stuff first in my project and see if there isn’t any solution available in marketplace then i start thinking about A*. So do you planning to release this? If so, when?

97

I actually sent my project to marketplace review three weeks ago, which was poor planning as went on holiday right after. Because of this the release has been delayed a bit, even though it is basically finished. It will probably be on the Trello voting boards in a few days, after which it usually takes about a month before it is released on the marketplace.

98

Hey, great addition to the marketplace! Most awesome. Will this work for more than ground planes? So let’s say I’d want flying drones or something? It’d be good to hear how it handles paths opening up and closing as well, if it does at all.

Thank you!

99

[=;206337]
Hey, great addition to the marketplace! Most awesome. Will this work for more than ground planes? So let’s say I’d want flying drones or something? It’d be good to hear how it handles paths opening up and closing as well, if it does at all.

Thank you!
[/]

Thanks! At the moment it only works for a single ground plane, with no more than one pawn per tile. This is one of the first things I want to add, however. I’m not sure if I’ll be able to include it before the release, but if not I’ll try to include it shortly after. I’m not entirely sure what you mean when you talk about paths opening and closing. Do you mean whether new obstacles can be added at runtime, which the pathfinding will take into account? That works right out of the box, as every path is generated anew at the start of each pawn’s turn.

100

It should be pretty easy to alter the grid to work with a Z plane, especially if you only need 1 of them. You could even use Navmesh for the ground as usual, and then have special transitions to the air grid where A* takes over.