Optimizing efficiency and graph sizes

Beginner Questions
1

I am making an RTS game, and use this as my pathfinding solution.
My current need considerations involve:

  1. A lot of units possible, a few thousand planned (maybe a few hundred)

  2. Huge graph sizes for an expansive area

I tried to use the example script for the minebot (and modifying it for my needs) and saw a notice saying it was not optimal and is bad on performance for large unit numbers. How can this be improved? I essentially want all the features that the minebot has (plus a few more that i’ll code) and want efficiency (as this will be for mobile). Is there an example of why the following script is NOT efficient and how it can be improved?

http://arongranberg.com/astar/docs/class_a_i_path.php#details

I will need an area a few thousand units wide for the play area. My options for graphs are this:

  1. Build one giant graph (few dynamic avoidance obstacles needed after runtime initialization)
  2. Build a number of graphs that handle a smaller area (and then enable/disable ones as needed)

The problem with 1 is obviously if this will cause huge memory problems in mobile devices (ipad 3, or tegra 3 devices and up) and wether the units can handle this graph well.
The problem with 2 is that graphs will need to be loaded/unloaded, and could cause performance issues if units keep going back and forth between graphs. I will potentially need ALL graphs enabled, and will run into problems discussed for number 1.

Which method is better with mobile in mind? I’m thinking number one, as it only loads like 2mb of data for the graph, and has less memory load times for paging in/out graph chunks.

2

Good points. I’ll try and switch to a raycast graph.

When unity made that, what was their baseline specs to determine 100,000 triangles?
I’m curious, because I’ve seen mobile (ios specifically) handle some crazy games on an ipad3.

3

Well, I definitely know that on PC you should not push more than a few million tris and 500*2000 is already a million tris.

Apparently 10 million is too much even with everything batched into as few draw calls as possible, very simple shaders and only a single model: https://www.youtube.com/watch?v=KHEmpXkcuzs

4

Hmm ok. Thanks for the video and such! Hmm. 10mil triangles with 6-8 fps? That’s pretty decent (but definitely not what you want as a game).

Thanks for taking the time. :slight_smile:

5

Hi

I think you are overestimating what mobile processors can do. Small stuff adds up if you do it thousands of times per frame.

A recast graph is a navmesh based graph. It will use less memory than a grid graph and be faster to search.

…500 triangles… You know 500*1000 is 500000, the unity guidelines for mobile is “not more than 100000”.

Yes, the local avoidance would probably be fast enough unless all the ships are very densely packed.

6

Well, The ipad3 seems to handle calculations decently as apps are compiled to native code.

I don’t need perfect movement, just movement that mimics space ships as envisioned by sci fi.

I ditched the character controller and just use a transform move, and then rotate based on variable speeds to the target waypoint.

My game uses a flat surface, so raycasting is not needed (all units will be on the same plane, same y height).

I will attempt to batch textures and such to eliminate a bunch of drawcalls, but i do see where i need a drawcall for each unit. Each unit is a small mesh, around 500triangles each.

Is a tiled raycast graph a navmesh? If so, is a grid graph worse? Plus, about how many navmesh “cuttings” can I do in 1 second (guessing to be about 10x10 units wide) before it is a huge drag on performance?

Plus, i saw the local avoidance is back, is that optimized for mobile? (if not, i can just have my units go through each other for movement for now).

Thanks for replying, I love your pathfinding solution :slight_smile:

7

Hi

  1. Are you trying to get a few thousand agents working on mobile… I think you will have to lower your expectations a bit. Just rendering a few thousand agents on mobile will require a few thousand drawcalls (unless they are basically just single quads or something) which is already too much for mobile.
    Along with 2, this will be close to impossible on mobile.

Assuming it would work, this is what you would do for best performance.

You would use a single large graph. The best graph would be a tiled recast graph since it can handle huge areas easily. The few dynamic obstacles would be handled using navmesh cutting (see docs).

The AIPath script is not efficient because it uses a lot of math to give you smooth movement if you would want several thousand agents, you would need to use much simpler calculations to be able to do them all. The minebot AI uses a character controller which are notoriously bad for performance, especially when they collide with other agents. If you want a few thousand agents, you will need to only use a single raycast dowards to check for the terrain height below it, more than that and it will be too slow.