Mini-Scale Pathfinding!

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

1 Like

I’ve found this plugin to be insanely helpful for static maps, the path finding is blazing fast too

edit: after reading more I realized this most likely won’t work for you since your game is an RTS game so your map won’t be static

If your army of mini men are too small you could potentially just scale everything up keeping them still relatively tiny while being big enough for pathfinding :joy:

The way roblox does it is by generating a navigation mesh, which is used to detect which points are “walkable” or not.

If I were you, I would find out some way of generating a representation of the map ahead of time - probably on server start up - and use that pregenerated representation in order to pathfind

Also, take a look at some more modern and efficient approaches to pathfinding - here is one that comes to mind:

Finally, think about trying to group nearby units headed for the same location together. That would drastically reduce your compute time.

1 Like