Having trouble understanding what graph type(s) to use?

I’m implementing a 3D physics-based game in which users can create custom characters with all differenct sizes. Physics properties may also be different for every character as well (acceleration may be different depending on how they built their character, for instance. Additionally, acceleration in the local forward direction might be different than backwards).

Properties of an agent:

  1. Dynamic size
  2. Dynamic speed/turn rate/acceleration
  3. Can move in all directions (not limited to XZ movement plane)

Users will control units to attack ‘bases’ that have similar properties to that described above. In theory, units can move throughout and around the bases by flying around. However, I need the units defending the base to move around this dynamic environment without running into the base (and ideally without running into eachother).

Properties of a base:

  1. Made up of many objects connected together which colliders.
  2. Objects that make up a base are fully destructible (and should open up pathfinding when destroyed).
  3. There may be many ‘holes’ of different sizes throughout bases that units could fly though.
  4. There may be open spaces. Estimating about 75% of a base would be open space, although this isn’t guaranteed.

I’ve taken a few stabs at implementing pathfinding in the past but failed. Dynamic agent sizes, dynamic agent speed/acceleration, dynamic environment and the fact of it being 3D are all issues I had run into, causing me to sideline the pathfinding features. After looking through the graph types, it isn’t clear to me what I should use for AI controlled movement of units through the bases.


  1. Do I need 1 graph per agent size? (This could be an issue due to sheer amount of agents.)
  2. What type of graph do you recommend using for this situation?
  3. Any other advice and/or gotchas that you can think of?

Any help would be greatly appreciated!


Is this full 3D in the sense that agents can move around in the air like birds?

That is correct, they are flying around in the empty spaces, provided the open airways are large enough for the agent.

My current approach (since posting this forum question) is to create a point graph with a custom generator that essentially ‘rasterizes’ a Bounds object. This is generated by performing uniformly distributed Physics.CheckSphere() calls across the Bounds to generate the valid nodes and then subsequently using the PointGraph’s original PointKDTree to generate the valid connections based on maxDistance. Unsurprisingly, I’m running into some issues with the sheer amount of nodes for the same reasons the grid graph is inefficient (From GridGraph Desc: “It is not particularly good from a performance and memory point of view at handling large worlds with large open spaces however as it represents all regions with the same node density regardless of if they need that detail or not.”).