User Tag List

Results 1 to 5 of 5

Thread: Calculating the shortest path in RANDOMLY generated maps

  1. #1
    Clicker Fusion 2.5 (Steam)Fusion 2.5 Developer (Steam)Android Export Module (Steam)HTML5 Export Module (Steam)
    Literswater's Avatar
    Join Date
    Apr 2014
    Posts
    164
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Calculating the shortest path in RANDOMLY generated maps

    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.

    game.jpg

    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.

  2. #2
    Clicker Fusion 2.5 Developer

    Join Date
    Jul 2008
    Posts
    1,302
    Mentioned
    13 Post(s)
    Tagged
    0 Thread(s)
    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.


  3. #3
    Clicker Fusion 2.5 (Steam)Fusion 2.5 Developer (Steam)Android Export Module (Steam)HTML5 Export Module (Steam)
    Literswater's Avatar
    Join Date
    Apr 2014
    Posts
    164
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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.

  4. #4
    Clicker Fusion 2.5 Developer

    Join Date
    Jul 2008
    Posts
    1,302
    Mentioned
    13 Post(s)
    Tagged
    0 Thread(s)
    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.

  5. #5
    Clicker Fusion 2.5 (Steam)Fusion 2.5 Developer (Steam)Android Export Module (Steam)HTML5 Export Module (Steam)
    Literswater's Avatar
    Join Date
    Apr 2014
    Posts
    164
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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:

    game.jpg

    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.

Similar Threads

  1. Replies: 35
    Last Post: 23rd May 2017, 08:33 PM
  2. Google Maps extension. como posso usa a extensão Google Maps?
    By marcorios7 in forum Android Export Module 2.5
    Replies: 7
    Last Post: 7th November 2015, 08:01 AM
  3. Timer Record and in the order of shortest time
    By marcorios7 in forum Android Export Module 2.5
    Replies: 5
    Last Post: 14th April 2015, 05:51 PM
  4. Randomly Generated World
    By LemonyLime in forum Multimedia Fusion 2 - Technical Support
    Replies: 0
    Last Post: 8th January 2012, 06:47 AM
  5. File Object - Create Maps in maps?
    By DJ_Wild in forum Multimedia Fusion 2 - Technical Support
    Replies: 3
    Last Post: 15th August 2011, 10:17 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •