Clear path from A to B

Hi all,

I have a simple grid of nodes which is randomly filled with green tiles and red tiles. Any ideas on how I would make sure there is a green path between the blue square and the yellow square?

The path does not need to be a straight path there just has to be a path between them. In fact, I would prefer it not to be straight.

My initial idea was to use A* pathfinding and add random weighting to each of the nodes, but I feel there must be a better solution. Any ideas or links to useful materials would be greatly received.

Thanks in advance!

65983-unityanswer.png

Why not A* though? It’s going to do exactly what you need.

Red nodes are not traversable, and green nodes are. Random weighting won’t do anything for you if you’re just looking for a path. A normal A* result will tell you if there’s a path or not by virtue of whether or not the algorithm returns anything.

Blue is your start and yellow is your destination.

Am I missing something?

If you want to check if there is a green path between the blue and yellow tile all you have to do is a simplified pathfinding method, simplified because you will not have to return a path.

Create two lists of tiles or whatever references them the best, one called the open list and another called the closed list. Add the starting tile let’s say the blue one to the open list. Then iterate in a loop while the open list is not empty.

In your loop you will add to the open list the neighbouring green (or yellow) tiles that are not in the closed list of the first element of the open list and then remove that element from the open list and add it to the closed list.

You should also, at the beginning of the loop, check if you are on the yellow square. If that’s the case return true. If your loop ends by itself return false.

Edit

If I were you and wanted to make sure there is a random path between my two points I would create it.
But do you need your blue and yellow tiles to be fixed before the path is created? If not, why not create a blue tile somewhere and just red tiles everywhere, then create a random path of green tiles starting from the blue one and when you feel yourself far enough of your start position make a yellow tile and stop.

Make the code keep on generating new random sets until the pathfinding code says its possible then show the set to the player.

Thanks to all for replying. A good friend of mine helped me resolve this for my particular situation.
My solution is using a flood fill algorithm which checks that all parts of the map are accessible from the blue square whilst I am generating random obstacles (red squares) using this as a reference:

Sebastian Lague’s Create A Game Series

Once I have generated this fully accessible map I can then safely place the yellow square in a random location within the green squares.