Turn based strategy system

Community Showcase Game Development
21

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

Ok, that seems promising. Did you check fps, or did it just feel slower at higher altitudes?

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

Hmm, ok. I’m having a hard time seeing how I would implement this in my blueprint. Perhaps it is because we do things differently. Everything in my blueprint is based on arrays. Could you quickly try to describe the three steps of math you mention? Do you get the numbers from the actual coordinates of the tile meshes?

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

Yeah, spreading the loops out between ticks is certainly possible, and I’ve done it my blueprint. I don’t feel the need at the moment, but when I start creating AI that will have to consider multiple paths before deciding, it might become necessary. Worst case I’ll have them have a question mark above their heads while they decide, like in the old Worms games. I doubt it will run that slow, though.

22

[=;184313]
Ok, that seems promising. Did you check fps, or did it just feel slower at higher altitudes?
[/]

Just overall response of starting movement and also my line trace which currently hides my colored volumes seemed to react slower. I didn’t check FPS. I probably need to delve into the performance monitoring tools, but I haven’t really had the need to yet. When things are slow or choppy I already know why so I haven’t had much need.

[=;184313]
Hmm, ok. I’m having a hard time seeing how I would implement this in my blueprint. Perhaps it is because we do things differently. Everything in my blueprint is based on arrays. Could you quickly try to describe the three steps of math you mention? Do you get the numbers from the actual coordinates of the tile meshes?
[/]

I pretty much use all arrays as well, but I do a lot of work using the index for the current and surrounding tiles.

The math in my case revolved around checking what offset I am on. Right now, I take current index and get the offset from an array. That is one area where I could instead take current index, and based on it’s value figure out which offset I am on with 3 steps of math, and he was saying it would be faster. Probably right if Get with Index plows through the whole array, but he might still have a point as well even if it doesn’t just for memory issues. But it might be moot either way. It is something I will test out when I have time or when I am doing a big optimization push.

[=;184313]
Yeah, spreading the loops out between ticks is certainly possible, and I’ve done it my blueprint. I don’t feel the need at the moment, but when I start creating AI that will have to consider multiple paths before deciding, it might become necessary. Worst case I’ll have them have a question mark above their heads while they decide, like in the old Worms games. I doubt it will run that slow, though.
[/]

Yeah I think it depends on how many actors need to decide paths at one time, and what kind of time frame they have to decide in. I think ideally, you want the AI to do as much work as possible simultaneously while the player is deciding their moves. Any work left to be done when the player hits end turn will just have to be performed then.

I have been pondering ways to handle turn based movement and turn sequencing to take into account pathfinding times among other things. If you have ever played a Civ game you know how pathfinding really bogs even the best computers down in the endgame, especially on larger maps. A large part of this is all the workers roaming around, which is one reason why the tile improvement system won’t be based on units. But generally I think a lot of the calculation is performed at the end of the turn anyway which sets you up for a wait.

One way to improve end of turn time would be to handle movement so that it all happens at the end of the turn. That way the the pathfinding could bake while the player makes their moves, and any player movement wouldn’t necessarily spoil pathfinding work that has already been performed. Then, when end of turn happens and the movement phase commences the pre-calculated pathfinding starts moving pieces including the player units. This would have units moving into a tile simultaneously, starting battles. Players would have to be a little more careful when racing off into the darkness. Comes with the trade off of players losing a bit of control and predictability though, so that has to be gauged.

There are probably other problems that aren’t immediately apparent as well. Pathfinding and turn sequence go hand in hand and the rest of the game depends on it, so I will be spending a lot of time working those details out before moving on to other systems.

23

Ok, time to finally show a couple of the more visible changes I’ve made: Variable terrain cost and spline smoothed movement. Here is a quick vid:

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

The tiles in this video have twice the movement cost of regular tiles, which in this case makes moving around them a more efficient path. This video doesn’t demonstrate it too well, as the same path would in this case be generated even if the brown tiles had a much higher cost. Costs can be freely changed to be as high as one desires, and can even be made lower than regular tiles. As mentioned I’ve also made movement a lot smoother, by having the pawn follow a spline through the path. I’ve also added the option of displaying the path spline as an alternative to arrows or highlighted tiles for showing the path, though this isn’t shown in the video. Under the hood, I’ve made numerous improvements, and the system is now more efficient than ever before.

[=;184563]
Just overall response of starting movement and also my line trace which currently hides my colored volumes seemed to react slower. I didn’t check FPS. I probably need to delve into the performance monitoring tools, but I haven’t really had the need to yet. When things are slow or choppy I already know why so I haven’t had much need.
[/]

I’ve checked the fps of my own project now. A 100100 grid was much more than 120 fps. 200200 dropped it to around 90, and 400*400 to around 60. But I just realized that I am spawning a separate tile volume actor for each tile instance, which I can probably find a way around, and which will probably make things a lot quicker. Showing fps is as simple as clicking the downward facing arrow in the top left of the viewport and selecting “show FPS” by the way.

[=;184563]
I pretty much use all arrays as well, but I do a lot of work using the index for the current and surrounding tiles.

The math in my case revolved around checking what offset I am on. Right now, I take current index and get the offset from an array. That is one area where I could instead take current index, and based on it’s value figure out which offset I am on with 3 steps of math, and he was saying it would be faster. Probably right if Get with Index plows through the whole array, but he might still have a point as well even if it doesn’t just for memory issues. But it might be moot either way. It is something I will test out when I have time or when I am doing a big optimization push.
[/]

Ok. I don’t use any offsets at the moment, so I don’t have your exact problem. I did notice some slowdowns when using huge grids which might be explained by what your friend is suggesting. Starting the Dijkstra and a* algorithm froze the game for a noticeable amount of time when playing on a 400*400 grid, even though the path finding array shouldn’t really be any bigger. There might be several explanations for this, though, and I’ll try to figure it out.

[=;184563]

Yeah I think it depends on how many actors need to decide paths at one time, and what kind of time frame they have to decide in. I think ideally, you want the AI to do as much work as possible simultaneously while the player is deciding their moves. Any work left to be done when the player hits end turn will just have to be performed then.
[/]

That’s a really good solution, actually. If I ever experience any problems with slowdown when creating AI, I’ll definitely try something like this.

24

Nice.

Got FPS to work, but I was reminded of a problem that only seems to plague me when playing the game from the level viewport. Upon starting the game in any mode, the camera/map is furiously spinning like a propeller. I don’t have this problem when playing using any mode using the play button in a blueprint. I made a post about it ages ago but there was no response. Probably some camera problem but it is low on my priority list.

Anyway, FPS is about .5-10 when the map is generating, then 110 when it has loaded, and then when I quickly zoom out it can drop to 30-40 before rising back to 90 when I have stopped zooming. This is on a 5K tile map which is really more like 15K with the 2 world wrap maps. Also, enabling visibility on my tile overlays dropped the FPS to 30-40.

25

Hi , awesome work so far! Great to see activity in the turn based strategy department. I wanted to mention here as a heads up that I’m also working on a blueprint path finding implementation. I’ve worked on those in the past, here are some samples of the system I made though not in UE4:https://.com/watch?v=EFb5LhhxUnohttp://36.media.tumblr.com/9d45cd0aa24a9711710fef44e64694e1/tumblr_n2edrjTxKx1r3dimco1_1280.png

My goal is to submit it to the marketplace as well. I really hope I’m not messing up your plans by that, since you are also considering to submit it to the marketplace. I wish I found this post sooner so I could’ve notified you earlier.

26

[=NisshokuZK;187154]
Hi , awesome work so far! Great to see activity in the turn based strategy department. I wanted to mention here as a heads up that I’m also working on a blueprint path finding implementation. I’ve worked on those in the past, here are some samples of the system I made though not in UE4:https://.com/watch?v=EFb5LhhxUnohttp://36.media.tumblr.com/9d45cd0aa24a9711710fef44e64694e1/tumblr_n2edrjTxKx1r3dimco1_1280.png

My goal is to submit it to the marketplace as well. I really hope I’m not messing up your plans by that, since you are also considering to submit it to the marketplace. I wish I found this post sooner so I could’ve notified you earlier.
[/]

Hi Nisshoku, no worries :slight_smile: Turn based and tile based systems are common in marketplaces of all game creation software, so I had no illusions that I was the only one working on this. But thanks for the heads up anyway! For my own system, I am planning to give it out for free when I am done with something that works. However, if I am later going to spend a lot of time making it more accessible and easy to understand, I’ll probably want to put a price tag on it (though the old version would still be free). For the user it can only be a good thing to have multiple different implementations to choose from, and I’m sure there will be enough differences between our solutions that they may appeal to different developers. Good luck on your blueprint!

27

I see, relieved to hear that. :slight_smile: Yes, I’m sure there will be implementation differences making both useful to have on Marketplace. You also best of luck and I’ll keep an eye out for your updates!

28

[=NisshokuZK;187658]
I see, relieved to hear that. :slight_smile: Yes, I’m sure there will be implementation differences making both useful to have on Marketplace. You also best of luck and I’ll keep an eye out for your updates!
[/]

Thanks! Are you planning on making a progress thread as well?

29

I did! You can find it here: Path finding and action planning for Fire Emblem-like games (large images beware) - Work in Progress - Unreal Engine Forums

Let me know what you think. :slight_smile: I’ve been thinking about possible differences in our implementations (and goals). I see that you did a stress test with a huge map, do you allow for path queries of any size? I’m wondering because you did show an image where you highlight all tiles within X range, did you compute those using multiple path queries or one exploration query?

30

[=NisshokuZK;189093]
I did! You can find it here: Path finding and action planning for Fire Emblem-like games (large images beware) - Game Development - Epic Developer Community Forums

Let me know what you think. :slight_smile: I’ve been thinking about possible differences in our implementations (and goals). I see that you did a stress test with a huge map, do you allow for path queries of any size? I’m wondering because you did show an image where you highlight all tiles within X range, did you compute those using multiple path queries or one exploration query?
[/]

Cool! I’ll be following that one for sure :slight_smile: I’ve done a lot of changes since I did the stress test, and the whole system is currently undergoing a major revision. When I did the stress test, I used one quick exploration query to find all reachable nodes, and then a path query to find the path to a specific endpoint among those nodes. I’ve since changed it so I do everything in a single exporation query.

As for my goals, I ideally want to create a base template that can easily be adapted for multiple sorts of turn based strategy games, like XCOM, King’s Bounty, Final Fantasy tactics and, yes, Fire Emblem. I want to include the bases that are common to all these sorts of games, but leave the development of more game-specific elements to the user.

31

Ok, it’s been a while since I’ve updated, but that doesn’t mean I haven’t been busy. I’ve made three big changes since last time:

  1. Tile maps can now be created and edited directly in the viewport without launching. I felt it pointless to reinvent the wheel by creating my own lever editor from scratch, when UE4’s built in viewport editor is already excellent for such a purpose. I had to add a lot of functionality myself, but thanks to construction scripts and blueprint interfaces, this was surprisingly simple. Creating tiled levels where the blueprint recognizes walls, difficult terrain etc. is now drag and drop, as is placing pawns. Creating new pawns and tiles with different meshes and abilities has also been made easy, with several modifiable attributes being inherited from the TilePawn and TileBase parents, such as move speed and attack distance for pawns and walkability and added movement cost for tiles.

  2. I’ve thrown Aout the window and am using Dijkstra’s algorithm for everything at the moment. It’s gererally much better for the sorts of games I’m making this for, where you almost always want to calculate all paths a pawn can reach from it’s current position. I might bring A back for specific jobs, such as calculating really long specific paths in games with very large maps, but at the moment Dijkstra works like a charm. Now all possible paths are calculated at the same time, making comparing different paths later on much, much faster. And speaking of faster:

  3. Overhauled much of the blueprint, making it about half as big, and a lot more intuitive. In the process I identified some bottlenecks in performance, and the system had yet again become much more efficient. All possible paths for a pawn with a movement of 10 tiles/turn on an open grid are calculated in less then a millisecond. The blueprint has come a long way since I was proud to have it calculate individual paths of eight tiles without crashing!

I feel the blueprint is really starting to shape up nicely, and though there are still loads of features I want to add I feel the fundament is now in place. Here’s a video that demonstrates how tile grids can be built in the viewport as well as a glimpse of the speed of the improved path finding algorithm:

https://www…com/watch?v=-We2vaEwAMk

(P.S. All paths are generated almost instantly. The path changes in the video because I’m hovering the mouse over different tiles)

32

Looking good. :slight_smile:

How big(in kilo/megabytes) is your pathfinding blueprint?

Are you going to add any low-level AI stuff like deciding between 2 possible objectives when making a path? For instance, you tell the unit to move from one continent to another, so it decides which of 2 ports is closest or and/or best, and then chooses one to use for the water crossing. Then it would have a similar scenario when choosing a path to the best landing zone(s).

That sounds specific, but I think you could make it pretty generic with a multi-objective pathfinding process so that people could just assign objectives and then weight those objectives based on whatever factors.

33

[=;190557]
Looking good. :slight_smile:
How big(in kilo/megabytes) is your pathfinding blueprint?
[/]

Thanks! I’m unsure. I’ll check when I have the opportunity. However, the blueprint is still undergoing big changes, and I know I’ll be deleting and adding a lot of paths.

How big is your blueprint? Do you have everything contained within a single blueprint, and what sort of blueprint is it? In my case almost everything is contained within an actor that has a single instance in the scene. All other blueprints also do most of their functions through this blueprint, using blueprint communications.

[=;190557]
Are you going to add any low-level AI stuff like deciding between 2 possible objectives when making a path? For instance, you tell the unit to move from one continent to another, so it decides which of 2 ports is closest or and/or best, and then chooses one to use for the water crossing. Then it would have a similar scenario when choosing a path to the best landing zone(s).
That sounds specific, but I think you could make it pretty generic with a multi-objective pathfinding process so that people could just assign objectives and then weight those objectives based on whatever factors.
[/]

That’s actually my next planned feature, and probably the biggest reason why I switched to using Dijkstra’s algorithm exclusively. All I have to do is add the location and attributes of relevant actors encountered during the path finding search. From these I can create an array of possible targets and then choose the one that fits certain criteria, such as the enemy with the lowest health, the closest city that has a port etc.

A quick note I’d like to add is that the blueprint no longer needs a physical grid of actors to function. Everything works just as well with just a single, solid plane, for instance. In the future I might add the possibility of doing pathfinding on uneven surfaces, perhaps with a grid projected onto a landscape mesh. That’s a bit down the line, though.

34

This looks really interesting! I saw that you wouldn’t mind sharing some of this code a while back. If you still wouldn’t mind doing so, is there any way I could take a look at this?

35

Hi syytnth. Thanks for the interest. My original plan was to design a working system for myself first and release it for free before making it cleaner and more beginner friendly and releasing it on the marketplace. However, after getting a lot of requests for getting it to the marketplace earlier, I instead started prioritizing making the system suitable for the marketplace.

A lot of my more recent work has been adding features that won’t benefit me personally that much, but will make it simpler to use for new users. These are features that I have added specifically for a planned marketplace release, and as such I’m afraid don’t intend to share them freely.

However, I have already shared an older version of the blueprint that has full A* functionality, which is what all the rest of the system is based on. That blueprint can be downloaded here. I will also be happy to answer any other questions you might have about the blueprint or how I’ve achieved the later added features, though I do not wish to share the entire blueprint now that I’m getting close to a marketplace release.

36

That is perfectly reasonable! I consider myself a moderately experienced programmer but I’m really new to Unreal and had some interested in building something similar to what you have here for myself, and when I saw your thread I thought it would be a really useful way to get acclimated to UE.

That said, if you will have the system ready for the marketplace soon, I may just go ahead and be your first customer :slight_smile:
Do you have an idea for when you think you’ll be ready with this? I am anxious to get my hands on something

37

[=;190601]
Thanks! I’m unsure. I’ll check when I have the opportunity. However, the blueprint is still undergoing big changes, and I know I’ll be deleting and adding a lot of paths.

How big is your blueprint? Do you have everything contained within a single blueprint, and what sort of blueprint is it? In my case almost everything is contained within an actor that has a single instance in the scene. All other blueprints also do most of their functions through this blueprint, using blueprint communications.
[/]

Mine is sitting at a monstrous 17MB. I have a couple others that might add up to a couple MB. Someday I will split it up, but it works, and I almost want to see how far it can go before hard breaking. :stuck_out_tongue: Compile time might eventually annoy me into carving it up though. Currently a couple seconds.

[=;190601]
That’s actually my next planned feature, and probably the biggest reason why I switched to using Dijkstra’s algorithm exclusively. All I have to do is add the location and attributes of relevant actors encountered during the path finding search. From these I can create an array of possible targets and then choose the one that fits certain criteria, such as the enemy with the lowest health, the closest city that has a port etc.

A quick note I’d like to add is that the blueprint no longer needs a physical grid of actors to function. Everything works just as well with just a single, solid plane, for instance. In the future I might add the possibility of doing pathfinding on uneven surfaces, perhaps with a grid projected onto a landscape mesh. That’s a bit down the line, though.
[/]

It sounds like you could be recreating navmesh. That is one of those things that I wish the devs would expose to blueprints bit by bit so we could plug into it and use the functions that are already in the engine.

38

[=syynth;190927]
That is perfectly reasonable! I consider myself a moderately experienced programmer but I’m really new to Unreal and had some interested in building something similar to what you have here for myself, and when I saw your thread I thought it would be a really useful way to get acclimated to UE.

That said, if you will have the system ready for the marketplace soon, I may just go ahead and be your first customer :slight_smile:
Do you have an idea for when you think you’ll be ready with this? I am anxious to get my hands on something
[/]

Thanks! Glad you understand. I’m done with most of the main features, but I’d at least like to add some basic ai and camera controls before release. I also still have a lot of cleaning up and commenting to do. I have tons of other features planned, but I guess I’ll just patch them in as time goes by :slight_smile: Still, December is very hectic for my, both at work and at home, so I doubt I will be done until early January. I’ll be happy to give you any tips you want to get you started before that time, however.

[=;191142]
Mine is sitting at a monstrous 17MB. I have a couple others that might add up to a couple MB. Someday I will split it up, but it works, and I almost want to see how far it can go before hard breaking. :stuck_out_tongue: Compile time might eventually annoy me into carving it up though. Currently a couple seconds.

It sounds like you could be recreating navmesh. That is one of those things that I wish the devs would expose to blueprints bit by bit so we could plug into it and use the functions that are already in the engine.
[/]

Holy… 17MB‽ That’s frickin’ huge :open_mouth: I think you might actually be the record holder for biggest UE4 blueprint. Mine is at a measly 1.77MB (about a tenth of yours), and shrinking as I simplify and clean it up. I was at a maximum of 2.42 MB a few versions ago. I’m feeling a bit inadequate :stuck_out_tongue: Doesn’t that greatly slow down the framerate in the viewport if you have the blueprint open in a separate window?

As for me recreating navmesh, I guess there is some truth to that. Still, everything would still be grid based (though I guess even that could be changed if I really wanted) and a much better fit for the sort of turn based strategy games I’ve made the system for. I just realized it actually wouldn’t be too hard to implement, but it’s certainly far from a priority. I agree with you that having more of the navmesh functions exposed to blueprint would be extremely useful, though.

39

Yeah I would be surprised if anyone has a single blueprint bigger than mine, but honestly that is only because I am doing it wrong. :stuck_out_tongue: But I know that and I am fine with it for the time being. The only thing that slows down due to the size is the compile time, but it is fine for now. I think there is some other issue where I make a minor or otherwise irrelevant change and the file size changes by several hundred KB. I haven’t tried to really track it down, and it hasn’t otherwise caused issues, but I find it interesting.

When Ian Shadden was helping me out back in spring he mentioned that he had implemented a navmesh solution for his own purposes but had found it somewhat imprecise for grid based movement so he made an A* system. He did mention that it could have gotten better since he tried it so that may have been last year.

I wonder if navmesh uses some kind of A* or similar or if it is just tracing everything out. I know grids are involved, and you currently need a separate navmesh for different enemy sizes. If it does use something similar to A* and we could just get some key pieces exposed then it could be an ideal solution for people using blueprints to get the speed of C++ on the core pathfinding algorithms.

40

Ok, time for a new update. I’ve made three major additions to the system: vision, camera control and AI, and I’m really closing in on it being complete enough for a marketplace release. I’ve included a video that showcases all three new features. They are described in more detail below.

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

Vision: Pawns now have a range stat that determines what tiles they can see or attack (can be used for both). This takes into account any obstacles in the way. In the video, tiles that can be seen by the pawn at its current position are highlighted in red. Building on this I’ve added a new type of tile that blocks movement, but not vision, which is shown in the video.

Camera control: All basic camera control options are included: Pan, zoom and rotate. All movement is made smooth using interpolation. In addition the camera can be set to automatically follow the currently active pawn; which can be overridden by panning.

AI: I’ve made a rudimentary AI which will serve as the basis for future AI-development. This AI chooses the enemy with the lowest health within range and moves into melee range with that enemy. I have not implemented attacking yet, so the pawn just kind of stands there, staring. For the next update I plan on making the AI a bit less friendly. Included in the AI system are the beginnings of an initiative/turn order system.

As an added note I recently ran a new stress test, and again I’m surprised at how well UE4 and my system handles more extreme situations. I created a 400*400 grid (160000 tiles) and placed a pawn with a movement of 100 on it. Calculating the optimal path to in excess of 10000 tiles took less than half a second, and except for that half second judder everything ran at above 60fps (ignore the apparent lag in the video. I still hadn’t fully understood the recording software). This is even though nearly every tile is visible in the viewport. This makes me pretty certain that for small grids, the system is probably efficient enough for mobiles and tablets.

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

[=;191642]
When Ian Shadden was helping me out back in spring he mentioned that he had implemented a navmesh solution for his own purposes but had found it somewhat imprecise for grid based movement so he made an A* system. He did mention that it could have gotten better since he tried it so that may have been last year.

I wonder if navmesh uses some kind of A* or similar or if it is just tracing everything out. I know grids are involved, and you currently need a separate navmesh for different enemy sizes. If it does use something similar to A* and we could just get some key pieces exposed then it could be an ideal solution for people using blueprints to get the speed of C++ on the core pathfinding algorithms.
[/]

It’s interesting that he didn’t manage to get it precise if they use A* pathfinding. I wonder why that would be. I sure hope we can get more of navmesh exposed in time. That might be the easiest way to make grid based pathfinding work well with huge games such as Civ.