Feature Questions Before I Buy

Beginner Questions
#1

Hey Aron, looks like you’ve made a great package here. I’ve read much of the documentation and watched some videos, but I still have a couple questions about my use case before I feel comfortable buying.

For context, I am building a game with essentially identical mechanics to Fallout 4 settlement building:

This means placing arbitrary geometry to construct buildings that NPCs then navigate around and interact with in various ways.

Here are my questions:

1. Can I dynamically recalculate my graph with no main thread stutter?

This page:
https://arongranberg.com/astar/documentation/4_1_11_05f3b7d8/graphupdates.html

says:

You can also recalculate graphs asynchronously (only available in the pro version). This does not guarantee a good frame rate, but you can at least show a loading screen.

Showing a loading screen after the placement of each building part isn’t going to work, it has to be seamless, ie. on a background thread.

Maybe also relevant: it’s possible for the player to click rapidly, eg. if they are placing several floor pieces in succession. Ideally I could detect a recalc in progress and cancel it/restart it if the player lays down parts quickly. Possible?

2. Can new geometry block navigation before it’s baked into the mesh?

Given that it doesn’t stutter the game, as described above, the recalc doesn’t have to be fast at all: when placing a new floor, for example, it’s not important that NPCs be able to navigate onto it right away, they can wait a few seconds, however they must at least avoid the geometry right away.

Eg. if they are already walking a path that went through the area that I just placed a block in, it’ll have to avoid that obstacle even before it gets baked into the walkability graph.

I assume this is easy, but it would be a deal breaker if it were somehow not possible.

3. How smooth will NPC interactions with moveable parts be? (Eg. Elevators, Ziplines, Conveyors)

This is less of a dealbreaker issue, and more just trying to understand how deep in the weeds I’m getting with this.

I’ve seen a couple discussions / videos from past years (both from you and others) with elevators, and they all without fail mention being “hacky”, so I’m wondering if something cleaner has been built in the mean time.

This is a scenario where the elevators are realistic in the sense that an agent would approach them, hit the button, wait for the platform to arrive and doors to open, walk onto the platform, ride the platform, wait for the doors to open, then continue their path on the new floor. I’m sure I can get a script working to do all this, I’m just checking if there is already a clean way built to handle this?

4. What should I be asking?

Numbers 1 and 2 are the only potential deal breakers I know of–the rest of the features cover my scenarios. Given the context you have, can you think of something else I should be aware before buying?

Thanks a lot for your help!

#2

Hi

  1. You can recalculate recast tiles on a separate thread. The drawback is that pathfinding is paused while this happens (looking at the video, I would expect it to recalculate in less than a second). This is actually more of an architectural constraint than a technical one (i.e pathfinding could technically be happening on the graph right up until the last step in the recalculation, however right now pathfinding is always paused for the whole duration of the recalculation).
    Take a look at https://arongranberg.com/astar/docs/graph-updates.php

The quote that you are referring to is for recalculating the whole graph, which you most likely do not want to do. Recast graphs are tiled, and each tile can be recalculated individually.

I am guessing that you will need to add geometry that an agent can use, not just remove geometry (i.e an obstacle).
If you just have obstacles, then navmesh cutting can solve that very efficiently (see https://arongranberg.com/astar/documentation/dev_4_1_19_3b555458/navmeshcutting.html).

Another approach is to use a layered grid graph. They are much faster to update, however they will only work if you world is not too large. I’m not sure what world size or resolution your game will require, but it may be useful to look into.

I made a video of me just moving some objects around in a simple scene while dynamically recalculating a recast graph as soon as it detected that the object had moved a significant distance.

This worked quite well, however note that this was a veeery simple scene. In more complex scenes you may get different results.

  1. No. For pathfinding to take something into account, it needs to have it baked into the navmesh.
    Depending on the recalculation times this may or may not be an issue for you though. You may be able to handle it by simply adding a collider around the object for a second or so, to keep agents outside it. Note that you also have the special case of someone removing an object while another agent is just about to walk on top of it, how to handle that is a bit more tricky perhaps.

  2. There is nothing built-in for the actual behaviors. This is a pathfinding library and those approaches are better formulated in terms of state machines or behavior trees (e.g ‘move to elevator button’, ‘move into the elevator’, ‘wait…’, ‘move out of the elevator’). In terms of adding links so that the agents know that they can actually use an elevator, those links can be added right now, however agent support for following links is not the best at the moment. I would say it is the least polished part of the package. There is an example scene where you can see an agent jumping between platforms and climping up a ledge, so things like that are possible though.

#3

Thanks for getting back to me!

  1. So if the agents stop during recalc, does that mean that all my NPCs across the whole scene that are walking will stop simultaneously, then restart once the recalc is done? Or just the ones in the relevant tile? Or just the ones on this mesh, but not on other meshes in the same scene?

  2. The collider idea will work fine! You’re right about the edge case, but I’m sure I can work it out.

  3. Sure, my NPCs are GOAP agents driven by an internal state machine. It’s good to be reminded that the links are relatively unpolished. At least I’d have the source so I could push forward by patching any limitations. As long as I can have the NPC navigate to the link point, then pause navigation while I go through the rest of the steps, then resume navigation starting from the connecting point, then I should be able to work out the rest.

#4
  1. Agents don’t stop, only pathfinding calculations stop. This means agents cannot recalculate their paths during a graph update. Usually this is fine, however if the update takes too long or there are too many of them so that very little time is left for pathfinding, then things can go badly.
#5

Oh, perfect, that’s fine with me. These NPCs are pretty leisurely, they’ll be fine chilling out for a second or two while it refreshes :slight_smile:

I took the plunge and bought pro just now.

Thanks for the help. If I write any useful mesh link code, I’ll let you know so maybe it can be incorporated!