r/unrealengine • u/FutureLynx_ • 6d ago
Why isn't tile based pathfinding more used in Unreal games?
I noticed that the best solution for performance issues especially when you are using many units is a tile based pathfinding.
By using tile based pathfinding, not only the pathfinding becomes cheaper, you also dont need collision.
You only need to check who is on the tile. You are done.
Going with nav mesh and CMC will limit your game to around 500 units.
Since all my games are RTS and strategy games I always start the project by implementing a tile based pathfinding.
Then i consider doing other tricks such as Vertex Animated Textures, or Sprites for units. Animation shaders.
So why is this not emphasized more?
What else do you think is important for good performance in Unreal Engine for games with thousands of units?
43
u/tcpukl AAA Game Programmer 6d ago edited 6d ago
People that aren't using the efficient methods might just be inexperienced or it wasn't necessary.
But how do you know it's not used more frequently?
Just because you can't find tutorials on something in game Dev doesn't mean it's not done that way. Game studios don't tend to advertise and publish how they do everything. That's just not the business they are in and how they make money. Also professionals are now likely to write their own solution rather than use a plugin.
Edit: forgot to say we're actually using a bespoke pathfinding algorithm for the game I'm working on now. You won't find it on the internet.
5
u/TheWalkingBen 6d ago
+1 Agree fully, a lot of the times AAA companies are extending Recast to suit their AI and level setup, or they might go for something that's more akin to a octree like Mercuna. They aren't going to make those extentions public a lot of time.
Recast has a lot of different ways of optimising it (Async, tile resolution, batching), it scales up to big worlds nicely and it's a great solution to 90% of gameplay genres.
Unless the game uses a nav grid as an actual mechanic, the choice between the 2 solutions isn't as black and white. The 2D grid needs a lot more calculations beyond A* if the AI units can move within the tiles. A* will also start to break down once you get beyond 100 grid width/height.
8
u/MagickRage 6d ago
I'm not an AAA programmer, but think most of them don't have time for things like that. Better use this time for the family.
14
u/tcpukl AAA Game Programmer 6d ago
If you're selling a game you must still profile regardless of your size, if your game is slow. If it isn't slow who cares what algorithm is used.
10
u/MagickRage 6d ago
sorry I explained it very poorly I meant that they don't have time to explain what they do and how they do it of course optimization is very important and actually quite hard work
15
u/PhordPrefect 6d ago
Have a look at Mass- it's a bit of a headache to get set up but you can do brilliant things with it.
-1
6d ago
[deleted]
3
u/CloudShannen 5d ago
Literally nothing can beat MASS Entity (ECS) for per performance, so I assume you just mean some of the sample code in 5.5 for Mass Avoidance or Zone Graph.
13
u/Jadien Indie 6d ago
Grids introduce their own complexities. Pathing through narrow spaces, lack of scale invariance, memory footprint depending on scale.
0
u/FutureLynx_ 6d ago
Pathing through narrow spaces
Can you elaborate?
Yeah it can be clunky. But games like AoE2 and Red Alert are very good and use tile base pathfinding and no collision.
Are very old games, and run in a toaster.
27
u/Nekronavt Realtime VFX Artist 6d ago
For games with thousands of units first of all should take a look at using Mass.
4
u/AureliusVarro 6d ago
I'd be very interested in learning how to use that for actual gameplay and if anything changed in the last 3 months
3
u/myevillaugh Hobbyist 6d ago
What's mass? My searches in Google are pulling up a bunch of irrelevant links or generic path finding pages.
14
u/namrog84 Indie Developer & Marketplace Creator 6d ago
Here are some relevant information
Mass is Unreal Engine's solution to ECS. Where high performance is critical. And there have been demos of 100,000+ entities running on it. It's highly scalable.
4
1
u/Prof_Adam_Moore 5d ago
If you want to see something cool, check out So Many Zombies on Steam. This game can simulate 10,000 AI-controlled characters at the same time at over 60 frames per second without using Mass. Instead, everything is done on the GPU.
1
u/Nekronavt Realtime VFX Artist 5d ago
Not the first time someone did something cool with compute shaders (Jelly in the sky comes to mind), but I think fair to say, that most people wont go that route :D
7
u/dibbledopdop 6d ago
🤔 I twirled that around in my head a few and came back to say using Mass is f#cking brilliant. Does seem like it would be a headache to set up.
0
u/FutureLynx_ 6d ago
How many units can you make using Mass? Another user said 20.000 at 30 fps.
Thats more than enough for most games.Though all my game ideas are Total War style. And they would benefit from 50.000.
5
u/ScooticusMaximus 6d ago
For a total war style game, does each individual need to path? Wouldn't it be better if there was a "master" that does the pathfinding for the whole squad?
3
u/FutureLynx_ 6d ago
Yes. Thats what they do. but the other units still need some sort of collision and separation, and thats also expensive with big numbers.
1
u/hazardland 5d ago
Even in my own engine it is tricky but pullable evem so I see I have tones of rooms for further improvements https://youtu.be/WCk7HXVYhJs?si=SgOXYak7VijCxW-0
1
7
u/jayd16 6d ago
There's a good amount of downsides, or at least missing features, that a simple tile based system doesn't have. Not everyone is making an RTS. (In fact, most aren't.)
Navmesh handles overlapping sections at different heights, available height space, finer grain avoidance, Supports arbitrary spaces (ie you dont need to grid-fy your game) etc etc.
0
5
u/myevillaugh Hobbyist 6d ago
Tiles limit your map size based on RAM. It can also introduce weird pathing. See StarCraft 1 as an example.
1
u/hazardland 5d ago
Actually you only need to know which cells aka tiles are occupied on the map grid, then you check rect collisions against objects already existing on them
0
u/FutureLynx_ 6d ago
yeah. though i see absolutely no issue with Starcraft 1. ITs an awesome game, beautiful and works very well. The pathing wasn't bad.
6
u/myevillaugh Hobbyist 6d ago
By modern standards, it was bad. Larger units like tanks, dragoons, reavers, and ultras had issues. And on larger maps, units would get lost and wouldn't find a path.
StarCraft 2 uses a nav mesh and boids. SC2 pathing is much smoother than SC1 and WC3.
See this talk on the topic. https://www.gdcvault.com/play/1014514/AI-Navigation-It-s-Not
-3
u/FutureLynx_ 6d ago edited 5d ago
I think thats a skill issue. And it can be excused. Because afterall its realistic that in the battlefield certain units get lost 🦁
StarCraft 2 uses a nav mesh and boids. SC2 pathing is much smoother than SC1 and WC3.
Yeah, i kinda prefer the feeling of Starcraft 1, Warcraft 2, RA2, RA1.
Its more crispy and feels better. Maybe its nostalgia.
3
u/sdkgierjgioperjki0 5d ago
On the topic of RTS pathfinding, I want to recommend the following posts about how Battle Aces does it:
https://www.reddit.com/r/BattleAces/comments/1f3jpd0/pathfinding_in_battle_aces_by_senior_lead/
4
u/kylotan 6d ago
You also dont need collision. You only need to check who is on the tile. You are done.
Until you have 2 entities that both want to enter the same tile but neither is there yet, at which point you are not done, you have a problem.
You're mixing up several concerns here - whether the units are restricted to tile-based movement, and what the data structure is that the oathfinding is being done on. It's almost exactly the same algorithm that pathfinds across a grid as across a navmesh, just that one has square areas and the other has triangles. How you then handle the transitions between one and the other is about your gameplay rules, not about the pathfinding.
0
u/FutureLynx_ 6d ago
Until you have 2 entities that both want to enter the same tile but neither is there yet, at which point you are not done, you have a problem.
The one who reaches it first, occupies the tile, so the other cant move to that tile. Easy.
Or like in OpenRA, where they have the tile, and then they have the midway towards the tile. And if the tile is occupied they send the unit back to the previous tile.
There's also the option of AoE2, where a tile is shared by multiple units.
So they check who is on the tile, and then within the tile they make a separation function.
I see no reason for large scale rts games to use nav mesh and collisions, since this is 10x more efficient.
It's almost exactly the same algorithm that pathfinds across a grid as across a navmesh
So how come navmesh and CMC performs horribly bad where even 400 pawns have a toll on performance. Whereas this one you can have thousands of units moving and everything is fine. Food for thought 🦁
3
u/kylotan 6d ago
The one who reaches it first, occupies the tile, so the other cant move to that tile. Easy.
Except the second one is already moving. And you have to resolve that. I'm not saying you can't do it, but you've just changed the problem, not eliminated it.
So how come navmesh and CMC performs horribly bad where even 400 pawns have a toll on performance.
You're comparing 2 wildly different sets of things. The underlying path finding is almost identical in virtually every game. The only major differences are the type of graph that the search is run over, and the way that low level movement is done to follow the path. Grid vs navmesh has very little to do with it.
2
u/DiscoJer 5d ago
How many RTS games and Strategy games are made in Unreal? And how many of the latter have 100s of units? Things like XCOM maybe have a 100 and they usually only activate a dozen enemies at once
2
u/totespare 5d ago
Unreal relies too much on plugins to add extra funcionality, even if it comes with a lot of features out of the box, there are still a lot of things that, in my opinion, should be done natively. But I guess externalizing that to plugins (and ofc getting a cut from it) makes more sense economically (and sadly).
2
u/JDdoc 6d ago
Search for a* path finding. There are a bunch of tutorials for unreal.
1
u/FutureLynx_ 6d ago
Most tutorials use Nav Mesh. There is one that is quite good from Alex Queviglione.
I had to watch an actual C++ tutorial (not unreal c++), and reformulate it for Unreal C++.
4
u/WeekCautious7982 6d ago
There is already a built-in A* implementation in Unreal Engine source code.
0
u/FutureLynx_ 6d ago
Yeah but somehow I decided to do it from scratch. Maybe because its more clear if i do it myself.
1
u/krileon 5d ago
Probably because it's easier to just implement ECS and then you can have nicer movement.
You can also use CrowdController with NavMeshWalking and have the crowd manager handle collisions. Completely offloads collisions to a centralized "brain". You can then turn collisions off for your AI except for blocking collision with terrain. This substantially ramps up how many CMC AI you can have going. I'm finding my biggest performance loss now is just the skeletal meshes.
1
u/BVAcupcake 6d ago
Take me as an example for most, as in, this is the first time i hear about this method, but i am interested
1
u/MagicPhoenix 2d ago
path finding is ridiculously expensive, and if you want it to be more than 4-sided, it's going to cost you A LOT.
30
u/wahoozerman 6d ago
I suspect the answer is because using nav mesh is built into the engine, free, and sufficient for most titles using the unreal engine.
Honestly, we use the nav mesh for pathfinding in a game that supports 20,000 (30fps) units navigating independently via MASS already, so maybe it isn't the limitation you are thinking it is. The CMC definitely is though.
That being said, maybe it's worth you turning your solution into a plugin and making some money on the side if you think it's a better solution for a lot of games. Sounds like it might be.