Turn based strategy system

[Zeustiak]

Looking good. On the long route, can you get your guy running in the general direction while the rest of the path is calculated? Something like, If Path > X, find short path first, get guy running, then continue calculating long path. This may be an area where some level of multi-threading is required unless there is a workaround.

Actually, I am pretty sure the answer to that is doing this on a tick, where the calculations are somehow spread over a period of time. For a long path I think that would be ideal. When I start work on my own pathfinding solution I am going to have to seriously study how that works.

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

I think that has something to do with the lack of control over the navmesh in BP. If he had gone into C++ he probably could have fine tuned where each navmesh grid point is set and everything else. From what I understand, you can change the grid size and other general navmesh settings in blueprint, but it is still going to automatically generate over your map and without finer control from BP it would be a real pain to line both grids up. Your units might generally stick to the tiles, but not be exactly centered on them for instance. I think that is the kind of problems he was having, but he did say they could have made it better since he tried it last year.

Generally though, after looking at the exposed pieces of navmesh, as well as looking at most of the navmesh documentation/threads I could find, I think there is more there than would be useful for most tile based games. Navmesh is primarily built for 3D solutions and appears to use tracing to build in many if not all cases.

As long as you get the core algorithms put into C++ eventually, I think creating a separate solution for tile based games may be ideal. I feel like Epic is waiting on someone to create this solution in C++ and do a pull request so they can add it to the engine.

[Monokkel]

After several more days of work the blueprint now has enough features that I consider it ready for release on the marketplace!

I will stop adding new features for a while, and focus on polishing and commenting what I already have, so that implementation will be easy and enjoyable for users. Improvements made since my last update is an overhaul of how paths are displayed to the user, using 2d marker-meshes and splines, as well as turn order implementation for the AI and player.

I’ve also had fun making stages out of some meshes from the Couch Knights demo. Check it out:

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

And here are a few images showcasing some of the blueprint’s features:

[=;195543]
Looking good. On the long route, can you get your guy running in the general direction while the rest of the path is calculated? Something like, If Path > X, find short path first, get guy running, then continue calculating long path. This may be an area where some level of multi-threading is required unless there is a workaround.

Actually, I am pretty sure the answer to that is doing this on a tick, where the calculations are somehow spread over a period of time. For a long path I think that would be ideal. When I start work on my own pathfinding solution I am going to have to seriously study how that works.
[/]

The problem with calculating part of the path first is that you have no way of knowing if you are going the right way until you reach the end point. I guess you could start with a greedy search, just choosing whatever tiles are closest to the end compared to the last node, and while your pawn followed the path you could do A* and direct the pawn back onto the path once it has been found. However, if the path requires that you must for instance go backwards first, rounding a wall, you would get imperfect paths. For turn based games I think it’s much better to calculate the entire path first, but there are still some possible shortcuts if you do it like this. I will certainly look into such solutions in the future.

[=;195543]
As long as you get the core algorithms put into C++ eventually, I think creating a separate solution for tile based games may be ideal. I feel like Epic is waiting on someone to create this solution in C++ and do a pull request so they can add it to the engine.
[/]

Heh, yeah. There are really only a couple of points in my blueprint that cause any real slowdown for very long paths, and converting these to C++ is one pf my goals. I don’t think you are allowed to submit C++ code in the marketplace yet, but I could make this as a separate download for anyone in need pf extra speed.

[Zeustiak]

Looking good! The pics remind me of the old games with the toy army men.

[=;197698]
The problem with calculating part of the path first is that you have no way of knowing if you are going the right way until you reach the end point. I guess you could start with a greedy search, just choosing whatever tiles are closest to the end compared to the last node, and while your pawn followed the path you could do A* and direct the pawn back onto the path once it has been found. However, if the path requires that you must for instance go backwards first, rounding a wall, you would get imperfect paths. For turn based games I think it’s much better to calculate the entire path first, but there are still some possible shortcuts if you do it like this. I will certainly look into such solutions in the future.
[/]

Right, I think I had my mind on more real-time solutions that might need that kind of workaround. Calculating a single path in a turn based environment should be fairly instant as long as the path isn’t tens of thousands of tiles long. It is all the AI pathfinding running in the background or when you hit End Turn that I am really worried about.

[=;197698]
Heh, yeah. There are really only a couple of points in my blueprint that cause any real slowdown for very long paths, and converting these to C++ is one pf my goals. I don’t think you are allowed to submit C++ code in the marketplace yet, but I could make this as a separate download for anyone in need pf extra speed.
[/]

I mean someone needs to make it in C++ and then do a pull request on Github. Would be bonus if that happens before I get to it, but I am not counting on it.

[Monokkel]

[=;197880]
Looking good! The pics remind me of the old games with the toy army men.
[/]

I guess it shows that I grew up playing Army Men

Good times

[=;197880]
I mean someone needs to make it in C++ and then do a pull request on Github. Would be bonus if that happens before I get to it, but I am not counting on it.
[/]

We’ll see, but with how far you’ve come in your map generator it’s unlikely someone will have made it in time. For my own part I plan on at least adding hex grids and elevation before adding C++ functions

[Zeustiak]

Yeah same here. I will push everything in blueprint as far as it can go before moving to C++. The generator could probably always stay in blueprint, but it will just be faster in C++. Pathfinding on my scale though, will just have to be in C++ at some point or the game won’t be playable in the end game. This is a problem with most 4X games that I aim to defeat. Hopefully all those other studios just didn’t have the time to find a good solution by the time they realized it was a problem, which means it is possible to solve. One of my goals is to get each AI on it’s own thread eventually. We will see how that helps.

[anonymous_user_c777a802]

FWIW When you’re ready to release this, I would be more than happy to help with the porting to C++. I may be new to Unreal, but I’m comfortable enough with C++ and I feel like this would be a reasonable exercise in learning my way around UE4.

[anonymous_user_75c92df2]

Any idea on when this is coming out? I’m starting the prototyping for my game and I’d love to use this as a starting point instead of getting all of this up and running myself.

[Monokkel]

[=syynth;199588]
FWIW When you’re ready to release this, I would be more than happy to help with the porting to C++. I may be new to Unreal, but I’m comfortable enough with C++ and I feel like this would be a reasonable exercise in learning my way around UE4.
[/]

Thanks for the offer Part of my motivation for converting is to learn C++, so I intend to figure out as much as I can on my own just for the sake of learning. But I’ll be sure to get in touch if I need help.

[=owensd;199940]
Any idea on when this is coming out? I’m starting the prototyping for my game and I’d love to use this as a starting point instead of getting all of this up and running myself.
[/]

Thanks for the interest! It’s my hope that this blueprint will save people a lot of time. I sent it to epic right before christmas, but I haven’t heard anything from them yet, probably because it’s the holidays. They are supposed to start with new updates come january 7th, so hopefully my blueprint will be up on the Trello boards shortly after.

[Monokkel]

Whew! After spending days cleaning up and commenting my blueprint it’s finally in a state where I believe others will be able to understand and use it. This was the first time working in blueprint really felt like work, but I’m glad I took the time, as it will now also be a lot easier for me to work with as well. It runs smoother too Below is a screenshot of the entire blueprint. Almost everything in my system is contained in that blueprint, save some small blueprints in the pawns, tiles and camera. It’s a lot bigger than it looks at a glance, since there are tons of macros, functions and collapsed graphs; some running several levels deep. Reminder to self: start tidying while you’re working.

After trimming out all unnecessary bits from the blueprint, it now weighs in at 2.5MB. A lot less than what I would have predicted.

[Moss]

Seams very promising! Can’t wait to see it in action in a game!

[Monokkel]

Thank you! So do I

[Zeustiak]

Nice. Do you have anything to take into account other objectives in addition to attacking? I am thinking of another grid with tile importance values that would represent strategic objectives that the AI could weigh when making paths.

I have been doing a bit of refactoring myself, but I still have a huge amount left to do once I reach a stopping point with the generator. Sitting at 19MB, probably 20-22 by the time I am done with the current work. Contemplating ways to split it up while still managing it from a central blueprint.

[Monokkel]

The system should be fairly flexible in its current state, and the current method of checking is mostly thought as an example. It is driven by a priority array that is currently set to the health of any enemy pawns occupying it, but you could easily change that to number of trees for harvest, powerups to pick up or anything else. However it only cares about the end point at the moment, and cannot prioritize what tiles to pass through along the way to the goal. That’s actually a non trivial problem, and will take a bit of work, but is planned down the line.

[Monokkel]

New big update! After cleaning up the blueprint I could finally go back to adding new features, and I started by adding my favorite one: Hex grids!

There are still a few minor issues that need to be ironed out (the viewport doesn’t handle hex grid snapping by default, for example), but for the most part everything that works with square grids now also works with hex grids. Adding hex support was easier then what I had feared, but then I had designed the system to be mostly grid agnostic from the start.

[Zeustiak]

Great! Are there spaces between the hexes or is the black hex outline an overlay or part of the grey hex? Been wondering what the best option for such an overlay might be without creating thousands of new meshes. Though I guess I could just use a material on my collision volumes while reshaping them…

[Elendil]

Awesome work man ! I’m impressed …

[ambershee]

Hexagonal grids has piqued my interest.

Great work so far!

[Zhi_Kang_Shao]

Wow nice work, support for hex grids.

[jonimake]

I suppose the grid cell size is variable too?

[Monokkel]

[=;201110]
Great! Are there spaces between the hexes or is the black hex outline an overlay or part of the grey hex? Been wondering what the best option for such an overlay might be without creating thousands of new meshes. Though I guess I could just use a material on my collision volumes while reshaping them…
[/]

In the screenshot I’m using a grid of instanced static meshes generated in the construction script. Here is a closeup:

The tiles are just for show, however. The system works just as well with just a single collision plane for the entire grid. You don’t need individual collision volumes or anything, as everything is calculated using arrays and vectors. I’m going to include some various options for displaying the grid with the marketplace release, but how the grid is visualized is unconstrained by the system. If you wanted to make something really optimized, but still visualize the tiles, you could possibly use something like 's perfect tile system, where the entire level would just be a single mesh with a single texture.

[=Elendil;201158]
Awesome work man ! I’m impressed …
[/]

[=;201170]
Hexagonal grids has piqued my interest.

Great work so far!
[/]

[=NisshokuZK;201258]
Wow nice work, support for hex grids.
[/]

Thanks to all of you! It’s taken quite a bit of time, but I’m really happy with what I’ve got at this point. I love hex grids, and I originally planned to make it hex based from the start, but for simplicity’s sake I started with a square grid. I always tried to keep it as grid agnostic as possible, though. I could quite easily add other grids too, like triangular grids, but I’m unsure how much interest there will be in such stranger grids. I’m probably going to add them later, but that’s a lot further down the line.

[=jonimake;201325]
I suppose the grid cell size is variable too?
[/]

Sure is! I guess I never made a post about it, but about a week ago I made it so the size of the cells can be scaled to whatever size you want, and be placed wherever you want on the map. You could have a small chess board game on a table within a larger 3D-game for instance, without having to bother scaling and moving everything around the grid. You can also use tiles with different width and height if you want to (2 x 1 rectangles, for instance), though I haven’t seen any games that use that sort of grid. But who knows what people will use my blueprint for, right?