Navigating by non-physical and physical aspects of a scene?

Arakade · February 5, 2016, 2:23pm

Hi,
I want to use A* Project to allow my AI players to determine paths that maximize going across valuable areas. A way to do this would be creating a semi-physical ‘space’ where traversal cost is a combination of both normal physical and the value-measure (i.e. paths of least ‘value’ would be least likely chosen). However, I also wish to navigate by regular physical space.

I seek advice on the best way to achieve this.
I think my ‘value space’ would be best done as an optionally-used addition to the physical data. More details…

My world is partially procedurally generated with resources smoothly varying over the ground. Resources don’t affect traversability … well, kind’a. (Maybe I can explain: it’s snow, they’re snowmen that roll over sufficiently flat snow for health. The snow is an unmoving but modifiable voxel space atop static world geometry.)

(Wha?!.. just realized I seem to have no video clip of this!? How can this be?! Will fix for ScreenShotSaturday!) Anyway, back to the question…

I’d like to have my AI be able to determine nearest/etc ‘usable’ resources. (usable = sufficient smooth snow. They need this when low on health!)

In case it makes a difference, I’m currently using a GridGraph though I’ll likely need Layered pretty soon.

My first impulse was to avoid needing to modify the A* project source. Perhaps somehow including this info in the existing A* info – perhaps as a … um, varying tag? I’m not convinced by this approach. Thoughts? Otherwise, next!

I next allowed myself to poke around in the code (beautiful, I’m sure you know) and wondered if I could add some custom user data to a GridNode (e.g. hang a System.Object reference off GridNode and populate in UpdateNodePositionCollision() with an optionally null delegate). Then perhaps some optionally null cost evaluation delegate could override cost determinations for Graph consumers that ask in a certain way. My intent here being a patch to A* Pathinding Project that can be pushed and be useful to others so as not to fork myself painfully

Any thoughts, etc are obviously not only most welcome but keenly sought!
Thanks, Rupert.

p.s. I’m using latest A* Pro with Unity 5.1.3 (soon to upgrade) on Windows 8.1 in case it’s relevant.

aron_granberg · February 8, 2016, 2:42pm

Hi

Hm. I think the problem you are trying to solve is very hard in theory (i.e to solve optimally). However some cheating can probably be done to get something working.

My first thought would be to make nice snow have a different tag than the rest of the ground and set the penalty for traversing the regular ground very high. Then you could e.g use the XPath path type to add a custom ending condition for the path. I recommend something like “if world distance to start position > threshold” since then that will give you back the path which moves X world units away from the start point with the lowest cost (i.e highest amount of snow). You would set the heuristic on the path to None for it to search in a circle around the start point.

Arakade · February 8, 2016, 5:06pm

Thanks for replying!

Before I start, here’s that video of the Snowmen rolling for their life I promised

OK but wouldn’t that penalty apply even when not aiming to traverse ‘good’ snow? (i.e. valid paths that happen to not have rollable snow would be incorrectly biased against/removed from the search.)

Had a quick look into XPath path type…

…Gotcha. Yes that part makes sense. It’s much better than my planned MultiTargetPath approach where I’d need to specify a few potential places the AI might want to end up (or I thought I might try a Flee path but I’ve not looked into that yet).

So, just need to determine whether my concern at the top is correct.
Thanks again!

aron_granberg · February 8, 2016, 5:16pm

You can set the tag penalties per path request by changing the tagPenalties field on the Path object.

However the Seeker sets that field when StartPath is called, so maybe you are better off modifying the array that the Seeker uses.

seeker.tagPenalties = tagPenaltiesForSnowBias;
seeker.StartPath(...);

seeker.tagPenalties = tagPenaltiesRegular;
seeker.StartPath(...);

Note that you cannot modify the array itself since the path will read from that same array when it is being calculated, and if you happen to have both a MultiTargetPath and a regular path that are being calculated at the same time they will still use the same array and thus the same penalties unless you change it to a completely different array.
Hope that makes sense.

Arakade · February 8, 2016, 8:06pm

OK that sounds great. (I’ve not implemented yet but I might start a little later this evening.)
Thanks again for all this help! Your superb support was one of many reasons I chose your asset over others.

So (cheekily ), the last part that I think I don’t full have yet is how to (ideally efficiently) set the tags in the right places. I’m aware of 2 ways one can set tags:

using the image-based
using GraphUpdateObject to set an entire area.

What others are there?

The way I’d originally thought to do this was tie-into the raycasting you already do that looks at gradients. This is exactly the info I need anyway – that plus whether the surface is consistently the snow material (easy to also check in the RaycastHit info). Is there a way to do this? I guess the supported way would be:

On snow updates (including initial generation), wait for a given section of floor to have snow generation complete.
Gather snow rollability info myself (might be able to determine from procedural generation tie-in or maybe just do some raycasting myself – haven’t determined yet.)
Call UpdateGraphs(GraphUpdateObject) enough times to cover areas / variations, pre-populated with appropriate tag settings

Thoughts?

p.s. Actually, I just realized there’s an added complexity due to vary sizes of Snowman making different widths travellable / usefully rollable. Darn. (i.e. A huge snowman needs different radius on its path tests… hm I know that info is in the original A* scan – I guess one puts the smallest size in there and maybe the Seeker has some setting to indicate how wide it actually is? Sorry, thinking aloud here. I’ll need to investigate this.)

Thanks again, R.

aron_granberg · February 8, 2016, 8:18pm

Hi

Thank you for the kind words
When you have used the package for a while, a rating and/or a review on the Unity Asset Store would be very appreciated.

If you can easily get the information from a raycast and you know what regions need to be recalculated, the best option might be to make a subclass of the GridGraph.

public class MyGridGraph : GridGraph {
     public override UpdateNodePositionCollision (GridNode node, int x, int z, bool resetPenalty = true) {
            base.UpdateNodePositionCollision(node, x, z, resetPenalty);
            node.Tag = // some snow check here
     }
}

You will also need to add

[CustomGraphEditor(typeof(MyGridGraph), "Custom Grid Graph")]

To the GridGraphEditor script to make it show up in the inspector.

Then you can simply call UpdateGraphs with the updatePhysics field set to true and that will call the UpdateNodePositionCollision method for all nodes that need to be updated.

I would recommend that you create two or maybe three graphs to handle the different sizes. It can be done with tags as well, but the tags are going to be used for snow and it is usually generally better to do it using a separate graph instead (unless you are very concerned about memory/graph update performance).
You can choose which graph to use by passing a graphMask parameter to the seeker.StartPath call in the movement script. See A* Pathfinding Project

Arakade · February 8, 2016, 11:47pm

Great! Created myself a GridGraph subclass, updated the Editor attribute and overrode UpdateNodePositionCollision() then copied the original code from GridGenerator. I did this so I can re-use the ray-cast that was already being done in there. Got the hit.transform.GetComponent.sharedMaterial and do a dummy test and yep – can tag on the basis of material

Only hitch is that even without my extra code, I get this error a lot:

NullReferenceException: Object reference not set to an instance of an object
  at Pathfinding.GridGraphEditor.OnSceneGUI (Pathfinding.NavGraph target) [0x00066] in D:\Users\Rupert\Dev\Unity3D\AIExperiments\Assets\Standard Assets\Editor\AstarPathfindingProject\Editor\GraphEditors\GridGeneratorEditor.cs:623 
  at AstarPathEditor.OnSceneGUI () [0x0008a] in D:\Users\Rupert\Dev\Unity3D\AIExperiments\Assets\Standard Assets\Editor\AstarPathfindingProject\Editor\AstarPathEditor.cs:900 
  at (wrapper managed-to-native) System.Reflection.MonoMethod:InternalInvoke (object,object[],System.Exception&)
  at System.Reflection.MonoMethod.Invoke (System.Object obj, BindingFlags invokeAttr, System.Reflection.Binder binder, System.Object[] parameters, System.Globalization.CultureInfo culture) [0x000d0] in /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System.Reflection/MonoMethod.cs:222 
Rethrow as TargetInvocationException: Exception has been thrown by the target of an invocation.
  at System.Reflection.MonoMethod.Invoke (System.Object obj, BindingFlags invokeAttr, System.Reflection.Binder binder, System.Object[] parameters, System.Globalization.CultureInfo culture) [0x000eb] in /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System.Reflection/MonoMethod.cs:232 
  at System.Reflection.MethodBase.Invoke (System.Object obj, System.Object[] parameters) [0x00000] in /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System.Reflection/MethodBase.cs:115 
  at UnityEditor.SceneView.CallOnSceneGUI () [0x0006f] in C:\buildslave\unity\build\Editor\Mono\SceneView\SceneView.cs:1987 
  at UnityEditor.SceneView.HandleSelectionAndOnSceneGUI () [0x0000b] in C:\buildslave\unity\build\Editor\Mono\SceneView\SceneView.cs:1352 
  at UnityEditor.SceneView.OnGUI () [0x001a3] in C:\buildslave\unity\build\Editor\Mono\SceneView\SceneView.cs:1188 
  at (wrapper managed-to-native) System.Reflection.MonoMethod:InternalInvoke (object,object[],System.Exception&)
  at System.Reflection.MonoMethod.Invoke (System.Object obj, BindingFlags invokeAttr, System.Reflection.Binder binder, System.Object[] parameters, System.Globalization.CultureInfo culture) [0x000d0] in /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System.Reflection/MonoMethod.cs:222 
 
(Filename: Assets/Standard Assets/Editor/AstarPathfindingProject/Editor/GraphEditors/GridGeneratorEditor.cs Line: 623)

It happens when I first compile until I manually press “Scan” and then again on exiting Play mode.
Guess I might need to customize that editor a bit after all! On first glance, it’s special-casing the type exactly matching GridGraph. Perhaps changing to checking assignable from will fix.

Anyway, thanks so much so far! I’ll be coming back to more of this tomorrow night

aron_granberg · February 8, 2016, 11:55pm

Hi

Can you paste the line which throws the exception? The line numbers in my dev version will differ slightly between each released version so it is hard for me to know what is causing the problem.

Arakade · February 9, 2016, 12:27am

The ‘if’ here throws the exception. I’d guess guess nodes is null and graph.nodes.Length is exceptioning? I can’t confirm that now. (shutdown)

            if ((graph.GetType() == typeof(GridGraph) && graph.nodes == null) || (graph.uniformWidthDepthGrid && graph.depth*graph.width != graph.nodes.Length) || graph.matrix != matrixPre) {
                //Rescan the graphs
                if (AutoScan ()) {
                    GUI.changed = true;
                }
            }

Thx

Navigating by non-physical *and* physical aspects of a scene?

Navigating by non-physical and physical aspects of a scene?