Thanks Zeus. 
My blueprints together are 3 MB right now. As for the main path finding graph, it looks like this zoomed out:
Cool, seems relatively manageable. 
Itching to work on my own system!
Indeed, that graph is about the biggest portion of the logic in the plugin so thats fairly manageable.
I’ve started working on an algorithm to do line of sight checking before flagging tiles as attackable (tile is within attack range, the red tiles). Until now I just computed a hollow diamond shape based on the minimum and maximum attack range, overlaid that over all reachable tiles and flagged the tiles within that shape as attackable. In the graph you can see that at the bottom: “Generate all attack offsets” generates the diamond shape and the loop below that marks the overlaid tiles as attackable + some extra stuff. I had already put a “HasLineOfSight” function that until now always returned true. This was so that users can implement it, since there are multiple ways to do line of sight on a grid. Its rather hard as well so I didn’t feel up for it. 
But after thinking about it some I decided to do an implementation myself so that there is line of sight checking out of the box, since hey, I proclaimed you could make Advance Wars like games with this out of the box. So the way I’m going to do line of sight is using a line rastization algorithm from computer graphics: deciding which pixels to color for a line is actually the same as deciding which grid tiles to check for line of sight. I also want to take into account that when a line crosses exactly through a corner of a tile, a special check needs to be done. I’m not actually sure how tile based games usually handle this case, can line of sight pass through the corner of a blocking tile? Would like some thoughts on this. It will be easy to do either case, but I don’t know which one to put in as default. To illustrate the case I’m talking about:
I already implemented the line rasterizing algorithm in C++ using fractions! Here is an example output:
The ? marks show the corner cases. The reason I wanted to do fractions other than it being fancy is that I want to detect those corner cases consistently and not miss them due to rounding errors. I’m pretty proud I got that working, now the fun task of converting it to blueprint…
I have been thinking in hexes for so long now that I actually had to think back half a dozen years to the last time I had played a square based strategy game. 
I think it is really up to the mechanics and theme of the game. If you can move diagonally then probably line of sight, but if you can’t then maybe it is blocked. And you could make it depend on what is in the adjacent tile. Some things could block less than others.
I also had trouble deciding what should be the default option for looking cross corners for my own system. I’ve made both options available for users, as I’ve seen both methods used in different games. Allowing for crossing corners is currently the default option, but it could really have been either way.
Edit: I think it might even be useful to make both options available in the same game. That way you could allow for looking through corners of buildings, but not in between two boxes placed next to each other.
Here’s an image of how it looks in my system with walls blocking (grey) and not blocking (blue) vision past corners.
You’re both right about players perhaps wanting some things to block more than others, for when you have objects that don’t take up the entire tile. Pretty awesome that you can have both types at the same time Monokkel.
I think you have a good point Zeus about being able to move diagonally, you can’t in my case so I’m gonna make corners block by default. Thanks for the input guys.
Zeustiak, your post here saved me lots of hours banging my head against the keyboard! https://answers.unrealengine.com/questions/117669/iteration-limit-setting-broken.html
Apparently I’m reaching iteration limit and UE then complains that my blueprint class has an infinite loop. I think it just means that you reached the iteration limit in one tick, that all while loops together contribute to, or something? The editor then reports it as an infinite loop, which is a ridiculously misleading error IMO.
Update: Got it working! I immediately noticed the performance hit when having abnormally large movement radii or attack ranges. I added a broad pass to optimize it a bit: the line stepping itself is the cost-heavy part, checking a single tile isn’t. So what I’m doing right now is first check all tiles within the rectangle from source tile to target tile. If none of them is blocking, line of sight is guaranteed.
Glad to see my past pain is at least useful for others.
I am not totally sure how they add up all the iterations. I am pretty sure it at least counts everything happening in a single execution line, and may reset every tick, but it can be annoying when it gets in your way when you pretty much want it to run millions or billions of loops. You should have seen me trying to get them to raise the limit past 1 million in the first place. Everyone was like “You must be doing it wrong” or “Why are you putting infinite loops in your blueprints”. Kept having to explain that no, in fact it is on purpose because I need to run this many iterations to craft realistic maps. Then people wanted me to spread it out over the tick as if players want to wait 20 minutes for a map to generate. I will admit, part of my problem is my insistence on keeping everything in a single blueprint, so when these functions are spread out it should be less of a problem, but still. I just wanted a toggle to turn the loop limit police off.
The line of sight stuff looks pretty good. I have to say, I am only vaguely familiar with rasterization, so I don’t fully understand how you are checking line of sight. Seems interesting though, so I will have to do some research when I am working my own system out.
I can imagine people thinking its your fault when you get an error message that says “Infinite loop detected”, must be frustrating if you know better. I see that the guys at Epic ran into issues when increasing the iteration count. I wonder what would happen if they left the limit out in its entirety. You’d get crashes when you actually do have an infinite loop or your call stack doesn’t fit in memory, but what else?
The line of sight checking happens per tile, which is rather painful when you try to envision it. I’m drawing a line from the center of a source tile to the center of a target tile. I recently had an idea for improving it. If I first check the farthest tiles and store the tiles that are passed directly through the center, then only one LOS check has to be done per slope value. So assume the source tile is (0, 0), I should be able to check the tile (4, 2) as part of the LOS check of (8, 4).
Zeus are you familiar with ray casting? What I’m doing right now is actually quite similar to ray casting with axis aligned rectangles. I keep a ray’s status (origin, direction) and update its origin to step from the source tile to the target tile. In each step, I compute which boundary is closer: a horizontal boundary of the grid or a vertical boundary. I step to that boundary, process the tile that is entered next and keep repeating that until the target tile is reached.
I think the telltale sign would be the game hanging, but I don’t see many other non-obvious problems with it. Actually, when you run the standalone game it doesn’t even have the limit. But then you lose the output log and print screen unless there is a way to turn those back on that I don’t know about. All in all, I think they could have a much less intrusive(and useful) way of telling you there is a problem rather than by just shutting you down completely, and then not giving you any useful information at the same time.
I know very little about ray casting. Amit seems to have a pretty good article that covers it though: http://www.redblobgames.com/articles/visibility/
Something I am definitely going to need so I will have to spend some time working on it when I get to that point.
The voting deadline on Trello has passed and while I haven’t heard back from Epic yet I should be good vote-wise. I’ve started on writing a document that will explain usage of the blueprint classes and how to customize them. Is anyone here interested in proof reading that when its done? I could use the help.
I got word that I passed the voting round! Continuing on prepping the user guide.
Here is a video where I demonstrate more clearly various terrain types, and how different units deal with them. I also show that it’s easy to switch characters and toggle the enemy preview.
Are you using A* algoritm? Could this be converted easily to be used non-gridded 2D games for flying monsters like bats that are going towards the player?
Hi Frisco, this is closest to Dijkstra’s algorithm and no heuristics. The implementation is fully optimized for finding all paths within a predetermined movement cost, rather than finding a single path of unknown movement cost. That makes it perfect for turn based strategy games where units usually have a maximum movement range per turn. For real-time games I wouldn’t recommend this, nor for non-grid based games.
Update: Discussion moved to Marketplace thread