koobas.hobune.stream
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!
@BackslashOllie What you could do is use a modified djikstras and use it as a flood-fill (add all neighbours of a node and assign them to the same int areaNum (a variable acting as an ID), do this until no more neighbours can be added and do this for every node which areaNum == 0) too check if both blue and yellow are contained in the same area of the grid. And if they're not connected you randomize the map again until they're in fact connected.
Thanks for the idea! I can see one problem with this for my situation is that when the levels progress the size of the grid and the amount of red space will increase. With this solution it will get to a stage where a path will not be available and if that is the case it will be an endless loop. How could I handle that situation?
This seems like just a general maze-making problem. Lots have been written on mazes. You might Search that, without worrying about it being a specific Unity solution.
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.
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?
Hey thanks for the response, I may not have made my question as clear as I should.
$$anonymous$$y question is really how I can randomly generate this grid making sure that there is a path from A to B. $$anonymous$$y thought with A* was to randomly generate the map then find path from A to B. If path is not successful either randomise again like @salmjak said or to clear red nodes until a path can be found. I feel that there is a better way of doing this though.
Ah, yea that makes a bit more sense now.
Definitely wouldn't pick A*, a bit too iterative of a process. If you only want a single correct path to the destination, you could try randomly generating the path first, then just randomly filling in red squares around it.
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.
