Is this behavior normal (Point Graph)? Why my car is not using the shortest path?

General
#1

Hi guys!

First sorry for my english it’s not my main language.

I’m currently developing a very simple traffic system with the A* asset and all work good except for one thing, a situation where the car is taking the longest path instead of the shortest. Please look at these pictures:

2018-10-07_17-33-06
2018-10-07_17-33-061455×486 321 KB

PS: Do not pay attention to node colors.
As you can see, the car is taking the longest way (to reach my target) instead of the shortest at the bottom.

Another example if I change the position of my target (this work good):

2018-10-07_17-33-48
2018-10-07_17-33-481456×503 322 KB

Another example (this work good too):
https://imgur.com/tnnOCzn

All my node connections are working good, it’s very strange that in the first case he took the longer path instead of the bottom one, who normally is shorter.

Here is a screenshot with my custom connections between nodes: https://imgur.com/a/f9vnYW2.
Every connection is only in one way (traffic way).

Again sorry for my english.
Thanks!

#2

Hi

With one way connections there are some parts of the system that can get confused.
The package tries to calculate the connected components of the graph, however that info is not well defined in some cases when using one way connections.

Which version are you using?

#3

Aaah hum ok I better understand why i’m having this behavior. I know that your asset is not optimised for a traffic system but I thought that I will be more smart than other people if I’m using a one-way connection between nodes. :sweat_smile:

I’m using the last version, 4.1.16.
Well, I imagine there is no “easy” method to fix that?

#4

Hi

Yes, you can disable that behavior like this:
In the GraphUpdateProcessor class, find the FloodFill() method with no parameters. Add a ‘return’ statement at the top of the method.

public void FloodFill () {
    return;
    ...
}
#5

Unfortunately it doesn’t work, the car is still going by the wrong way. :persevere:

2018-10-10_12-20-56
2018-10-10_12-20-561100×488 157 KB

Here is the steps of my test script:

  • Foreach through my anchors on roads (anchors are replaced by a node)
  • A node is added like this “activeGraph.active.AddWorkItem(new AstarWorkItem(ctx => { …some code… ctx.QueueFloodFill();}”
  • I scan the graph with the Scan() method
  • A loop with GetNodes is created where every node are connected between them in the good traffic way (every node have a cost of 0)
  • And finally I start the search with the seeker method StartPath(…)
#6

Hmmm… Strange.

If you are doing that before the scan, then any nodes you create in there will be destroyed once the Scan happens. The Scan completely recalculates the graph from scaratch.

You say every node has a cost of 0. You don’t mean the edges have a cost of zero I hope? If so, that would mean that the pathfinding system cannot differentiate between the path at the top and the path at the bottom because they have the same cost (a cost of 0).
Also, if you are using odd costs, you should probably set A* Inspector -> Settings -> Heuristic to None. Otherwise the system assumes that it is not possible to move between two points with a lower cost than the world space distance between them (this is the A* specific part of the A* pathfinding algorithm).

#7

Yes you got it, the good combination is FloodFill() return; and Heuristic set to None. :clap:

I will in a near future put different type of roads (dirt road, asphalt, etc.) where the edge cost of asphalt is higher than dirt road, will I have a problem of setting a cost with the Heuristic setted to None?

#8

Hi

Nice!

No, that will work fine.
With the Heuristic set to None the search will be equivalent to a Dijkstra search.

#9

Thanks you again for your time, it’s marvellous! :smile: