A* Pathfinding Project

RTS game pathfinding


#1

Hello,

Bought your asset but now I’m kind of confused because I can’t find anywhere in the documentation very clear explanations on how to achieve this kind of basic use case.
I want units to pathfind around each other. Like if one ranged units stop to shoot, then melee units pathfind around them.
And also, when you order units go to a position I want them to go to that position but not take the same path.

What are the best scripts for this?
Is grid graph best?


#3

Hi

Currently there is no example of this built in to the package. I am however working on a demo for rts functionality that also includes some nicer local avoidance specifically for rts games.

You can find this beta if you go to the download page (https://www.arongranberg.com/astar/download) and click the ‘Show Older Versions’ button and download the RTS beta (note that it requires Unity 2019.1 to run).
Here is a video of how it looks: https://www.youtube.com/watch?v=wBUdMXeeej0&feature=youtu.be

This really depends on what kind of behavior you want. Usually you just want local avoidance for this. If one uses SC2 as an example, that is doable with only local avoidance.

A grid graph is usually pretty good for rts games if you are going to be building buildings and your map is not too large. A recast graph could be an option otherwise.


#5

Thanks I’ll check it out. If it works well I might use the beta branch in my project.


#6

kuva

I downloaded the RTS beta as you suggested but in the example scene all the meshes for the units are missing. It seems they are not included in the package.


#7

Hi

I think that beta version requires a relatively recent version of Unity. Try it with Unity 2019.1. Hopefully it should work better.


#8

Hello Aron!

The behavior shown in your RTS demo is very relevant to the project that I’m currently working on. Do you have an estimate on when these additions will be included as an official release (e.g. non-beta)?

Thank you!


#9

I’ve been using it now and results have been satisfying.
However when there are more units RVOSimulator seems to cause lags spikes.
Any advice on how to optimise the RVOSimulator?


#10

Hi, I’ve been contemplating getting this pathfinding solution for a while now in the hopes to also build an RTS game with it. Seeing this thread gives me hope but I’m just wondering how Pathfinding Project will hold up on extremely large maps with potentially 10,000 units split between 10 players in multiplayer. This is an extreme example but I’m going to be working on something on the scale of Supreme Commander and Total Annihilation and I’m hoping this of all things will handle it.

Total Annihilation is over 20 years old and can handle this amount of pathfinding (10,000+ units) on extremely large maps that are 32,000x32,000 pixels large (the maps are made from 2d image) if you can imagine that scale, in Unity I think this would translate to a pathfinding grid of roughly 2048x2048 unity units.

Is this scale possible? Obviously I’d also like for this game to run at a decent framerate but again this is the most extreme example. :slight_smile:

Thanks,
MattyWS


#11

Hi again, I ended up buying anyway just to profile it and with this RTS test you made I’m a little disappointed by the results though I appreciate that it is still being developed. I waited for a larger number of units to see how it’d cope and by the time I got this many;

The game was at 5fps (my pc is a beast just for the extra info). This isn’t many but I also noticed the fps actually went up when they were moving and went down when they were bunched together. After profiling, it was most definitely the pathfinding causing the fps to be so low.

The units being a little clumsy and trying to clump together might be the reason, they’re constantly fighting for space and not just giving up maybe?

At any rate, would you be able to confirm if this low fps is to be expected? If so I’ll have to move onto another solution for pathfinding but I’ve heard this one is the fasted. :confused:

Thanks,
MattyWS


#12

Hi @MattyWS and @sepnax

Sorry for the late answer. The reason for the late answer is that I have during the last week been experimenting with using the Unity Burst compiler to improve the performance of the local avoidance system and so far it is looking pretty good. I wanted to see what the performance was before I answered. It can now in the most optimal scenarios (i.e. pretty much no overhead, all agents are just rendered as quads in a single mesh, they don’t even have their own GameObjects or pathfinding) handle 20000 agents on my computer at 20 fps (or 120 fps if I restrict the RVO simulation fps and use double buffering, though that has some consequences for the local avoidance quality).
Note that in the RTS beta there is the SC2Avoidance script which currently does some relatively slow stuff and tends to be the slowest part of the simulation. It loops over many nearby agents in order to determine if it should stop or not. This is possible to optimize significantly, but that has not been done yet. This is one of the reasons it is still a beta.

Here is a screenshot of 20000 agents

Note that you should not expect to have anything near 20000 units in the game with RVO as the above scenario was pretty much the ideal case. Even the code for generating the mesh to render the agents had to use the Burst compiler.


A* and the job system
#13

Thanks for the response! This is very promising, 20,000 is above my own extreme case by double so I’m happy to see this. How does this handle on a larger more complex map? I’m willing to compromise map size for performance but I’d still like to have up to 32x32 maps which would be a terrain of 1024x1024 unity units. Is a nav mesh better than a grid for this case?


#14

@aron_granberg
Nice.

I’ve been now using the RTS Game Beta branch.
I literally copied all the components regarding pathfinding from that and have made no changes to the pathfinding, because I want to keep as far away from it as I can :smiley:

However I get this issue that the enemies cannot find a path sometimes in very obvious scenarios.
https://streamable.com/jwdb4
Here the enemies on the left seem unable to path to the guys on the right.
https://i.imgur.com/wQSS8Sf.jpg
This is a screen cap of the nav graph.

Do you have any idea what could be causing that kind of behaviour?
How do you suggest one would go about debugging this?


#15

Sorry for the late answer. I have been traveling and have not been able to answer support requests for some time.

@sepnax
Huh, strange. Are you using the FunnelModifier for your agents?


#16

@aron_granberg
Not that I know of.
Should I?


#17

@sepnax

Unless you are using the RichAI movement script, yes. Though I suppose if you are copying stuff from the RTS branch you are probably using the RichAI movement script…

Do the paths look correct when the units get stuck?


#18

@aron_granberg
They looked incorrect, and after investigating it more I was able to locate the bug in my client code.


#19

Just wanted to let everyone here know that I have uploaded a new beta (4.3) to https://www.arongranberg.com/astar/download which includes the new RVO system with Burst support. I’ve also done some other optimizations to the RTS example.

Let me know if you run into any issues with it.


#20

That upgrade wasnt as painless as I thought it would be.
I got the Unity updated, packet manager packets and assembly definitions compiling.
I realised that you had probably deleted bunch of classes I referenced in some of my client code :grinning:


#21

Most of were just problems with assembly defs but I think SC2Avoidance you really deleted?


#22

Yes. SC2Avoidance was deleted. The logic is built-in to the AIPath/RichAI scripts now.
See https://www.arongranberg.com/astar/documentation/dev_4_3_4_6f357bd7/aibase.html#rvoDensityBehavior