Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Procedural Path Generation In A Grid

Discussion in 'Scripting' started by CunningGrayFox, Feb 28, 2015.

  1. CunningGrayFox

    CunningGrayFox

    Joined:
    Jan 7, 2014
    Posts:
    24
    Long story short I'm building a procedural generator for the level map in my game. I currently build a grid data structure as an array of cells. Originally, I was trying to generate the longest simple path from a start point to an end point however I was informed by the internet that such a problem was NP-Complete.

    To quickly move past the theoretical stuff and get to coding I decided on A* pathfinding with obstacles placed on the grid to lengthen the path a bit. This would give me a path that is roughly half of the length of the longest simple path which isn't bad however the path is extremely uninteresting as it just basically moves from one corner of the grid to the opposite corner in a more or less diagonal fashion leaving a lot of empty cells.

    I was thinking of spicing the path up by maybe messing with the accuracy of the distance estimations of A* or maybe switching around the placing of the end point as the pathfinding process runs itself but I just don't know if those are good ideas.

    Are these bad ideas, programmatically speaking? Do I ditch A* entirely and use some other method of graph search? Do I forget graph search algorithms and do something entirely different?

    Help me spice up the path!
     
  2. Antistone

    Antistone

    Joined:
    Feb 22, 2014
    Posts:
    2,836
    A* is designed to find short paths; it's probably not a good algorithm if you're trying to find long ones.

    How large is your grid, and how often do you need to calculate a path? Finding the longest path is NP-complete, but if your grid is small enough and you recalculate rarely enough you could do it anyway.

    I doubt that longest path is really what you want, though; if your map is mostly open, that's basically going to zig-zag back and forth across the entire length of the map over and over.

    Why don't you talk a bit more about what you're trying to accomplish? What are you using the path for? What sort of qualities would make it "interesting" for your purposes?
     
    CunningGrayFox likes this.
  3. CunningGrayFox

    CunningGrayFox

    Joined:
    Jan 7, 2014
    Posts:
    24
    So, the path is for an automated player avatar to move from level to level.

    The map is a level map for a match three game.

    I know its overkill to run such complex logic to generate something that every other game just reduces to a static sprite, however, I really wanted this to be different from the cookie cutter match three's that you find on the app stores. The map seed is going to be based on player number + another number like DateTime.Now. Each player gets their own unique path and all the levels on said path would be procedurally generated as well(obstacles, win conditions, layout, etc.). I figured for a single indie dev this is probably the best route, at the game level, to make this game somewhat unique. Some of the win conditions and obstacles will also be different but that uniqueness exists at a lower level.

    I wanted to include 200 levels initially and then expand later. What I'm currently doing is building a grid data structure of 20 points, grid_width=4, grid_height=5. Each of those 20 cells will have a 15x15 grid inside of it that will have the actual path the automated player will walk. The path that I'm trying to generate at the 4x5 level will dictate start and end points for the 15x15 grid paths.

    So, to put it in visual terms I stitch all the 15x15 grids together into a massive grid and from that I will build a mesh of tiles to be rendered as the actual map the player sees. Each 15x15 will have 10 levels in it. The path should only be calculated once when the player first starts the game.

    Regardless, in both grids I will encounter the same issue of uninteresting path if I use A*.

    The longest path could work visually because at the 15x15 level you would use another procedural algorithm to generate path since there only needs to be 10 levels on the 15x15. This would leave space for trees and empty spaces etc.

    Most of all, thank you for the reply Antistone. Trying to build this in a vacuum has me wanting to smash my whiteboard over my own head and eat my calculator.
     
    Last edited: Mar 8, 2015
  4. Antistone

    Antistone

    Joined:
    Feb 22, 2014
    Posts:
    2,836
    Well, it sounds like you want something random, which is an important requirement to note--typical path-finding algorithms are inappropriate if you need the outcome to be different each time.

    Conceptually, I'd try something like the following:

    Start at your defined start space
    Move one space in a random direction
    If that random space happens to BE the end space, you're done!
    Otherwise, check whether ANY valid path exists from your chosen space to the end space without crossing your path so far (e.g. using breadth-first search)
    If not, back up and choose a different random direction
    Treat your random space as the new start space
    Treat your old start space as an obstacle
    Recurse


    If that tends to produce results that are too squiggly for your taste, change the random weights so that it's more likely to move in the same direction that it moves on the previous step.
     
    CunningGrayFox likes this.
  5. CunningGrayFox

    CunningGrayFox

    Joined:
    Jan 7, 2014
    Posts:
    24
    I currently have something similar to what you conceptually laid out except its done in a loop using a stack as the counter and a "visited" boolean as the backtracking/escape condition. What I currently have produces a more maze like pattern with several deadends, however, it doesn't use BFS to look for any valid paths from current location to the end point.

    I think that BFS check may be the key to eliminating all these dead ends I'm producing. I'll also try a recursive version of what I currently have.

    Thank you for the new approach. I'm going to implement and report back.
     
    Last edited: Mar 1, 2015
  6. CunningGrayFox

    CunningGrayFox

    Joined:
    Jan 7, 2014
    Posts:
    24
    So I began working on something when I realized I didn't really need to BFS every time I entered a new vertex. I ended up implementing a DFS with an escape condition for the path once it reaches the target point. The DFS backtracks when it hits a dead end so by the time you hit the final point your stack is full with only those points that actually makeup the path to your location. After, I just pop them off one by one as I write them to a list.

    Still playing with the seed to achieve MAXIMUM SQUIGGLOCITY!