Questions about graph creation

#1

Hi,

I am considering buying this product as on the surface it looks like it will save me a huge amount of time but I have a few technical questions I couldn’t find answers for by searching the forums.

I am currently making a procedurally generated equilateral triangle based world with a hex backbone. I am wanting to do navigation based on the hexagons, I already know if a hex is walkable or not and all this information is stored in a 2d array.

Question 1: Can I load the 2d array directly into the A* pathfinding algorithm and use it for navigation or is there some easy conversion I can do?

Question 2: Although the walkability is calculated by the hex centres would this be an issue for the agent height, as the height can vary across a hex according to the 6 triangles that make up the hex. Obviously I could convert the hex walkable data to tri based but this would triple the number of nodes/grid points and therefore is undesired as I am dealing with a huge world.

Example:

Question 3: Local avoidance. My game will have a lot of walkable areas that have local obstacles such as trees. I’m pretty sure the answer is yes but just to check does the local avoidance system work well for avoid small obstacles such as trees or is it more designed to avoid other agents?

Question 4: Can you switch an agent easily between two different navigation systems, I am wanting to use the hex based system when an agent in out in the open, but use a node or nav mesh based system when the agent is in a more complex area such as a base.

Question 5: If I can use the 2d array of walkable hex data can this be updated at runtime? If it can does this have any performance considerations or can I do a simple array edit just changing the required hexes? This also goes for node or nave mesh systems can they be modified at runtime and if so what is the cost?

Thanks,

Ken

#2

Hi

Are you sure you really want it backed by a hexagonal graph? What is the reason for this if you want to use navmeshes for dense areas anyway?

In the meantime, as for 1. Take a look at https://arongranberg.com/astar/docs/graphupdates.html in particular this section: https://arongranberg.com/astar/docs/graphupdates.html#direct.

2 Pathfinding is done per node, so if you want different information in each triangle, then each triangle has to be a node.

3 Generally it is better for agent-agent avoidance. agent-obstacle local avoidance is not that well optimized at the moment either.

4 Yes, you can use multiple graphs and switch between them by sending a different graphMask to the Seeker.
This requires some minor changes to the movement scripts just to pass a new parameter.
See AI of different size in Recast Graph

5 Yes, that is also covered by the links above. The cost depends on what you need to change, changing the penalty of some nodes is very fast, however changing other things such as walkability can be slower because of other data structures that need to be recalculated.

#3

Thanks for the response.

The reason I want to use the hexagonal grids is after the world gen I already have the hexagonal graph data, so I want to avoid baking a huge nav mesh in run time. Also I want the navigation to be as efficient as possible so using the hexes is the smallest possible data set. For the dense areas that are placed in the world, they can have there nav mesh pre baked.

With regards to the 3rd question is it possible to edit paths on the fly to do my own avoidance? As the avoidance path would only be a small deviation I was planing to do with via 2 hit boxes in front of the agent similar to the way it was done in left 4 dead with the zombies.

Thanks

Ken

#4

Ok. Though keep in mind that it can sometimes be tricky to do pathfinding on multiple different graphs in a smooth way.

Yes, you can edit the path. However iirc left 4 dead used a movement behavior that was applied each frame, they didn’t edit the path directly. So writing your own movement script sounds like what you want to do. You can check out this part of the get started tutorial which shows you how to write a (very simple) movement script: https://arongranberg.com/astar/docs/custom_movement_script.html