Longest Path + Branching

I'm trying to find a solution for a longest path problem that includes branching.

keep in mind that i have almost zero background on programming and have learned everything by myself, most of the articles that i found were a little too theory-heavy

i use a lot of A* on my projects, and have seem that there is something we can do with A* to find longest path, but i couldn't wrap my head around it...

Well, here is my problem:

I have this little Snake:



and i need to find the longest path possible to move(in this case it starts at the zero and goes to 7).

The problem is, the longest path should be like one of this:



and the problem comes to branching and looping.

the basic idea is that the path will keep going until it has nowhere to go or only cells that have already been seen.

but the idea of being seen should only count towards that branch...

and if there were only one or two branches, that would be alright...but the idea is that you may have branches...that may have branches...that may have branches...and I need a form of checking only if this "family" of branches have checked that spot.

I have a few ideas, but most seem to be not optimal and I would like to know if anyone has a good source and/or algorithm that may solve this!

TL; DR : anyone has a source/algorithm to find the longest path with loos and branches, without a branch going through a spot twice?

 

Use A*, but negate the heuristic.

A* finds the path with the shortest heuristic distance. By negating it you'd make 'large' values seem 'small' since -1000 < -100... where as 100 < 1000.

That or sort your open list backwards.

You can see in my implementation of A*:
https://github.com/lordofduct/space...ter/SPPathfinding/Graphs/AStarPathResolver.cs

There is no checking of shortest distance anywhere. The entire algorithm is predicated on the '_open' binary heap sorting with the nearest nodes on top. By sorting backwards (or making distance backwards) you tend to move away from the goal.

Problem here is that if you have an opened ended graph, it'll always move away. Your graph has to be a closed set so that it innevitably reaches the goal, just going the longest way around possible.

There may be some other caveats I'm not thinking of off the top of my head... but I'm at work right now, and don't have my environment in front of me to run any actual tests. If you haven't given it a try by the time I'm back at my unity machine, I'll check it out.

 

huuumm, levels of code I wish I had

no matter how much I think about it, the A* for long path doesn't make sense in my head when I'm using loops and branches...not saying it doesn't work, just that I don't understand

i will work my little monkey head off to try something out like this, and go through your code a few times, as my A* implementations are rather simple and low lvl

i do have an idea using some structs, that is not really hard, but probably not optimal.

 

I'm pretty sure you can't modify A* to find the longest path in any reasonable way.

The longest path problem is NP-complete, which means there is no "good" way to do it (as far as anyone in the world currently knows). You basically have to check every possible path (including overlapping paths). Note this means the time to find the path may increase exponentially with the size of the graph.

You should probably use a dumb depth-first search with no optimizations.


Tangent:

The reason that shortest-path is "easy" and longest-path is "hard" is because shortest paths are decomposable: if the shorest path from A to B happens to go through C, then it will always* be the shortest path from A to C concatenated with the shortest path from C to B. For longest paths, this is not true: if you take the longest path from A to C, and then concatenate the longest path from C to B, the result might not be a path at all (that is, it might cross itself).

The snake "wants" to just spin around in a circle forever, because that would be longer than actually going to the destination. But that's not a "path", because "path" implies that you don't visit any single node more than once.

*The reason for that is actually a hidden assumption in the problem statement: the graph is normally assumed to have no negative-cost cycles. (That is, there is no way to get from X back to X for a net-negative cost.) If negative-cost cycles might exist, then shortest-path is just as hard as longest-path. (Conversely, if positive-cost cycles are guaranteed not to exist, then longest path becomes easy!)

 

So I'm here to confirm what Antistone said.

Though it doesn't crash (because my graph is a closed set), the path isn't necessarily the longest.

It's just 'not the shortest'.

Example:

(green is start, red is goal, red line is the path it takes)

Note that in this it can only go through doors into different rooms, so that impacts the path.

Here it is ignoring doors:


It's still not the longest path, but it does snake all over the room. This is primarily because A* does not like to return to a node it has already been to. Otherwise you'd get what Antistone was talking about with it spinning around on itself infinitely.


...

[edit]
Actually playing with this some more... it's pretty close to the longest path it could take. Maybe not perfectly... but pretty dang close.

In my first image, upon looking closer. It can't really go into any of those other rooms because once in you'd have to back track to get to the goal (which would make you walk back through the door you came, which A* avoids returning to tiles).

Even when it seems to go straight into room 4 and right out again... you may think it could wander around that room some... but it can't because there's only 1 tile there, it'd have to cross over that 1 tile to wander around room 4.

Even in the 'ignore walls' examples. The gaps that are missed are probably just because the path it decided on up to there wouldn't allow a successful path because it'd require criss-crossing otherwise.

So yeah... not perfect maybe... but kind of is the longest path.

And since your graphs are more linear rather than open world like my map is... it might actually work out even nicer.

Try negative heuristic out, see if you like it?

If you go through my code, you can ignore the region titled "ISteppingPathResolver Interface". It's just a duplicate of the Reduce method that could be done 1 step at a time in a coroutine or something (for paths that are extra long, and can't be threaded, so would otherwise lock up a frame). The algorithm as a whole works without that portion of code.

...

Anyways, here's the code I slapped together for the example to see if negative heuristic works (it ain't pretty, but I was just trying it as proof of concept):

Code (csharp):

1.  
2. using System.Collections;
3. using System.Collections.Generic;
4. using UnityEngine;
5. using UnityEngine.Video;
6. using UnityEngine.UI;
7. using UnityEngine.SceneManagement;
8.  
9. using com.spacepuppy;
10. using com.spacepuppy.Dynamic;
11. using com.spacepuppy.Scenes;
12. using com.spacepuppy.Scenario;
13. using com.spacepuppy.Serialization;
14. using com.spacepuppy.Serialization.Json;
15. using com.spacepuppy.Graphs;
16. using com.spacepuppy.Pathfinding;
17. using com.spacepuppy.Tween;
18. using com.spacepuppy.Utils;
19. using System.Linq;
20.  
21. using com.mansion.SceneGenerator;
22.  
23.  
24. namespace com.mansion.DebugScripts
25. {
26.  
27.     public class zTest01 : SPComponent
28.     {
29.  
30.         public SceneInfo Scene;
31.         public float Scale = 1f;
32.         [InsertButton("Click Me", "DoWork", PrecedeProperty = false)]
33.         public bool IgnoreDoors;
34.  
35.         private Example<TileInfo> _example;
36.  
37.         public void DoWork()
38.         {
39.             if (Scene == null) return;
40.  
41.             _example = new Example<TileInfo>();
42.             _example.Solve(new TileGrid(Scene.Tiles, IgnoreDoors), Scale);
43.             UnityEditor.SceneView.RepaintAll();
44.         }
45.  
46.         private void OnDrawGizmos()
47.         {
48.             if(_example != null)
49.             {
50.                 _example.DrawGizmoPath();
51.             }
52.         }
53.  
54.  
55.  
56.  
57.  
58.  
59.         private class Example<T> where T : Component
60.         {
61.  
62.             private IList<T> _tiles;
63.  
64.             public void Solve(IGraph<T> graph, float scale)
65.             {
66.                 var astar = new AStarPathResolver<T>(graph, new MyHeuristic(scale));
67.                 astar.Start = graph.PickRandom();
68.                 astar.Goal = graph.Except(astar.Start, EqualityComparer<T>.Default).PickRandom();
69.                 _tiles = astar.Reduce();
70.             }
71.  
72.             public void DrawGizmoPath()
73.             {
74.                 if (_tiles == null) return;
75.                 if (_tiles.Count < 2) return;
76.  
77.                 Gizmos.color = Color.red;
78.                 for (int i = 1; i < _tiles.Count; i++)
79.                 {
80.                     Gizmos.DrawLine(_tiles[i - 1].transform.position.SetY(1f), _tiles[i].transform.position.SetY(1f));
81.                 }
82.  
83.                 Gizmos.color = Color.green;
84.                 Gizmos.DrawSphere(_tiles[0].transform.position.SetY(1f), 0.5f);
85.  
86.                 Gizmos.color = Color.red;
87.                 Gizmos.DrawSphere(_tiles[_tiles.Count - 1].transform.position.SetY(1f), 0.5f);
88.             }
89.  
90.             private class MyHeuristic : IHeuristic<T>
91.             {
92.  
93.                 public float scale;
94.  
95.                 public MyHeuristic(float sc)
96.                 {
97.                     scale = sc;
98.                 }
99.  
100.                 public float Distance(T x, T y)
101.                 {
102.                     return Vector3.Distance(x.transform.position, y.transform.position) * scale;
103.                 }
104.  
105.                 public float Weight(T n)
106.                 {
107.                     return 0f;
108.                 }
109.             }
110.  
111.         }
112.  
113.         private class TileGrid : IGraph<TileInfo>
114.         {
115.  
116.             private IGraph<TileInfo> _grid;
117.             private bool _ignoreDoors;
118.  
119.             public TileGrid(IGraph<TileInfo> sub, bool ignoreDoors)
120.             {
121.                 _grid = sub;
122.                 _ignoreDoors = ignoreDoors;
123.             }
124.  
125.  
126.             public int Count { get { return _grid.Count; } }
127.  
128.             public bool Contains(TileInfo node)
129.             {
130.                 return _grid.Contains(node);
131.             }
132.  
133.             public IEnumerator<TileInfo> GetEnumerator()
134.             {
135.                 return _grid.GetEnumerator();
136.             }
137.  
138.             public IEnumerable<TileInfo> GetNeighbours(TileInfo node)
139.             {
140.                 foreach(var n in _grid.GetNeighbours(node))
141.                 {
142.                     if(_ignoreDoors)
143.                     {
144.                         yield return n;
145.                     }
146.                     else
147.                     {
148.                         if (n.Room == node.Room)
149.                         {
150.                             yield return n;
151.                         }
152.                         else if (n.Doors != WallSide.None && node.Doors != WallSide.None)
153.                         {
154.                             yield return n;
155.                         }
156.                     }
157.                 }
158.             }
159.  
160.             public int GetNeighbours(TileInfo node, ICollection<TileInfo> buffer)
161.             {
162.                 int cnt = buffer.Count;
163.                 buffer.AddRange(this.GetNeighbours(node));
164.                 return buffer.Count - cnt;
165.             }
166.  
167.             IEnumerator IEnumerable.GetEnumerator()
168.             {
169.                 return _grid.GetEnumerator();
170.             }
171.         }
172.  
173.     }
174.  
175. }
176.  

Note how I use the 'Scale' variable to negate the heuristic.

 

well i actually did use branches

that being said, it's probably only functional because:
A: it's a limited and small number of vertices
B: there is not that much of open paths.

i'm pretty sure it's not optimal, clean or even "smart", but it solves my problem and has a pretty good runtime(need to test with more vertices, but i think it'll be ok within my scope)

i used the basics of A*, ignoring any values as the path is somewhat predetermined by the next available cells.

in the end of the code i throw out a shuffle, because i didn't figure out how to settle ties for the longest path, but should not matter for the code in question.

this is what i did(ignore the update, as it was just a test):

Code (CSharp):

1. public class PathFinding : MonoBehaviour
2. {
3.  
4.     Core currentCore = null;
5.  
6.     private void Update()
7.     {
8.  
9.         var core = Snake.selectedCore;
10.         if (core != currentCore)
11.         {
12.             currentCore = core;
13.             var path = PathOrder();
14.             foreach(var mCore in Snake.cores)
15.             {
16.                 if (path.path.Contains(mCore))
17.                 {
18.                     mCore.distance = path.path.IndexOf(mCore);
19.                 }
20.                 else
21.                 {
22.                     mCore.distance = 0;
23.                 }
24.             }
25.         }
26.     }
27.  
28.     public static Branch PathOrder()
29.     {
30.         List<Branch> branches = new List<Branch>();
31.         List<Branch> closedBranches = new List<Branch>();
32.         var mainPath = new Branch();
33.         branches.Add(mainPath);
34.         mainPath.Add(Snake.selectedCore);
35.         while (branches.Count > 0)
36.         {
37.             var newBranches = new List<Branch>();
38.             foreach (var branch in branches)
39.             {
40.                 var core = branch.head;
41.                 var adjancents = core.GetAdjancents();
42.                 var validAdjancents = new List<Core>();
43.                 foreach (var adj in adjancents)
44.                 {
45.                     if (branch.CheckPath(adj))
46.                     {
47.                         validAdjancents.Add(adj);
48.                     }
49.                 }
50.                 if (validAdjancents.Count == 0)
51.                 {
52.                     closedBranches.Add(branch);
53.                 }
54.                 else if (validAdjancents.Count == 1)
55.                 {
56.                     branch.Add(validAdjancents[0]);
57.                 }
58.                 else
59.                 {
60.                     closedBranches.Add(branch);
61.                     validAdjancents.Shuffle();
62.                     foreach (var adj in validAdjancents)
63.                     {
64.                         var newBranch = new Branch(branch);
65.                         newBranch.Add(adj);
66.                         newBranches.Add(newBranch);
67.                     }
68.                 }
69.             }
70.             foreach (var branch in closedBranches)
71.             {
72.                 branches.Remove(branch);
73.             }
74.             branches.AddRange(newBranches);
75.         }
76.         int size = -1;
77.         var finalBranches = new List<Branch>();
78.         foreach (var branch in closedBranches)
79.         {
80.             if (branch.path.Count > size)
81.             {
82.                 finalBranches.Clear();
83.                 size = branch.path.Count;
84.                 finalBranches.Add(branch);
85.             }
86.             else if (branch.path.Count == size)
87.             {
88.                 finalBranches.Add(branch);
89.             }
90.         }
91.         finalBranches.Shuffle();
92.         return finalBranches[0];
93.     }
94.  
95. }
96.  
97. public class Branch
98. {
99.     public Branch(Branch Parent = null)
100.     {
101.         if (Parent != null)
102.         {
103.             parent = Parent;
104.             path.AddRange(Parent.path);
105.         }
106.     }
107.     public List<Core> path = new List<Core>();
108.     public Branch parent;
109.  
110.     //true = não checado - false = ja foi checado
111.     public bool CheckPath(Core target)
112.     {
113.         if (path.Contains(target))
114.         {
115.             return false;
116.         }
117.         else
118.         {
119.             if (parent == null)
120.             {
121.                 return true;
122.             }
123.             else
124.             {
125.                 return parent.CheckPath(target);
126.             }
127.         }
128.     }
129.  
130.     public void Add(Core target)
131.     {
132.         path.Add(target);
133.     }
134.  
135.     public Core head
136.     {
137.         get { return path[path.Count - 1]; }
138.     }
139. }