I will use this thread to post about my project that I’m currently working on!
Project Shinrin( still thinking of a name ) will be a turn based strategy rpg game, yay, another one!
I’ve been inspired mostly by XCOM and Fire Emblem, and I will combine different elements of those games. But with maybe more dynamic attack abilities like a CRPG like Divinty Original Sin
I’m still looking for an art style but I’ll probably go with something stylized with materials. So not necessarily hand painted.
I’ll keep the setting of the game under wraps for now But you will probably be able to make guesses as I post more.
So, for the actual progress. I’ve been working on this for few months now, only during the weekends though. I do everything alone at the moment and I use blueprints. In the near future I’ll look to convert some of my parent classes to c++ so that I can create c++ functions for them. Everything you see in the video in terms of art are obviously placeholders, just saying
This is a video from earlier this week.
It’s late right now so I probably forgot to mention some things. I will also update this first post in the future so that it is actual with the progress.
If you have any questions or remarks, shoot
Cheers!
Update!
This weekend I worked on the basic AI unit behaviour. The AI first chooses a target unit depending on distance, health and stats. Combining these values gives each unit a score. The unit with the lowest score gets assigned as that AI’s target.
Then I look for the shortest path and check which reachable tile is closest. I had to tweak some of my existing function to make them work.
I was struggling a bit with finding the correct tile. First I checked the shortest path of every reachable tile towards the target unit, which was pretty heavy. I was able to greatly simplify this and changed the function speed from 300ms to 12ms or lower. There is still some error that sometimes generates an infinite loop but that is for next week.
Also lost some time with a corrupted blueprint. I was lucky I had a backup. But I also decided to start using Source Control to avoid this in the future.
The AI doesn’t take attack distance in account yet(for ranged attacks) and will not stop moving when they are standing next to the unit because they want to go to tile their target is standing on.
That is something I will try to do next week.
This looks really promising! We have similar inspirations and it seems like you have ended up with similar solutions to what I have done in my own TBS development in UE4. The problems you are describing sound very familiar to ones I’ve had in the past, so feel free to ask me if you need any input
What are you using for your pathfinding? Personally I use something similar to Dijkstra’s algorithm. This might be unnecessarily complicated for your game if you do not intend to include difficult terrain, but I assume you are using something similar. If so you should be storing the location of a parent tile (the tile you have to go through to reach this tile) in each tile, which means that finding the shortest path to each tile should be nearly instant once pathfinding is completed. 12ms still seems way to slow to calculate something like this, especially if you are not taking attack range into account, so I’m guessing you’re calculating the shortest path to each tile individually when needed? I would recommend reading Amit Patel’s wonderful articles on pathfinding here if you have not done so already. They were immensely useful to me when I was starting up.
Good luck going forward and let me know if you need any insights from someone who has gone through much of the same stuff
Haha hey, Monokkel! Yeah it’s not the first time I see you reply in my threads, so thanks for reading!
I based my pathfinding on A*, but it’s not exactly the same I think so probably more like Dijkstra’s. I have not yet fully implemented the ability to take tile cost in to account I think, but the tiles do have the variable. I’ve read a bit of Amit’s website back when I started with this. Might have to reread some stuff, thanks
Yeah that is what I do, each tile has a parent tile var. I do everything in one function. So it does the pathfinding and then it creates an arrat with the shortest path, with the parent tile variable thing. And then I return the array.
If I have time tonight I’ll fire up my project and see if I can give you more exact times of the functions
Thanks for replying!
Oh, I see! I did not recognize your username immediately and without the character models you used in your last thread I did not realize it was the same project. You seem to bee making great progress! A* is probably unneccessary for a project like this, since you generally want to know the path to all tiles in range and not just one, though there are of couse exceptions. What method are you using for generating the heightmap, by the way? I use line traces myself.
No, it’s not the same project. The project from last year was really my first project to learn blueprints Now I restarted from scratch and made much more organized and better. It’s also not a school assignment this time but my own thing.
Not sure I understand. To get the tiles in range I use a flood fill then I use A* when I hover over the tile I want my character to go to. Is that not good?
For the height I don’t use a map? Like an image? I just calculate their height based on position and compare the values. Units can only go up and down with a special slope tile.
Thanks!
Ok, I see. My toolkit is actually still the same project that I started working on when I first got Unreal Engine, though it has been completely overhauled so many times that I don’t think there is anything left from my first version.
I do indeed think it is not a good idea to run A* pathfinding again every time. If you store the parent of each time when you do your flood fill you can simply take your target tile, get its parent, then get the parent of its parent etc. until you get to the starting point. You should then have your path. If you use both flood fill and then A* you end up doing something multiple times that you only need to do once.
By height map I just meant what solution you have implemented for height in your grid. From your answer it seems like you have a bunch of individual tile actors and you get their locations when you run your pathfinding, am I correct? You should be aware that having a lot of individual actors quickly becomes pretty taxing on memory. I personally use hierarchical instanced static meshes, though whether or not this is necessary depends on how large you want your levels to be. Note that if you do so you cannot get the location of each tile quite as simply and would need to either use invisible actors (as Ian Shadden does) or getting their locations using tracing or other methods and storing them in a vector array (like I do).
Oh cool! I watched some of your videos before I think, looks cool!
Now that you explain it, it’s true that I could assign the parent tiles already during the getRange function. However, for the AI, I need one single path to their target and then see how many tiles of that path they can move. So for the AI an A* function seems more logical as there is only one path. Or at least one for each potential target unit.
Yes, my tiles are each an actor bp. What part exactly is taxing? The actors themself or the static mesh components of the actors?
Thanks you for the help and information Monokkel! I’ll analyse your comments, do some tests and decide what things I should change this weekend!
You are already pointing out why you might not want to use A* for even the AI. If you want to have a good and efficient artificial intelligence the AI unit should know of all units and tiles it can reach so that it can decide between them. Also, for maps and move ranges of the sizes you use in your screenshots A* might not even be faster than Dijkstra (or especially not a breadth first search), so I see little reason to use it. I started with A* myself, but switched to Dijkstra’s algorithm for the reasons mentioned.
When it comes to your actos the part that is taxing is the meshes. As mentioned Ian Shadden uses hundreds of invisible actors in his TBS example, and it seems very efficient. I personally prefer using an array of locations instead of placing lots of actors, but both solutions have pros and cons.
This weekend I followed some of @Monokkel 's advice and I now use instanced meshes for map creation. This gave me a 10-20fps boost(uncapped). But I still think I can optimize some more especially the meshes outside the intractable level.
Created some c++ classes to reparent my main blueprints. In time I’ll transfer some variables to c++. I do this so I have more freedom in the future in terms of functions. For example: binary save system or a sorting function. Which is way easier to write and read than creating a spagetthi with nodes. (imo)
Also started with the new pathfinding function
Oh right, I also broke everything by changing the name of my c++ classes. It’s been a while since I worked with c++ so it’ll be though in the beginning…
I’m still working on the Dijkstra implementation. In close range I get the desired results, however for the AI it’s not really efficient at the moment…
Yes, it is faster to choose the unit and the tile for the AI(1-2ms) But the algorithm checks all tiles until it has found every enemy unit. So not sure what I do wrong that makes it so slow.
In a way I don’t have that much problem with it as if I were to put the function on another cpu thread I could use something that indicates that the enemy is thinking instead of having a short freeze.
Help would be appreciated as I had hoped I would be further ahead at this point.
Thanks for reading
EDIT: I tried the experimental BP cooker that turns BP’s in c++ and the algorithm ran 2x as fast or faster. So I will definitely rewrite it in C++ if I can.
Ok guys, I’m still working on this!
I rewrote the Dijkstra in C++ and now it’s pretty fast! I made a video with a slightly bigger map and gave the units unlimited movement range to test it.
Some things like movement on slopes broke with the c++ transfer but I was going to change that anyway so I’ll do that later.
Next I’ll focus on the AI a bit more to take attack range into account when searching for a target tile. And some more C++ transfer stuff.
Then I want to either first make it so you can select where the units spawn before the battle starts or redo the map creator to be more user friendly. Because now I just make them in the editor but I can’t see anything because the instanced meshes aren’t spawned in the construction script. So I’d like to make a in-game map creator mainly for myself. But then I also need to figure out how to do binary saving…
Anyway here is the short video
Another update!
After struggling for a few weekends with a binary save system, which finally works, I now created a first rough iteration for a ingame map editor.
Not every button works yet, but I can create some maps. I can easily expand this and my intention is to have the base building element based on this system.
As for now there is still room for a LOT of optimization. But for now this editor is only for me to quickly make maps so I can test things out in the combat gameplay.
The thing with the cliffs you see bug out is something I’ll probably redo from scratch. I was thinking that you select what kind of ground the tile has and that it can automatically detect when it needs to use special cliff tiles.
Yay, forums are back online!
So I was slacking a bit in July, but I made some progress since.
Here are two new videos from last week.
The second video is a recorded AI vs AI battle. Since the AI still needs a lot of tweaking it’s a bit boring to watch but it helps me to find some AI bugs and things I need to change.
Here I also added some quick placeholder sound effects and tried spawning grass on tiles. However the grass takes away 20 fps or more so I need to look into some performance tricks for grass.
I do hope I find some because I really want a lush forest environment in my game.
But you will probably be able to make guesses as I post more.
