• Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
  • Asset Store
  • Get Unity

UNITY ACCOUNT

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account
  • Blog
  • Forums
  • Answers
  • Evangelists
  • User Groups
  • Beta Program
  • Advisory Panel

Navigation

  • Home
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
    • Blog
    • Forums
    • Answers
    • Evangelists
    • User Groups
    • Beta Program
    • Advisory Panel

Unity account

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account

Language

  • Chinese
  • Spanish
  • Japanese
  • Korean
  • Portuguese
  • Ask a question
  • Spaces
    • Default
    • Help Room
    • META
    • Moderators
    • Topics
    • Questions
    • Users
    • Badges
  • Home /
avatar image
1
Question by ByteSheep · May 04, 2014 at 11:13 AM · 2daipathfindingtileroad

2D Tile Road Pathfinding

I'm currently trying to implement a simple path finding script w$$anonymous$$ch 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 w$$anonymous$$ch should be followed.
I would like to then be able to return the path w$$anonymous$$ch 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 - t$$anonymous$$s class just holds information on each tiles rotation, position in the grid and type of tile.

I also created a new class called QuadInt w$$anonymous$$ch will just hold 4 integers. I use t$$anonymous$$s class to store w$$anonymous$$ch 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);


T$$anonymous$$s would look like t$$anonymous$$s 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. T$$anonymous$$s is where I am getting stuck unfortunately. The main problem is that the roads have multiple conjunctions at w$$anonymous$$ch 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 t$$anonymous$$s kinda t$$anonymous$$ng works.. I'm not sure if A* could be used in t$$anonymous$$s scenario?

Are there any flaws in my approach and any ideas on how to deal with t$$anonymous$$s issue?

Thanks for the help!

example_tile.png (29.2 kB)
screen shot 2014-05-04 at 12.21.01.png (350.9 kB)
Comment
Add comment
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users

2 Replies

· Add your reply
  • Sort: 
avatar image
2
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* w$$anonymous$$ch not only will find the shortest but also will go faster since it uses heuristic to predict w$$anonymous$$ch should be shorter.

Comment
Add comment · Show 8 · Share
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users
avatar image 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 :)

avatar image 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)
avatar image 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.

avatar image 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!

avatar image 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
avatar image
0

Answer by Mathes06 · Jan 22, 2019 at 07:22 PM

I know t$$anonymous$$s 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 t$$anonymous$$s avaiblable? I still have problems with lining up the tiles correctly.

Comment
Add comment · Share
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users

Your answer

Hint: You can notify a user about this post by typing @username

Up to 2 attachments (including images) can be used with a maximum of 524.3 kB each and 1.0 MB total.

Welcome to Unity Answers

If you’re new to Unity Answers, please check our User Guide to help you navigate through our website and refer to our FAQ for more information.

Before posting, make sure to check out our Knowledge Base for commonly asked Unity questions.

Check our Moderator Guidelines if you’re a new moderator and want to work together in an effort to improve Unity Answers and support our users.

Follow this Question

Answers Answers and Comments

21 People are following this question.

avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image

Related Questions

FixedUpdate is Being Called Less and Less Over Time...Why? 1 Answer

How do I go about making a 2d platform enemy ai 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


Enterprise
Social Q&A

Social
Subscribe on YouTube social-youtube Follow on LinkedIn social-linkedin Follow on Twitter social-twitter Follow on Facebook social-facebook Follow on Instagram social-instagram

Footer

  • Purchase
    • Products
    • Subscription
    • Asset Store
    • Unity Gear
    • Resellers
  • Education
    • Students
    • Educators
    • Certification
    • Learn
    • Center of Excellence
  • Download
    • Unity
    • Beta Program
  • Unity Labs
    • Labs
    • Publications
  • Resources
    • Learn platform
    • Community
    • Documentation
    • Unity QA
    • FAQ
    • Services Status
    • Connect
  • About Unity
    • About Us
    • Blog
    • Events
    • Careers
    • Contact
    • Press
    • Partners
    • Affiliates
    • Security
Copyright © 2020 Unity Technologies
  • Legal
  • Privacy Policy
  • Cookies
  • Do Not Sell My Personal Information
  • Cookies Settings
"Unity", Unity logos, and other Unity trademarks are trademarks or registered trademarks of Unity Technologies or its affiliates in the U.S. and elsewhere (more info here). Other names or brands are trademarks of their respective owners.
  • Anonymous
  • Sign in
  • Create
  • Ask a question
  • Spaces
  • Default
  • Help Room
  • META
  • Moderators
  • Explore
  • Topics
  • Questions
  • Users
  • Badges