Wayback Machinekoobas.hobune.stream
May JUN Jul
Previous capture 12 Next capture
2021 2022 2023
1 capture
12 Jun 22 - 12 Jun 22
sparklines
Close Help
  • 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 /
  • Help Room /
avatar image
0
Question by BackslashOllie · Mar 15, 2016 at 07:45 PM · randompathfindinggeneration

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!

alt text

unityanswer.png (21.5 kB)
Comment
Add comment · Show 3
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 Salmjak · Mar 15, 2016 at 08:10 PM 0
Share

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

avatar image BackslashOllie Salmjak · Mar 15, 2016 at 09:48 PM 0
Share

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?

avatar image Owen-Reynolds · Mar 15, 2016 at 08:44 PM 0
Share

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.

4 Replies

· Add your reply
  • Sort: 
avatar image
0
Best Answer

Answer by BackslashOllie · Mar 16, 2016 at 01:35 PM

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.

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

Answer by Brocccoli · Mar 15, 2016 at 08:51 PM

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?

Comment
Add comment · Show 2 · 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 BackslashOllie · Mar 15, 2016 at 09:12 PM 0
Share

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.

avatar image Brocccoli BackslashOllie · Mar 16, 2016 at 01:39 PM 0
Share

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.

avatar image
0

Answer by Oukalakakou · Mar 15, 2016 at 09:07 PM

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.

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

Answer by Dudicus · Mar 16, 2016 at 12:45 AM

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

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.

Follow this Question

Answers Answers and Comments

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

Related Questions

How to generate a random 2d world for a 2d endless runner 0 Answers

Random.Range not repeat same position 0 Answers

How can I let my car AI follow a Node-Path slightly random? (C#) 0 Answers

Spawning object with new random pathing.,Randomly moving after spawn 0 Answers

How to instantiate bunch of cubes randomly in particular direction? 0 Answers


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