Generic Advice for best practice for my particular Large World Game (huge tile based maps)?

I will be brief, so ask if I need to give additional details. I am not asking for hand holding - just what components I should look into, vague structure of how to handle things, and simple links or answers like “Try looking at X and Y features.”

I’ve went through some tuts and setup things to work well with a single room (1 tile) but would like to be ready for my larger maps. Make sure I’m in the right direction.

Grid Graphs seem great, and unless I’m mistaken they are also the best choice for me.

Logically, I figured it would be most efficient to have a grid graph for each individual tile, and only update a single tile when a new obstacle is placed on it (ex. Wall spawns, grabs its nearby tiles, and updates them.) This way I am not updating a massive 1000x1000 map anytime a 42x42 section or two needs updated.

However I read in another thread that I should only have 1 graph.

I would prefer to just load the grid graph & not have to worry about more complex logic like loading/unloading sections, unless I have to.

I also noticed grid graph baking is so fast in 0-1ms, I thought of just baking a new grid graph anytime the player moves in a straight line through an obstacle. (raycast straight line, and create graph if ray passes through obstacle). But I may be misunderstanding the debug log A*PP reports in #milliseconds. Performance (not hitching) is vital after the level loads. Input lag (calculating path) shouldn’t be a problem.

I also read an interesting solution here ‘Grid one moves with the player’ and thought this might be simpler? A grid for each PC / NPC? Rescan constantly?


Details

My game is a 2D game in a 3D world, on xz plane. Y is ALWAYS set to 0. No height is ever used. Sprites billboarded to screen, but everything is 3D. I don’t use meshes, just SpriteRenderers, but I do use MeshColliders and PrimitiveColliders.

Performance: My game is PC only, so as long as A* PP doesn’t take hundreds of MB’s, I should be fine. My game is not seamless, so the player loads into each location. This gives me plenty of time to bake navigation on load. This also means the largest location is a single tilemap.

I have two types of game locations. Very large procedurally generated tilemaps, and very small handcrafted locations. I figure the latter will be easy, so I am mostly concerned with the large procedural tilemaps.

How Large: Each tilemap has a size of around 25x25 tiles, with each tile being quite large - 2560x2560 pixels. So each location is at maximum 64k pixels by 64k pixels or units (Unity is set to 1 PixelPerUnit.)

A tile is the ground. A walkable square.
Using a grid graph on a single tile, I found a node size of 60 to work great.
A single Tile has a grid graph size of 42x42 (size 60)
So my maps are around 1050x1050 nodes (size 60)

I do not know if I will ever need to increase the tile size beyond 25x25, but may need to. So may need more than 1k x 1k nodes. Max I ever see using though is double 2k x 2k nodes @ 60. As a side note, I would like to explain to others in a future tutorial on huge open worlds how they can handle things, if I just need an extra step.

USAGE: Very simple. Click-to-move pathfinding for PlayerCharacter or NPC AI (Vector3 position), moving around obstacles (Trees, Bushes, Crates) so simple obstacle avoidance with straight lines otherwise. I thought of not even using pathfinding system, since I mostly just need obstacle avoidance, NPC/PC interaction/avoidance, and preventing out of bounds (off-tile) movement…but would like the player to be able to navigate a long way across fences if the path is within screen view. Although that is rare.

Currently I am using RaycastSmooth to get smooth straight lines when no obstacles are present, combined with SimpleSmooth to have a much smoother obstacle avoidance. Works really well with both on with a Seeker.

1 Like

Hi

Since you only need very short distance pathfinding I would recommend the ProceduralGridMover component.
You can find an example of it in the example scene called “Procedural”.
How it works is that it tracks a single object’s position and try to move a grid graph so that the object is never further than a specified distance from the center of the grid graph. It is smart about which nodes it updates so the overhead is much smaller than if you would recalculate the entire graph.

The ProceduralGridMover component will be too slow if you need a large or a too high resolution graph, but for your use case I think it will work really well.

Wow, I looked at that component & the example, and it looks like this is exactly the component I need! I will barely even need much of a grid graph size. This is so spectacular!

Thank you Aron. A* PP was so easy to understand and setup, it took me about 1 hour what Unity NavMesh took me 20 hours. I tried Apex Path asset before, and it doesn’t even have any written documentation (plus is so difficult to learn & needlessly convoluted).

A* PP is perfect. So well documented. And most of all so incredibly performant. Even better, all these scripts that come with it give me everything I need automatically. I couldn’t ask for a better asset.

I notice the ProceduralGridMover was written for a single individual & single graph.

This works perfectly for my PlayerCharacter (PC), but I wanted to ask what the best practice may be for giving my NPC’s navigation.

Since my NPC’s will also need their own grid graph to navigate, in addition to my PC, should I still use the ProceduralGridMover component for the NPC’s?

Should I be using a unique grid graph for each individual NPC? (multiple grid graphs)

While I’m not entirely sure how many NPC’s will be active at any one time, they won’t need to update their grid graphs very often, their grid graphs can have much bigger nodes or be smaller, etc. I should be able to get away with the performance hit even with a lot of them walking around. Maybe at most have a better (more accurate) grid graph when chasing the player, but otherwise use a very very simple one for movement?

NPC AI will vary, but I was thinking it would probably be best to just have them head in a direction & do a small & simple grid graph for obstacle avoidance along the way. However I could also do one really large 1k x 1k grid graph for the entire location (baking it on load) but have the nodes very large. The idea being to have a very broad path to go to long distance locations when wandering or just moving to/from Vector3 position1 & position2. (A bee wandering around until it’s done & then getting a path to return to its nest, a NPC spawned at the beginning of a road and moving to the end of said road along a path, etc.)

For calculating the path though, I don’t know the performance cost for huge grid graphs (1k x 1k). If it’s much more efficient, I can just have the NPC head in the direction of a position using BehaviorDesigner AI, and just use their own small personal grid (like the PC) to avoid obstacles along the way.

I’m not sure how this will work if I have things which block paths though, like bridges in the middle of the map (the only way to cross). Although every bridge/river/whatever will have a road going through it (most likely). So as long as the NPC can find a road, it can find its path through.

One last thing: I will have roads which allow for faster movement, for these NPC’s to travel on. Depending on how I do NPC pathfinding, then I’m thinking that having the AI to travel down the roads should be different. If the NPC have a short grid graph like the PC, then they’ll just have an AI Behaviour to walk towards the road if it’s in a certain distance & then follow the road’s prebaked path. If the entire location has a 1k x 1k node grid graph, then I’ll have road nodes have a lower movement cost. If any of that sounds inefficient/bad, please let me know.

Hi

Ah, you need multiple characters. That is significantly different.
So you could use multiple grid graphs around each character, however it would quickly become too slow.

As game developers we can often cheat in various ways. One way that may or may not work for your game is to simply not use pathfinding when the characters are not close to the player. So if the character is far away from the player you just move the character in a straight line to the target, however as soon as the character is within the range of the grid graph around the player it will be snapped to the grid graph and start to use that for movement. If you have an open environment the player will most likely not notice at all and it will be very fast.

Another approach you could use is to build a very coarse point graph and use that for rough navigation when outside the range of the player (see https://arongranberg.com/astar/documentation/dev_4_1_6_17dee0ac/writing-graph-generators.php, but often it is easier to just use the AddNode method on the PointGraph class). If you can use this depends on the way you generate your map, some procedural generation methods can very easily generate this kind of graph.

This is a great tip, thank you.

I might be able to do this by itself, or if not then just combine it with extremely simple straight-line raycast checks to confirm it’s a valid straight-line path (if raycast goes through a major landmark like a river or wall, grab the nearest precalculated road path (never blocked) & travel that way - straight lines but slightly diverted straight lines, like a V path.) and otherwise just ignore all obstacles & walk through them because it really won’t matter since the player won’t ever see them.

If all else fails, I can check the last solution, but that really does sound like it will work fantastic to just ignore obstacles for my NPC’s outside the player’s view!

Thanks! The tips you have to avoid pathfinding entirely work really well when figuring out how to handle a game’s navigation system.