Calculating the shortest path in RANDOMLY generated maps

Welcome to our brand new Clickteam Community Hub! We hope you will enjoy using the new features, which we will be further expanding in the coming months.

A few features including Passport are unavailable initially whilst we monitor stability of the new platform, we hope to bring these online very soon. Small issues will crop up following the import from our old system, including some message formatting, translation accuracy and other things.

Thank you for your patience whilst we've worked on this and we look forward to more exciting community developments soon!

Clickteam.

    I'm knee deep in a dark ocean of fast loops that make a randomly generated map for an Android game I'm developing. I wouldn't ask of you to spill out how to exactly achieve this, but I would really appreciate at least some directions of where to look.

    Please login to see this attachment.

    About how the map is generated:

    • EVERY dot is randomly positioned in the map
    • There are 1-3 Green dots that tend to be in the center
    • Many Blue dots are generated everywhere
    • 1-6 dots are Red

    I already got all of this to work properly, but was a fool to believe that was the hardest part..

    The goal:
    One red dot must go to the nearest green dot, using the blue dots as nodes. Out of 4 different paths, the user must click on the shortest one.

    I expected this to be easy with all the path finding extensions out there, but I've seriously underestimated the challenge of this due to the fact everything is randomly generated and positioned. Again I won't ask someone to think it all through for me, but it would be great if someone could tell me what extension or widget would be most recommended for this. There are so many options out there (advanced path movement, widgets, now I'm experimenting with Wargame Map Object), and simply knowing a specific one is my best bet would save me a lot of time.

    Please login to see this link.
    (because you can)

    Edited 2 times, last by Literswater (July 15, 2016 at 2:18 AM).

    It's not logically possible.
    What you're asking is the equivalent of if you have a map with lots of cities on it, and you want to drive from one city to another, via some other cities, but you don't know where any of the roads are. You need to define which dots are directly connected to each other, which is not going to be straight-forward. After that, you could use A* or Dijkstra's algorithm for pathfinding between dots (also not straight-forward).

    For example, you could say that each node is connected to its nearest two neighbours. In your example, that would at least result in all the dots being connected, but it's not guaranteed (see the second image), and some nodes will not be connected that intuitively probably should be (see the dotted lines in the first image). You could add more links by connecting each node to its three nearest neighbours, but then you'll find that some nodes become connected that probably shouldn't be (see the top left area of the third image), and you may still be left with other nodes that should be connected but aren't.

    Please login to see this picture.

    Edited 2 times, last by MuddyMole (July 14, 2016 at 1:12 PM).

    All nodes are connected to all nodes. You could basically go from the very left node to the far right while ignoring the ones in between.

    This is why I believed it's best to try and make it work with the Advanced Path Movement extension, since that seems to make branches like these possible.

    Please login to see this link.
    (because you can)

    That doesn't sound right...
    I'm assuming you can't just go straight to the target node without going through any other nodes first, or that would obviously be the shortest path.
    So in that case, the next shortest route will always be from the start, to one other node, and from there to the target node - there's no reason to detour via any additional nodes, as that would only make the path longer.
    Therefore, all you have to do is for each node, find the distance from the start point, and the distance to the target node, and add the two together - and then whichever node has the lowest total, that is the one node that the path goes through. You could do that with a single ForEach loop.

    Edited once, last by MuddyMole (July 14, 2016 at 11:08 PM).

    Dang you're right.. I've completely gone off track somewhere in the process and am not making any logical sense. The start and end themselves are the always the shortest path. I don't know why I've overlooked this and the direction I'm thinking in isn't even the puzzle I'm supposed to make. My apologies for the vagueness. This is what the player is supposed to do. I'll also edit my first post in order to avoid confusion of other people who want to assist:

    Please login to see this attachment.

    So it's actually simpler than whatever my mind has been drifting off to. It's a brain trainer that gives 4 options. So 4 paths, of which 1 is the shortest. The shortest one is the correct answer. I figured to create an invisible object and have it move along the given paths while constantly increasing its Value A with 1 until it reaches a Green, and the correct answer is calculated by looking which of those invisible objects have the lowest A Value.

    Please login to see this link.
    (because you can)

    Edited once, last by Literswater (July 15, 2016 at 2:21 AM).

Participate now!

Don’t have an account yet? Register yourself now and be a part of our community!

Register Yourself Login