0
\$\begingroup\$

Consider the following road network. The car (orange) needs to get to the red circle. It drives on the right hand side of the road and is initially facing down.

The shortest path is the blue one. But if it follows this path, it reaches the red circle on the wrong side of the road. To actually get to the red circle, it needs to take the green path - much longer. The pink dots represent the nodes - the road network is made up of modular road pieces. Each node also stores all the possible directions a vehicle could take from that piece.

How can I make a pathfinding algorithm that takes this into consideration?

enter image description here

Improve this question
\$\endgroup\$
7
  • \$\begingroup\$ Do you know on which side of the road the goal is ? \$\endgroup\$ – ColdSteel Jun 10 '19 at 2:32
  • \$\begingroup\$ Yes. I know the position and orientation (and thus the side of road) the goal is. The goal isn't necessarily at a pink node - it could be between them but it will always be on a straight section. \$\endgroup\$ – mr-matt Jun 10 '19 at 2:34
  • \$\begingroup\$ If being on the left side of the road is different than being on the right side of the road, then those two states need to be two different nodes. Once you've created nodes for the distinct states you care about, and set up their adjacency graph correctly, a completely vanilla pathfinding algorithm will find the shortest path that puts you on the correct side of the road. \$\endgroup\$ – DMGregory♦ Jun 10 '19 at 2:35
  • \$\begingroup\$ What about reverse pathfinding ? From the goal to the car, this way you can vanish out cells that are in opposite side of the road ? \$\endgroup\$ – ColdSteel Jun 10 '19 at 2:35
  • \$\begingroup\$ Then I have the same problem but at the other end. If I go from the red dot along the blue line, I will end up on the wrong side. I would have to go right at the T intersection and loop back around. \$\endgroup\$ – mr-matt Jun 10 '19 at 2:38
0
\$\begingroup\$

Each purple dot in your image will be represented by multiple nodes in the graph. Each graph-node will not only represent the car's position, but also the direction it came from.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Can you elaborate a bit more? What is the "graph"? And how would I represent a corner in the graph. \$\endgroup\$ – mr-matt Jun 10 '19 at 2:40
  • \$\begingroup\$ @mr-matt: A graph is the fundamental object needed to run A*. It's too large of a subject to get into in the comments, but there is a plethora of material online. You literally cannot use A* without understanding what a graph is. \$\endgroup\$ – BlueRaja - Danny Pflughoeft Jun 10 '19 at 2:42
  • \$\begingroup\$ Ok I see. Can you explain the part about storing the direction each graph-node came from? I'm not sure I understand how that would help. \$\endgroup\$ – mr-matt Jun 10 '19 at 2:54
0
\$\begingroup\$

I would use filtering. For example you can assign a filter to the car lest say a bitmask, then you can assign filter to cells (assuming it is a grid system).

When you run your ASTAR (assuming it is an astar) you can calculate cell cost or passibility by the filter masks - for example if the car has right filter mask then all the left filter masked cells will become impassible.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I'm not sure that will work. I've updated the screenshot with the node positions. I have one node for each road piece - the network is made up of modular roads. I'm not sure how I would divide that up to have a node on each side of the road. It won't work so well around the corners. \$\endgroup\$ – mr-matt Jun 10 '19 at 2:23
  • \$\begingroup\$ @mr-matt Sorry, guess I misread the question \$\endgroup\$ – ColdSteel Jun 10 '19 at 2:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.