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

Get help using Construct 2

### » 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

### » 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
45
S
15
G
73
Posts: 2,006
Reputation: 43,394

### » 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
67
S
28
G
24
Posts: 970
Reputation: 18,675

### » 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

### » Wed Nov 16, 2016 12:04 am

Pick closest with filtering should make things a little easier.
B
168
S
50
G
163
Posts: 8,221
Reputation: 105,061

### » 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
91
S
31
G
103
Posts: 5,234
Reputation: 67,754

### » 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
27
Posts: 2,441
Reputation: 20,346

### Who is online

Users browsing this forum: Apollo14, ivanski1983, KTML5 and 5 guests