Hello comrades!
I figured I’d head on over here to ask some questions about the wonderful algorithmic fun-tank we know as pathfinding. Yes, I know that Roblox has created a wonderful service for us to use, but sadly in my case, it isn’t quite… applicable.
Here’s a little video of what I have so far. You can see a little bit of pathfinding action at the end:
RoK with terrain and a floating camera!?!? #Roblox #RobloxDev pic.twitter.com/wbZNtiKC3U
— Xulp (@XulpRBLX) September 22, 2017
Sadly, my army of mini-men doesn’t possess the sheer tallness required by Roblox’s wonderful service, thus I decided to go about solving the problem my own way.
Currently I’m using an A* algorithm, which works well in getting from point A to point B, the problem being that it takes a lot of raycasting and that the client/server has to do a lot of pathfinds, which is of course laggy. Another issue is that targets aren’t always static, which is a big problem that I know that there are multiple ways to deal with, but essentially that just adds to the number of times it needs to recalculate.
To deal with some of the lag, I’m currently using a sort of short-cut method that says if a unit can do a raycast to its target unit, and if nothing’s in the way, walk straight towards it and don’t bother to pathfind. And this is actually built into my pathfinding script too; if a node (I’m currently using a grid with 1x1 cells) can cast a ray to the target, just set the target as the next node so that it avoids some work.
On top of it all, to find if a node is actually traversable, it takes another raycast from the current node to that point. Unfortunately, this isn’t a great solution if there’s no ground to walk on beneath, or if there’s a river in front of you, because this method has no way of detecting that. Plus, obstacles can appear along the way, so the unit has to actively do more raycasting to check for that.
So here comes the real question: Are there any better ways to go about this? And if so, how?
I know that computing paths is going to cause lag regardless, but are there ways to minimize that effect? And is there any other way to minimize the number of pathfinds needed? Also, is there a good way that anybody has in mind to handle long-distance pathfinds, assuming that there are few obstacles and mostly open terrain? Keep in mind that this is for an Age of Empires-like RTS game, so you can image the performance I’m shooting for.
Above all, I am far from an expert on this, so any input or suggestions would be incredibly helpful. I’m not looking for somebody to script me anything or give me code, just some concepts and ideas would be perfect.
Thank you for your help!
~Xulip the Tulip
