How to Make Lines Connected Point-to-Point from A to B?

[seto007]

Hello. I have been making a map navigation system meant to be similar to the one in FTL for the past 2 days. For reference, the FTL map navigation system can be seen here:

To do so, I have compiled a blueprint which places a single button (named “stars” here) in every single a quadrant of a 8 by 4 grid that makes up the map screen (with a few pixels of padding so that they don’t spawn too close to each other), with a random selection of up to 15 (usually 3-8) of these stars being made invisible after placement. From there, a random star of the 5 furthest to the left, and of the 7 furthest to the right, are made into the “start point” (seen in red) and “end point” respectively.

From there, I run the OnPaint function once with the below graph:

In case it’s tricky to follow, what this function does is get distance between the a visible star (first for each loop element) and gets it’s distance to every other star that is visible (second for each loop elements). From there, it compares the distance of the first start to every other star, and if the distance is either the shortest distance in the entire array of visible stars, or the star is within 275 pixels, it draws a line to that star to the HUD (with +20 pixels added to x and y because of the default slot position of the buttons being -20x and y with center anchors).

This produces a perfectly workable map in most instances where a player could find a path from start to end, as seen below:

However, the map generation sometimes doesn’t work as intended, with different sections of the map not being connected as can been seen below:

I’m not much experienced in programing or pathfinding, so while I wouldn’t be surprised if there’s a relatively simple solution like an algorithm that finds the shortest path between the start point and end point by comparing the points in every sector that isn’t on the left column of the grid and links them, I have no idea how I would go about setting such a thing up with the setup I’ve created.

Here are the blueprint pastebins for the [Event Graph][5], [Starting Point Creation Graph][6], [End Point Creation Graph][7], and [OnPaint Function][8] respectively in case you wanted to get a better idea of how I’ve gone about making this setup so far. Obviously it’s nowhere close to done, but that’s to be expected.

Thank you all in advance for any help provided, and for having such a helpful community!

[ClockworkOcean]

Unless you go for a special case, you’ve bitten off a chunk of what’s know as ‘the travelling salesman’ problem.

People have written PHDs on the best way to do this.

Travelling salesman problem

[seto007]

This article, based on what I’ve read so far, seems like it could be very helpful for formulating an optimal solution, so thank you for that. Tomorrow I’m going to try an automatic process based on the algorithm idea I briefly touched upon above and get back with the results if nobody presents a better solution, as the time I’ve taken to think about how to organize and structure it has resulted in some ideas that I think might be worth trying.

[UnrealSolver]

Nice thread, never knew that it’s called Travelling Salesman Problem

You can go for a workaround - create an image in f.ex. Paint in size of let’s say 5px x 100px

Now upload it, place in the UMG to check what is it’s size, if too big - make it shorter but not like 33px cuz it’s gonna be hard to calculate for you

Now you can calculate the distance between points you wanna connect, add the line image, rescale it (you’ll need a lil math), rotate it and you should get the desired effect

Obviously it’s not a standard way of doing it, it’s more a workaround which I used with 3D Cylinder with pivot at it’s bottom and so I was able to calculate and connect 2 or more points (but in 3D :P)

[seto007]

After 2 days, I have finally found a workable solution I am satisfied with!

I will try to give the best and simplest explanation I can, but considering how long the code in question is (link below, but WARNING: extreme spaghetti code), I might miss something important:

To start, the way the stars are set up is very deterministic, since they all inhabit a single sector & are placed in those sectors in ascending order (Star 1 is in sector 1, Star 2 sector 2, etc)

As such, their placement can be formulated into a grid as shown in the top image below.
With this knowledge, it is very easy to get the the active star’s location in relation to every other star. In the bottom image, it is done using Star 9, and also contains the accompanying math for any star shown beside it in notepad:

Using the active star’s name for reference, I can create an array of all the visible surrounding stars as such:

From here, I can get the 2-way length by dividing the distance of the of a nearby star to both the active and ending star by 2, and then add it to an array and draw a line to the shortest 2-way length in the array. If there are no active stars to be drawn to, then I instead go to the next pass; by the final pass, there is guaranteed to be at least one surrounding star:

Finally, the process will repeat until the end star is contained within the surrounding stars:

[Here’s the link to the full code.][6]
Again, expect extreme spaghettification & length xP

More optimal methods might exist, but I’m currently satisfied as is

[seto007]

Hey, just thought I’d let both of you guys know that I’ve found a workable solution which I’ve posted here, in case you were interested and didn’t get a notification.

[ClockworkOcean]

Ah, well done. Like I say, special case makes it more manageable

[Everynone]

WARNING: extreme spaghetti code

This is glorious! o_O

---

I built something somewhat similar once but in 3d; where every star had a fixed number of anchor points and those points would drive the logic of who can connect to whom, how many times and whether the path can be travelled both ways.

Sounds fun but it wasn’t.

[tincho79]

Is there an active link to the full code @seto007 ? Im traying a similar aproach and im stuck