The long road to success
Well . . . This past month was quite the interesting: First, shortly after my last entry, I discovered that by removing a chuck of the climbing system, it made it work much better and faster. So that was a thing. However, the elephant in the room was the idea of creating an alternative/better solution for the bog-standard, somewhat clunky Top-Down controller within Unreal. The project needed a much more responsive, snappier controller, otherwise I'd go bonkers, whilst testing the game (for example: it was really challenging to line up your character to face a wall, or even get close to it). Boy-o-boy, I was in for a treat. Not the kind you'd–or even I–except(ed)!
On one hand, I perfectly knew how difficult this would be. And as such, I was worried that this whole idea would end up in the dumps. Have to admit, at some points, I played with the idea of just switching to manual input, and be done with it. But by doing that, it would've ruined the core aspect of the game, and made it into a more arcade-esk cop-out; which was a no-bueno in this case. So naturally, I marched onwards and hit the web, to find out if I could find something useful. Have to say, didn't find much that was not C++ related. Which bummed me out big time. And to make matters worse, I only managed to find some vague pre-made samples/show-offs, which were unnecessarily hard to comprehend, due to the fact that there was no blueprint code shown, or if were than was super slow and immensely complex. But, after spending days on figuring out a solution to my problem (after throwing away the idea of ever using Navmesh for my purposes), I landed on a semi-neat solution. And what a huge mistake that was–sort of.
The idea of goal based pathfinding
Yep. You heard it. Goal-based-pathfinding. The tech-demo I saw convinced me to use this on a smaller scale, and thought to give it a try, with some added twists. First, the challenge was that I could only use my own code, which was quite easy, as I had no prior knowledge of how other systems worked/were implemented (I only later discovered the Strategy Sample, which I couldn't understand). The second flip came in the form of a "What if I turn this grid into a dynamic one?".
What I meant by that was the following: There would be an active grid, following the player, which would solve all the math on the fly, and calculate your desired path. This combined with the fact that a goal based system is much smarter than a simple Move-to-location logic (e.g., it is capable of finding out its way from a maze), I thought I was onto something.
By doing this, there would be no need for predefined zones (at least not for now) of what is traversable and what isn't (to put it simply). This was made possible by using traces, to check for collision, on each tile. But more of that later.
Iterations of the same thing
To test my theory out, I set down and spent a week or two, going back and forth with my enormous node design. Which I don't wish to share, as it became a spaghetti-of-a-mess, by the time I made it work.
So to scale down the project, and figure out the interior logic of how a system would be built up, I made a smaller version of it. A 9x9 grid, that reacted when I placed in an obstacle in the editor in its way, and would block or allow the player to move through that area. However, I underestimated how difficult that seemingly novel idea of "Each tile is set to one greater than the previous one" was; as seen in that video. . .
For one, I had to teach the system to look for obstacles, and with each step, look around, and adjust the global array I set up for the pathfinding. It goes without saying that I spent over a week just figuring out how in a world I can do this all together. Like, there were times that the tiles would not respond, or be inaccurately labeled (like miss counting, etc.). It was quite the headache, but in the end I managed to pull it off; after bashing my head into the wall a couple of times of course.
O and almost forgot to mention that in some ways, turning an array of locations into movement was more difficult than I ever hoped it would: The issue of feeding a data stream was a funny side trip! But that being said, I had something that looked like this:
Link in case missing: https://youtu.be/OTr7lhffEb4
Making it (not) work
There was a big problem with the video above: it was not automated. More like manually pre-calculated (as it took me some time to figure out the details). So the first thing was to make the entire thing do the math on its own. Hence came the use of arrays. And the problems that come with them. . .
When you introduce an array, you have to include a loop. When you include a loop, things will start to crash. A lot. And I mean like every two seconds. Sometimes it was so bad, that Unreal just crashed to my desktop, and wanted me to send a bug report to the HQ. Yay!
And the bug-hunting became more laborious, after each crash resulted in the same error message: "Found infinite loop". Thanks. Now I know what and where the problem is! However, whilst fighting with the editor, I also discovered that my collision system suffered another major, more threatening issue: it wasn't scalable at all (used box collision objects), and wouldn't even come close to match the screen space, you otherwise would've seen at any given point. Cool, so this idea was abandoned shortly after that. Then there was another issue, which I couldn't figure out for the longest. . .
Mo' ideas, mo' problems
On paper this should've worked. Seen it work elsewhere, but it was just not there yet. Sometimes it showed some great progress, but in others, it would quickly fall into chaos. Don't even remember how many times the code was changed, during this period. Eventually, it was time for me to give up with this idea; as the more research I did, the more clear it became that this just wasn't meant to be coded in blueprint. This whole idea of a goal based, dynamic system was doomed to fail from the beginning (which had height, and depth perception as well, just to make it that much cooler)!
The rise of the A*
Again, was reaching the point of resorting to my quick solution (manual input), when I came across A*. It required a similar approach/logic to what I had before (like the box method of looking around tiles), so implementing it was rather quick and easy (as I could build upon my previous foundings). This also meant that I had to fundamentally change how the math worked, as there was "less" of a need to pre-calculate the entire path in one go. And that the individual tiles themselves weren't smart anymore.
Link in case broken: https://youtu.be/fTSqX3bRonc
That being said, there were other limitations that hindered production: The look up time was horrible. You can tell from the video from above: It takes seconds for it to load and calculate a path. Oh and I just remembered to tell that I haven't used any pre-made grid (mesh instance) at any point. That would've added another layer of lag to this hot pile of ****.
Why not ditch everything, and calculate on the fly (in a different way)?
And because I was forced to ditch my box collision grid idea (from previous attempts), was left with one choice: to use a pseudo grid instead! Which meant that the "grid" only existed in a HUGE array. And this was what ultimately caused another pile of massive lag, when I first tried to use A*. It was a tough lesson to learn, but now I understood that Unreal, generally speaking (without implementing counter measures to stop loops from happening, or unnecessary look ups to happen; which I've no idea how to do), absolutely hates large arrays. And by large I mean over a hundred. It's just not optimized to be used in cases like this (as a matrix per say).
Then I had this crazy eureka moment of "Let's ditch everything, and keep only the essential". That meant throwing out the entire pre-made grid, and technically calculate a path, by tile, on the go. Which seemed crazy, and still does. But for some reason, it worked. So much in fact that it blew my mind, how fast it was. And. And! The fact that the code now was so small, it could've passed for a simple Print-to-screen node. No kidding!
Link in case broken: https://youtu.be/RT8F8zN-Kdc
Final steps
Now, the only thing was left to do, is to finally make our character to move. And it moves so fast that I had to lower the speed of which the game moved the mesh around, in order to make it more believable. See the proof below! Obviously, there's still a lot more to do with this system, as it is only capable of moving in two dimensions (and is a bit rough on the edges, and can only move in sight, that being said, the fact that it barely uses any code at all, and is entirely custom built, makes it the more impressive IMHO. as there's no grid per say, and makes me that more proud), but that is something to be done at a later stage. As I reached my goal of coming up with an alternative (better?) way, to move my puny-little imagination on the screen. . .
Link in case broken: https://youtu.be/hiQ9Olw7wns
