2D Tile Road Pathfinding

Question

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: alt text

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:

alt text

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 1

Best Answer

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.

Add comment · Show 8 · Share

ByteSheep · May 04, 2014 at 11:37 AM 0

Share

Thanks for the fast reply! This looks like exactly what I need, will read through the tutorial :)

ByteSheep · May 04, 2014 at 03:28 PM 0

Share

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?

alt text

If not then some of the roads will be blocked in certain directions I think.

example_tiles.png (19.1 kB)

fafase · May 04, 2014 at 05:11 PM 0

Share

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. Instead 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.

ByteSheep · May 04, 2014 at 05:29 PM 0

Share

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!

fafase · May 04, 2014 at 06:34 PM 0

Share

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 mind 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.

Show more comments

Answer 2

Answer by Mathes06 · Jan 22 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.

Add comment · Share

2D Tile Road Pathfinding

2 Replies

Your answer

Welcome to Unity Answers

Follow this Question

Related Questions