GMS 2 Path generation without V shapes or X crosses.

Discussion in 'Programming' started by Doulos, Jul 13, 2019 at 12:42 AM.

  1. Doulos

    Doulos Member

    Jun 8, 2019
    I am creating random paths of a specified length in a rectangle.
    The goal is a dynamic tower defense map. (ie, there is a path for the bad guys to follow, and space in between paths to put towers.)

    I have a mostly working Path generator. Generally speaking, a path is created without a major issue most of the time.

    Good looking path Example.
    There is 1 close spot there in the middle, but good enough.

    I have 2 big issues right now.
    1) Two path sections get too close to each other in parallel, leaving too little room for towers between. This is usually a V shape. But also could be two curves in paths. #1 here is usually not bad enough to be game breaking.
    But sometimes it is game breaking bad.

    2) The path crosses itself. This is actually very rare already. On the rare occasions when it happens #2 is almost always 100% game breaking.

    I am attempting to rewrite this section of my code to resolve both of these issues.
    Overview of current logic...
    1. Make path manually with only 1st and last 2 points At the location which I want to be the start and end of the path.
    2. Set constants defining limits of Box within which I want my path to stay.
    3. Randomly choose X and Y in box rounded to nearest 32.
      1. This was my attempt to ensure room between paths.
      2. I tried bigger numbers and it did not really help.
    4. Place X,Y in path at place with shortest length.
      1. This was my attempt to ensure no crosses.
      2. Made script to do this looping through each position in path.
    5. Check Length, continue until desired length.

    My current plan to fix the 1st big issue...
    1st step; Ensure minimum distance.
    1. After choosing a random X and Y.
    2. Add a bunch of points in a copy of the path at intervals to get a high-res path.
      1. Thinking ~500 should be plenty? At ~6000 length paths right now, That would give me ~12 pixel accuracy; I think.
      2. Question? Assuming I am making a script for this...
      3. Am I better off creating an array? Or create a new path?
    3. Find closest point, which would be roughly equivalent to perpendicular to path.
    4. Get the distance.
    5. Ensure that point is distance > Tower width + Enemy width + Tolerance
      1. Tolerance being a number bigger than the error I think the distance is giving me.
    6. Insert point in original low-res path.
    2nd step; Check for Acute Angle.
    1. After point inserted in shorted length position.
    2. Check the angle of the new point vs the 2 adjacent points on the path.
    3. If this angle is too small (degrees to be determined later), then I know the path is overlapping itself in a V shape.
    4. Then I would inject 2 points adjacent to the new point to create more of a U shape.
    Hopefully this fix allows the shortest path code to ensure no Crosses too? Will have to test to see.

    This seems very processor intensive. I have already had to split up creation once because nothing happened. It seemed like the code just ran out of time in 1 frame? Not sure what it was, but making the object do 1 portion at a time then alarm until next frame worked.

    Am I just far too concerned with efficiency / memory / processor time?

    Thus? Is there a function for this? Find the distance to the path from X,Y? Not a point on the path, but the perpendicular point along path itself?

    If not, other ideas are also welcome.
  2. the_dude_abides

    the_dude_abides Member

    Jun 23, 2016
    I can offer a way to avoid a path crossing itself. I won't say it's the only way, or the best, but it will work.

    If you go to they have a script called "line_intersection", which does as it's name says: returns whether two lines cross. So you would take one line as the last path point to the new one you want to create, then loop through the previous path points and treat them as the second line. If you get to the current path points without a positive result, then you know it isn't crossing itself. If you get a positive then you know you need to find a new position for the final path point.

    One thing to note: You would have to ignore testing 3 & 4 against 4 & 5 in this way, because the end point of the previous line is the same as the start point of the next line. Which would give a positive result even though they aren't crossing as such. To check that the last two lines aren't crossing would basically be seeing if the angle from 4 to 5 is not the exact reverse of the angle from 3 to 4 ( 3 to 4 is 45 degrees, and 4 to 5 is 225 etc)

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice