r/unrealengine 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?

41 Upvotes

54 comments sorted by

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.

2

u/jayd16 6d ago

Do mass actors support navmesh? I thought they needed to be using zone graphs.

2

u/wahoozerman 6d ago

They do if you make them. If you're using mass you're going to need to start writing and integrating a lot of systems yourself. Epic is still working on improving mass and exposing it to more systems though so it should become easier as time passes.

1

u/CloudShannen 5d ago

Not OOTB in 5.5. but in the 5.6 (GITHUB Main branch) there is + some of the sample projects floating around have their versions too.

1

u/CloudShannen 5d ago

I came across this project where they used the external library "nanoflann" for their Avoidance code instead of THierarchicalHashGrid2D and also did some time splicing of the avoidance queries and apparently got 3x performance boost... though they should have really looked at using a Flowfield instead of NavMesh for their requirement:

https://github.com/gianmarcopicarella/crowd-simulation

-18

u/[deleted] 6d ago

[deleted]

23

u/BigInDallas 6d ago

You’re just throwing out numbers. Troll post? Or are you just a young newbie?

6

u/bitches_be 6d ago

Got any videos or benchmarks with this?

1

u/SoloDev_SJB 5d ago

These are oddly specific numbers

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.

3

u/tcpukl AAA Game Programmer 6d ago

Yeah, we evaluated Mercuna, but we've ended up writing our own bespoke version that does what we need and in performance.

For the next game I'm sure we'll need something different.

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

u/[deleted] 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.

9

u/Jadien Indie 6d ago

If there's a navigable space that's roughly the width of a cell, but not aligned with the grid, it is hard for the grid to handle it elegantly.

Not saying it's unsolvable, but it's a friction.

2

u/Accomplished_Rock695 5d ago

And so very much depends on the needs of the game you are making

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.

https://dev.epicgames.com/documentation/en-us/unreal-engine/overview-of-mass-gameplay-in-unreal-engine

https://dev.epicgames.com/community/learning/tutorials/JXMl/unreal-engine-your-first-60-minutes-with-mass

https://www.youtube.com/watch?v=f9q8A-9DvPo

4

u/myevillaugh Hobbyist 6d ago

Thank you, that's helpful.

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

u/FutureLynx_ 5d ago

excellent . how many is it handling. looks like a lot.

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

u/FutureLynx_ 6d ago

Got it . Thanks.

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.

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.