(Seeking) Understanding for Pathfinding Behavior ("under the hood")

From the Asset Store
Units do not overlap each other and use different ways if there are several free ways.
  • A while back, like, when Ashley first introduced the new Pathfinding behavior (I get chills remembering how awesome this introduction was at the time), I seem to recall the explanation that using too many Pathfinding objects all at once (even worse if the cells used for finding paths along were of different sizes) could eat up a lot of CPU.

    So, what I'm wanting to seek clarification on is how exactly C3 processes each object (rather, each instance of an object). I'm going to try to explain what I THINK I currently understand and then if someone could help me correct my (mis)understanding and/or add some info that could help me better grasp what's going on "under the hood" of this game's engine.

    As I understand it, each object with Pathfinding generates a grid by which the objects move, via nodes at specific cells. How this is done, I couldn't begin to guess...lots of math. Yes, certainly lots of math.

    I'm going to assume that instances of that object use the same exact grid as a means saving overhead on the CPU. There's no sense in generating a new grid to calculate movement on, I would think. (Unless, for some reason, it's necessary that each instance of each object with Pathfinding needs its own grid?)

    Either way, I think it's safe to say that the more objects with multiple active instances of Pathfinding is going to eat up a lot of CPU simply because of all the demands for calculating the path...especially when the cells are tiny (because that's a lot more precise of movement going on there around objects...it's more cells to account for). And the larger the layout, the larger the grid, the more cells...maaaaaaaaath.

    NOW, I know I'm probably going to need to be corrected on my assumptions above, but this leads me to my questions further on how to try to save on CPU demands when using any amount of Pathfinding.

    1. Does simply having Pathfinding assigned as a behavior to an object (enabled, but not actively being used) cause any considerable demand on CPU? Regardless of the number of instances of an object in the layout?

    2. Would destroying an instance of an object make a difference as soon as it's not needed?

    3. Is a grid generated per object using Pathfinding? Per instance of an object? Or does this grid exist so long as Pathfinding is at all assigned to an object even if it's not used in the project layout?

    I will try to set up my own tests to see what I can figure out, too, but those of you with a greater understanding of how C3 works in the engine, itself, your insight and understanding would be of great value to me. Thanks for your time.

  • FYI the Pathfinding behavior uses the A* pathfinding algorithm on a grid. It's also massively more efficient in the C3 runtime.

    Generally so long as you have a reasonably large cell size and you're not using ridiculously huge layouts, it's pretty fast. The main cases people find it's slow is if they set a tiny cell size like 1x1, which forces the pathfinding algorithm to search through tens of millions of cells, which is really slow. The whole point of using a grid is to massively speed up the search by reducing the amount of searching that needs to be done.

    1. Does simply having Pathfinding assigned as a behavior to an object (enabled, but not actively being used) cause any considerable demand on CPU?

    No. It's only finding a path that uses CPU.

    2. Would destroying an instance of an object make a difference as soon as it's not needed?

    No, because of 1).

    3. Is a grid generated per object using Pathfinding?

    Grids are shared between all instances, but if you change the cell or border size, it has to create a new grid out of necessity. But you should not depend on that, it's designed to share the grid between all instances to make it much more efficient on CPU usage and memory.

  • Ashley Could you explain how to find the optimal cell size?

    For example, in this screenshot the grid size is 32 px, but pathfinding doesn't work unless I set grid size 15 or less. But I'm guessing 15 is not a good choice here and may cause problems on large distances. So what's the best cell size in this case?

    .

  • Pathfinding should work in that case. It's not clear why it doesn't. Did you apply a cell border to make sure blocks don't mark adjecent cells as obstacles?

  • Try Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Try Now Construct 3 users don't see these ads
  • Oh, I completely forgot that I can put negative values in cell border. It works now with cell size=32 and cell border=-1, thank you!

  • Thank you for taking the time and bearing with me, Ashley. I'm very grateful. That should help me keep things manageable.

Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)