Travelling salesman problem

General Recast graph
#1

Hello,

I have a TSP and I would like to use recast to create the graph that the TSP will have as a playfield, then find the answer to TSP using some algorithm and finally use RichAI to travel to each point one after the other properly.

Any suggestions as to how to feed the TSP solver the positions through the recast graph’s distances etc?

#2

In that case you will need to calculate a path between every pair of points in your TSP graph, and apply post-processing modifiers to the path to get a better distance measurement (see FunnelModifier on Documentation).

#3

Do you mean calculate every permutation of all the points first?

#4

No, just take every pair of points.

  • For each pair of points
    • Calculate the optimal path between them using this package
    • Insert that edge into your TSP graph
  • Use your TSP solver to calculate the best TSP path.
  • Feed the points, one by one as destinations to the movement script.
1 Like
#5

Yeah, isn’t that all the permutations needed? Cause you calcualte all the distances first from all potential routes in order to feed it to the TSP solver

#6

By permutations, I assumed you meant all N! permutations instead of just the N^2 pairs of points? Or am I misunderstanding something.

1 Like
#7

Yeah the N^2 I meant.

#8

Ok. Which part are you having trouble with?

#9

None I was just wondering whether there was a faster way that was the norm and I couldn’t think of cause even N^2 will be a lot of A* calls.

#10

You could also use Documentation which should be faster.

#11

I have yeah, I originally thought it would be a TSP solver but when I saw the example realized

#12 
        Vector3[] points = new Vector3[targets.Length + 1];
        OnPathDelegate[] pathDelegates = new OnPathDelegate[points.Length];
        MultiTargetPath[] multiTargetPaths = new MultiTargetPath[points.Length];

        for( int i = 0; i < targets.Length; i++ )
        {
            points[ i ] = targets[ i ].transform.position;
            pathDelegates[ i ] += PathDelegate;
        }

        points[ targets.Length ] = m_Character.transform.position;

        for( int i = 0; i < points.Length; i++ )
        {
            multiTargetPaths[ i ] = MultiTargetPath.Construct( points[ i ], points, pathDelegates, OnPathComplete );
            m_Seeker.StartPath( multiTargetPaths[ i ], OnPathComplete );
        }

I suppose the above is wrong for multiple reasons but the main one is whether I can calculate the paths without using any seeker or whether I need to add a seeker per point so that I can calculate them all simultaneously as this will stop for each start path.

#13

You can calculate them without using a seeker: see the bottom of this page: Documentation.
However you probably want to post-process it using the funnel modifier. You can call seeker.PostProcess(calculatedPath) in your OnPathComplete callback to do that.

[EDIT] Actually. Post processing it is kinda tricky. When the Seeker calculates the path itself it cooperates with the path to post-process the multiple paths individually. When the path is not calculated with a seeker, it will only be able to post-process the “main” path, which for a MultiTargetPath is the shortest one.
You will need to call seeker.PostProcess inside your PathDelegate callback, not inside the OnPathComplete callback.

1 Like
#14

Will I really need the funnel modifier though? Since TSP will calculate all the paths based on distances, I will have my result before needing to call the post processing.

Cause:

  • Calculate all edges in each pair of points
  • Put them TSP
  • Use the “ordered” list to go from one point to the next - these have been previously calculated no?
#15

You do not necessarily need it, but it will give you more accurate results. The length of a non-post-processed path on a recast graph can be a bit off since the path just passes through triangle centers.

#16

Ah yes ofc!

I just realized I didn’t use this in another project of mine which would really need it… facepalm

I’ll fix that during normal working hours :slight_smile:

1 Like