Wayback Machinekoobas.hobune.stream
May JUN Jul
Previous capture 13 Next capture
2021 2022 2023
1 capture
13 Jun 22 - 13 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 /
avatar image
0
Question by ShoCo2 · Aug 07, 2020 at 09:04 AM · aipathfindingalgorithmlogic

Generate tiles along a path a certain distance before reaching end position

My end goal is to create a path from start (the circle) to the end position (the square) while making sure that the path is 2-4 tiles long. The length of the path is randomized.

The problem is that since I am working with seed based generation, I want most seeds to look unique from each other, and in order to do so twisting and bending each path differently would help make each seed seem more different from each other (among other factors that haven't been implemented in the current build). If I had an algorithm to just go from start to finish, the program in most instances would just get to the destination in the shortest distance possible, but in my case I want it to purposely take a longer way before reaching the end destination.alt text

The above 4 is an example of how different lengths/variations of lengths can affect how the path looks and how it can occupy different spaces. The square's location is also randomly generated (also made sure the square can only occupy non corner tiles and tiles not directly in the way of the starting circle).

Is there any way I can implement this or any advice that you guys could possibly give me to help achieve this? Thank you!

helppng.png (63.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

1 Reply

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

Answer by Ymrasu · Aug 07, 2020 at 12:50 PM

I would make a flow field using Dijkstra's algorithm. That way I'd know how many steps it would take to get to the end position from anywhere on the grid. Then instead of just following the shortest path, I could set the path up to be a certain amount of steps.


For example: In your grid samples, the starting position would have a value of 3 (since it takes 3 steps to get to the end, which Dijkstra's figured out) but we want a path of 4. We keep the path of 4 in mind when deciding where to go next. So we check the neighbor values of start, and we want to stay at 3 or higher since our desired path is 4. But the neighbor values are both 2, there is nothing we can do about that so we 50/50 to choose one. Then we lower the path desired down to 3 since we took a step. Lets say we went east, the next to neighbors are 1 to the north or 3 to the east. Remember we want the path to be longer still since we still need 3 steps to finish the path, but we want to remain a bit random so we can do 25/75 chance to go to the 1 or 3 value. We lower the desired down again to 2 for that step; say we went east again, the new neighbor values would be 2 and 4, we cant pick 4 since our desired path length is 2 and going 4 would make the path too long. Lets back up one and say we had picked north that had a value of 1. That would put us next to the end, the neighbors would be west, north, and east with values of 2, 0 (the end), and 2. We know we cant go north to end it yet, that would make the path too short. So randomly pick one of the 2 values. Then continue to randomly select neighbors that wont make the path too long or too short while keeping track of the remaining path length required.


I hope my "example" wasn't too wordy to get lost in. If you need a little help with coding it, I can provide some as well. Good luck!


Edit: Here is a script I put together so you can learn from. Just attach it to an empty gameobject. It uses gizmos so you can visualize whats going on.

 using System.Collections.Generic;
 using UnityEngine;
 
 public class FlowField : MonoBehaviour
 {
     public int mapSeed = 1234;
     public Vector2Int mapSize = new Vector2Int(4,4);
     public int minSteps = 2;
     public int maxSteps = 4;
     public Vector2Int start;
     public Vector2Int end = new Vector2Int(1,2);
 
     int[,] flowfield;
     int[,] pathGrid;
 
     [SerializeField] int steps; // so we can see how many steps were chosen
     List<Vector2Int> offsets;
 
     // call this for each new target
     int[,] GenerateField(Vector2Int size, Vector2Int target)
     {
         // create grid of cells holding int value (steps from target)
         var field = new int[size.x, size.y];
 
         // set all cells to -1 to show it has not been assigned a value
         for (int x = 0; x < size.x; x++)
             for (int y = 0; y < size.y; y++)
                 field[x,y] = -1;
 
         // offsets to check neighbor locations (I dont like doing this, but it was quick)
         offsets = new List<Vector2Int>();
         offsets.Add(Vector2Int.up);
         offsets.Add(Vector2Int.down);
         offsets.Add(Vector2Int.left);
         offsets.Add(Vector2Int.right);
 
         // queue to store locations that need to be checked for neighbor cells
         Queue<Vector2Int> openCells = new Queue<Vector2Int>();
         // since we are starting from target, add it to queue to have it's neighbors checked
         openCells.Enqueue(target);
         // and set it's value to 0 (since its the end)
         field[target.x, target.y] = 0;
 
         // while we still have cells being checked
         while (openCells.Count > 0) {
             var current = openCells.Dequeue(); // grab next in line
 
             // check north, south, east, and west neighboring cells
             foreach (var offset in offsets) {
                 var neighbor = current + offset;
 
                 // check to see if its within bounds of array
                 if (neighbor.x < 0 || neighbor.x >= size.x || neighbor.y < 0 || neighbor.y >= size.y)
                     continue; // out of bounds, skip it
 
                 // have we already assigned a value this cell? (not -1)
                 if (field[neighbor.x, neighbor.y] > -1)
                     continue; // already assigned a value, skip it
 
                 // queue the cell so we can check for it's neighbors
                 openCells.Enqueue(neighbor);
                 // assign it's value of 1 step greater then the cell we're coming from
                 field[neighbor.x, neighbor.y] = field[current.x, current.y] + 1;
             }
             
         }
 
         // done checking all cells
         return field;
     }
 
     int[,] CreatePath(int[,] field, int seed, Vector2Int start, Vector2Int end)
     {
         var size = new Vector2Int(field.GetLength(0), field.GetLength(1));
         int[,] path = new int[size.x, size.y]; // 0 - not path, 1 - path
         Random.InitState(seed);
 
         int requiredSteps = steps = Random.Range(minSteps, maxSteps + 1); // max is exclusive, so we need to +1
 
         // begin path from start
         var current = start;
         // make start and end a part of the path
         path[start.x, start.y] = 1;
         path[end.x, end.y] = 1;
 
         while (requiredSteps > 0 && current != end) {
             // get neighbors
             var validNeighbors = new List<Vector2Int>();
             foreach (var offset in offsets) {
                 var neighbor = current + offset;
 
                 if (neighbor.x < 0 || neighbor.x >= size.x || neighbor.y < 0 || neighbor.y >= size.y)
                     continue; // out of bounds, skip it
 
                 if (path[neighbor.x, neighbor.y] > 0)
                     continue; // already assigned a value, skip it
 
                 if (field[neighbor.x, neighbor.y] > requiredSteps || field[neighbor.x,neighbor.y] == 0)
                     continue; // not within requiredSteps
 
                 // valid neighbor
                 validNeighbors.Add(neighbor);
 
             }
             
             // other logic or weights can be placed here
             if (validNeighbors.Count > 0) {
                 // randomly pick a remaining neighbor
                 int i = Random.Range(0, validNeighbors.Count);
                 current = validNeighbors[i]; // assign to current
                 path[current.x, current.y] = 1; // add to path
             }
 
 
             // lower requiredSteps and loop again until at end
             requiredSteps--;
         }
 
         return path;
     }
 
 
     private void OnDrawGizmosSelected()
     {
         if (flowfield == null) {
             // gererate a flowfield with a grid size of 4 by 4 and a target at location (1, 2)
             flowfield = GenerateField(mapSize, end);
         }
 
         // see flowfield values
         //for (int x = 0; x < flowfield.GetLength(0); x++)
         //    for (int y = 0; y < flowfield.GetLength(1); y++)
         //        Handles.Label(new Vector3(x + 0.5f, y + 0.5f), flowfield[x, y].ToString());
 
         // Draw grid for testing
         Gizmos.color = Color.white;
         // draw horzontal lines
         for (int y = 0; y <= flowfield.GetLength(1); y++)
             Gizmos.DrawLine(new Vector3(0f, y, 0f), new Vector3(flowfield.GetLength(0), y, 0f));
 
         // draw vertical lines
         for (int x = 0; x <= flowfield.GetLength(0); x++)
             Gizmos.DrawLine(new Vector3(x, 0f, 0f), new Vector3(x, flowfield.GetLength(1), 0f));
 
         // draw target
         Gizmos.color = Color.red;
         Gizmos.DrawCube(new Vector3(end.x + 0.5f, end.y + 0.5f, 0f), Vector3.one * 0.5f);
 
         // draw start
         Gizmos.color = Color.green;
         Gizmos.DrawSphere(new Vector3(start.x + 0.5f, start.y + 0.5f, 0f), 0.25f);
 
         if (pathGrid == null) {
             pathGrid = CreatePath(flowfield, mapSeed, start, end);
         }
 
         // draw path
         for (int x = 0; x < pathGrid.GetLength(0); x++)
             for (int y = 0; y < pathGrid.GetLength(1); y++)
                 if (pathGrid[x,y] > 0) {
                     Gizmos.color = Color.yellow;
                     Gizmos.DrawSphere(new Vector3(x + 0.5f, y + 0.5f, 0f), 0.1f);
                 }
             
     }
 
     private void OnValidate()
     {
         minSteps = Mathf.Min(minSteps, maxSteps);
         maxSteps = Mathf.Max(minSteps, maxSteps);
 
         mapSize.x = Mathf.Clamp(mapSize.x, 2, 10);
         mapSize.y = Mathf.Clamp(mapSize.y, 2, 10);
 
         start.x = Mathf.Clamp(start.x, 0, mapSize.x-1);
         start.y = Mathf.Clamp(start.y, 0, mapSize.y-1);
         end.x = Mathf.Clamp(end.x, 0, mapSize.x-1);
         end.y = Mathf.Clamp(end.y, 0, mapSize.y-1);
 
         flowfield = GenerateField(mapSize, end);
         pathGrid = CreatePath(flowfield, mapSeed, start, end);
     }
 }
 

Comment
Add comment · Show 4 · 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 ShoCo2 · Aug 07, 2020 at 08:27 PM 0
Share

Sounds interesting, I'll see what I can do and I'll let you know here if I need any help. Thanks!

avatar image ShoCo2 · Aug 10, 2020 at 12:04 AM 0
Share

Been working on it for a bit but I've been having some trouble with implementation of the algorithm into code, are you able to point me in the right direction? Thanks!

avatar image Ymrasu ShoCo2 · Aug 10, 2020 at 04:41 AM 0
Share

Added a script to the answer (it wouldn't let me reply it; I think it was too long, oops)

avatar image ShoCo2 Ymrasu · Aug 10, 2020 at 08:06 AM 1
Share

I can't express in words how thankful I am for such a detailed response with even comments on what each element does. Reading through it all right now and I have a good grasp of how I should proceed writing it in my final project.

If you got a PayPal I'm down to give you some coffee money or something man, seriously thanks!

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

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

Related Questions

How can I get my pathfinding algorithm to know that it cant go through certain sides of tiles 1 Answer

Using A* Algorithm for Pathfinding for a 2D platformer 1 Answer

how do I add abilities(Scripts/GameObjects) to my path finding agent 1 Answer

How to connect generated points on a sphere? 0 Answers

Start/End zigzag coverage region algorithm 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