0 Favourites

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

  • 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...

  • 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.

  • 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.

  • Construct 3

    Buy Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Buy Now Construct 3 users don't see these ads
  • 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.

  • Pick closest with filtering should make things a little easier.

  • 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:

    You can also find some examples of astar done in events if you search my posts. Possibly could be useful.

  • 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.

    Its lighting fast. But can probably still be optimised more.

Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)