Hey guys! I have one quick question: Does anyone know is it possible to add two paths not connected with each other in the same grid of nodes for A* algorithm?
Something like this:
The reason why I want to do this is I’m making a city sim project and I would like to add node-based pathfinding to my roads. Now the problem is if I make one street with road segments and another street which isn’t connected with first one, I don’t want vehicles to move from one street to another.
I’m using tile based grid and right now it’s 100 x 100 points. I think I could make all points in the grid by default with a cost of 1 and when I place a road segment, cost becomes 0. This could work really well but I’m afraid of having an array of 10,000 nodes.
A* just goes from a node through its connected nodes until it gets to the destination or fails. If the node it starts at has no possible way of getting to the other node it will just fail it wont be able to jump over.
In these cases, it is often helpful to keep track of connected components, so that you can quickly answer the question “can I get from A to B” before you do the actual pathfinding from A to B. Otherwise, A* will exhaustively search for a path before deciding that no path exists, and that can get extremely costly.
1 Like
Thank you so much for mentioning connected components. Looks like a great way to exactly do what I want right now. Will definitely look more into implementations of it.
Thank you guys for your time and helping me! Much appreciated