How do I calculate routes between points (star map)?

Get help using Construct 2

Post » Tue Nov 15, 2016 12:43 pm

I haven't really ventured into pathfinding beyond Construct 2's built in behaviors, but I've found that said behavior doesn't (seem to?) suit what I'm trying to accomplish.

I have a star map of sorts in my game project. I want to calculate a path between a start and destination star. There's a maximum "jump range", so I'm trying to calculate a path through a map of stars to reach the destination point. It seems like a pretty common thing in games- Elite: Dangerous, Stellaris... in fact most space strategy games... all feature this sort of pathfinding.

Where would one start in implementing such a system? Bit of a broad question I know, but after spending some time looking at pathfinding solutions online I'm struggling to see how it works when you have points without specific paths between them...
B
11
S
2
Posts: 13
Reputation: 601

Post » Tue Nov 15, 2016 1:03 pm

With pathfinding you can always set a destination as long as you know the destination. If you don't have a specific path to a final destination then it will pick the shortest route, you can see this visually if you enable the nodes.
B
46
S
16
G
78
Posts: 2,166
Reputation: 46,349

Post » Tue Nov 15, 2016 3:44 pm

@plinkie His situation is a different scenario than regular pathfinding. There are no obstacle, and the only limiting factor is the distance between nodes.

There are currently no official plugins in C2 that would enable him to do this, so I guess he needs to fallback to an event-based solution, or maybe a custom plugin...

Basically, you need to gradually and recursively search available nodes (that are within reach) and try to follow the shortest path.
B
71
S
30
G
25
Posts: 984
Reputation: 19,503

Post » Tue Nov 15, 2016 11:06 pm

Magistross wrote:@plinkie His situation is a different scenario than regular pathfinding. There are no obstacle, and the only limiting factor is the distance between nodes.

There are currently no official plugins in C2 that would enable him to do this, so I guess he needs to fallback to an event-based solution, or maybe a custom plugin...

Basically, you need to gradually and recursively search available nodes (that are within reach) and try to follow the shortest path.


I hate to ask but... how would one do this? I've been reading up on "A*" pathfinding and had a feeling that would be the key but I'm not entirely sure- it seems to be grid based in most examples.
B
11
S
2
Posts: 13
Reputation: 601

Post » Wed Nov 16, 2016 12:04 am

Pick closest with filtering should make things a little easier.
Image ImageImage
B
169
S
50
G
174
Posts: 8,322
Reputation: 110,788

Post » Wed Nov 16, 2016 3:38 am

A star isn't restricted to grid based, and it should work well for what you want to do.

Here's an awesome reference about it:
http://www.redblobgames.com

You can also find some examples of astar done in events if you search my posts. Possibly could be useful.
B
92
S
32
G
109
Posts: 5,291
Reputation: 70,993

Post » Wed Nov 16, 2016 10:50 pm

Because the shortest path will always contain only 3 nodes, there is always only 1 shortest path between 2 points ....

Here a different approach.
This solution finds a path that contains as much nodes as possible between start and end, with a perception of the shortest path.

https://www.dropbox.com/s/degglr7bv9w03 ... .capx?dl=0

Its lighting fast. But can probably still be optimised more.
B
33
S
18
G
28
Posts: 2,493
Reputation: 20,950


Return to How do I....?

Who is online

Users browsing this forum: Armench, Artcadev, farsen, mariusvm, TheRealDannyyy and 12 guests