Uniform Edge Cost Movement Range & pathfinding

General
#1

I’ve got a question about edgecosts and ConstantPath.

I am working on a project with xcom-like combat system. Units move on grid graph with eight connections. Unit range is square (as uniformEdgeCost = true on a graph) but the path should be as straight as possible.

What is the best way to achieve this? I am using ConstantPath (after setting uniformEdgeCosts to true and rescanning the graph) to be able to get square range for the unit. Then I would like to get the path to the point within the range - but with uniformEdgeCosts the path is unnecesarry mangled while with non uniform edge costs the path is exactly as would expect it to be. Is there a way to set edge costs only for calculating the path? Do I need separate graphs (one to calculating range, and other to pathfinding)? Or maybe there is a better way as rescanning the graph, or having duplicated graph seems far from acceptable?

I would really appreciate some insight ^^

P.S. I am using version 4.3.19 if that matters

#2

Hi

It sounds like you want to look at the A* Inspector -> Settings -> heuristic setting.

Take a look at https://arongranberg.com/astar/docs/pathfinding.html#Heuristic

Oh, and you can probably get the desired range using PathUtilities.BFS. See https://arongranberg.com/astar/docs/pathutilities.html#BFS

1 Like
#3

Thanks! Seems like BFS answering my question :slight_smile:

1 Like
#4

hi @aron_granberg - I’ve got another question regarding this.

The BFS gives me the exact range that I am after. But things are getting a little bit more complicated when I am using larger units.

Side info: I am writing x-com like movement with units that are occupying square space on grid/layeredgrid graph.

So - when using BFS for a larger units (i.e. 2x2, 3x2) I am getting the range that seems okay at first glance, but it may contain a “tight” passages when this unit couldn’t fit while traversing. Since BFS cannot utilize ITraversalProvider there is not easy way around it. The constant path would theoretically do just fine (because it uses traversal provider) but it gives me wrong range - since I cannot set uniformEdgeCost for entire graph.

Is there a way to overcome this? Maybe you have something planned or I can do something? What will be your approach? Do you plan to make BFS that will take traversal provider into account?

#5

Hi

You can use the optional filter parameter to the BFS call. The ITraversalProvider does require a path object as well, so you might have to create a dummy path object to pass to the ITraversalProvider.

See https://arongranberg.com/astar/docs/pathutilities.html#BFS

1 Like
#6

Thanks! I’ll try that!