My images are very placeholder, please forgive that. This is all done in a map widget (UMG), but I think this question is mostly about array math. The green face is the players location, AI icons are possible places to jump to, and the ring is the visual indicator for the range that you can move.
I want to be able to click to a system outside of my jump range and have it plot the shortest course to that location.
Background: All of the points are in an array, and all the points on the map are aware of their position in the array, and I have methods to check the distance between points when clicked all already implemented. The map is fully functional and traverseable other than plotting courses.
I was thinking maybe something with vectors and the radius of the jump range? Any ideas are appreciated
Why don’t you just detect the closest point in the range to the selected destination? After that, you can check if the distance between the destination and that point is equal or less than the radius of your range, and if not, you can do the same for the next closest point in the range. Have this checking algorithm in a loop and call it until the condition is met.
Btw you can detect the closest point in the range to the destination that’s outside by checking each one’s distance. To do that, you can subtract the destination loc from the candidate point and get the vector’s magnitude by using the length node, and then do the same thing for the next candidate but store the previous one’s value, and override the one that has a greater magnitude in the next comparison between two candidates. The candidate that wins the last comparison is the closest one to the destination
That’s close to what I was thinking! But unfortunately I ran into issues, for example going left through the center of the galaxy, or to the right to the distant arm where it would think the closest point is in a loop and it would crash. I could probably fix it by increasing the jump range for every ship, but it’s meant to be an upgrade able component of the players ship.
tldr some cases where the pathfinding encounters a void it doesn’t know how to find a nonlinear path
To overcome this issue, you can increase the Max Loop Iteration Count setting from the project settings. But if that won’t suffice, another great way to avoid getting that infinite loop error is spreading the iteration processes by using delays / timers. For example, if you get a for loop inside another for loop, set the outer one to iterate 10 times and the inner one to 1000 times, and put a really short delay in between like 0.000001 seconds, the code inside the inner for loop will have been iterated 10,000 times in a matter of 0.00001 seconds, which is still instant! While your PC may not be able to handle to iterate a heavy task 10,000 times instantly.
I already have the iterations turned up, that isn’t the problem really.
If you’re at the green position and you want to go to the red position, that solution will only look for paths in a vector towards the red x, instead of taking the yellow path around.
I understand how to plot a path across an empty room, but obstacles (empty spaces in this case) require a different solution.
There’s no super-simple solution to this problem. You need a pathfinding algorithm.
The most straightforward solution is probably the A* algorithm :
You can either implement it yourself, or use the general-purpose implementation provided by the Engine (in GraphAStar.h). The builtin solution is very generic and requires some setup to adapt to your own classes. See below how it can be used :
