- Home /
2D Tile Road Pathfinding
I'm currently trying to implement a simple path finding script which will just follow different roads on a 2d tile grid.
It might not even fall into the category of path finding since there are no obstacles - only different pieces of road which should be followed.
I would like to then be able to return the path which will bring you the closest to the target tile in as little moves as possible.
So here is my grid:
I started by creating a new class for each tile and named it the Tile class - this class just holds information on each tiles rotation, position in the grid and type of tile.
I also created a new class called QuadInt which will just hold 4 integers. I use this class to store which directions of a tile have road on them. For example:
Tile newTile = new Tile();
newTile.type = 1;
newTile.directions = new QuadInt(1, 1, 0, 0);
This would look like this for a tile:
So QuadInt(1, 1, 0, 0) describes if the top, right, bottom and left part of a tile have road on them.
Now I can know the road directions of each tile and compare them to find a continuous path. This is where I am getting stuck unfortunately. The main problem is that the roads have multiple conjunctions at which the path can take two or more different turns - I would have to follow one path and then go back to the first conjunction and follow the second route and do the same for any other crossroads along the way.
I would like to find my own solution if possible since I would like to learn how this kinda thing works.. I'm not sure if A* could be used in this scenario?
Are there any flaws in my approach and any ideas on how to deal with this issue?
Thanks for the help!
Answer by fafase · May 04, 2014 at 11:27 AM
You could start with a basic Bfs algorithm.
Each tile knows about the next tile and you just use the algorithm to find all paths. http://unitygems.com/tree-search/
Instead of returning when you get a path, you store it and compare them and pick the shortest.
Other way, use A* which not only will find the shortest but also will go faster since it uses heuristic to predict which should be shorter.
Thanks for the fast reply! This looks like exactly what I need, will read through the tutorial :)
Thanks for the tutorial fafase, I'm just a little stuck on how to setup the tree in this scenario.
The tiles in the grid can rotate so I would need to be able to create the parent tree at runtime. For each tile I could store which other adjacent tiles are reachable.
What I am confused about though, is can I parent tile 3 back to tile 2 in the following image, despite tile 2 being the parent of tile 3?
If not then some of the roads will be blocked in certain directions I think.
Well if the tile is rotating it might be a little different. You have your QuadInt and rotating a tile is pretty much pushing the value left or right depending on the rotation.
But I would have a script that keep track of all four adjacent tiles and which are currently children.
That is one tile has four adjacent and 0 to 4 children.
Adjacents are defined with drag and drop n the script, while children are done on Start and later on rotation (probably using an event).
Your method would rotate the tile, then considering the new QuadInt values would tell the adjacent tiles that their children list should be updated.
simple something like: for (int i = 0 ; i < adjacent.Length, i++) adjacent[i].IsChildren(quadInt[i], this);
and the method goes:
public void IsChildren(int value , Tile tile)
{
if(value == 0)children.Remove(tile);
else if (value == 1)children.Add(tile);
}
Then you can use bfs just as is. Ins$$anonymous$$d of the built-in array of the tutorial, you use a dynamic list of children.
Am I clear enough...?
What I am confused about though, is can I parent tile 3 back to tile 2 in the following image, despite tile 2 being the parent of tile 3?
Since a is adjacent of B, then B is adjacent of A and all children updates each other.
Awesome, I think that clears it up a bit ;) Am currently in the middle of creating a method which will update adjacent and children tiles.
Think I have a better understanding of the basics of the algorithm now, might have to read the tutorial a couple more times though haha.
So essentially I just need to add any adjacent tile (which has a connecting road etc) to the children array of the current tile and do this for all the tiles in the grid.
Then just use the Bfs algorithm which will cycle through the children and find the target I set. I think :) Thanks again for the help!
Essentially, each tile has 4 adjacent that are permanent and most likely added manually via inspector. Expect for the side tiles which have only 2 or 3 adjacent tiles.
While rotating, you updated the children list which correspond to the roads.
Nonetheless, keep in $$anonymous$$d that if a tile has a connection with the next tile, it may be that the next tile is not connected back!!!
Tile A may have a road to tile B but maybe there is no road on B, see your second tile on the first pic, it is connected to the first but the first has none, so when updating the children, you could also check if there is something on the other side which in the end would save some computation as you can discard a road with no real connection on the other tile.
Answer by Mathes06 · Jan 22, 2019 at 07:22 PM
I know this is a quite old question, but is therea new http://unitygems.com/tree-search/ or can I get a bit of the old code if this avaiblable? I still have problems with lining up the tiles correctly.
Your answer
Follow this Question
Related Questions
A* Pathfinding, destroying a path once it has reached its end 0 Answers
FixedUpdate is Being Called Less and Less Over Time...Why? 1 Answer
AI & pathfinding for 2D platformer - how to approach? 0 Answers
A* pathfinding for 2D top Down 0 Answers
Enemy Movement AI in top-down, 2D, tile & turn based game 1 Answer