Calculate fastest path in vector array

[stealthpaw]

Hi all. I need to calculate the fastest path in an array of vectors to get from X-start to Y-target.
Illustration:

https://files.facepunch.com/forum/upload/654/9b3550e1-8d20-4427-9fe4-c9e0d65139f7/image.png

I have tried various ways to work this out to no avail.

Can anyone help me figure this out?

[c👌de_g🎷]

Take a look at implementing Dijkstra's or A* pathfinding into Lua. There's a few other simpler (but less efficient) path algorithms you could also use.

[The_HAVOK]

this is pretty vague, how should it search? Is there a maximum distance between vectors that a path can be made? Is this in 2D or 3D space?
The easiest to do would be something similar to an A* pathfinder.

[solid_jake]

I believe there are some A* modules by themaw/spacetech if you want a reference

Search around for them on github or Google

[Vioxtar]

The shortest path would be start -> to -> target by default, assuming there is a connection between start to target.. basically pointing out that you didn't specify what your connections are, are they determined by vector indexes (can only increase index)?

[dingusnin]

Assuming all nodes are equidistant from it's neighbour, you can build an https://en.wikipedia.org/wiki/Adjacency_matrix, which under standard matrix powers gives you a new graph for each exponent n, who (i,j) entries gives you the number of hops between the i'th and j'th node. Even if your vectors are not equidistant from each other this gives you a few options - in particular you can create a grid of your own decision to which ever distance best fits your data set (read: grid who's minimum distance is a number similar to the concept of greatest common denominator of vectors. This can be done by considering each component seperately, and the gcd of vectors will be similar to an eigen vector in sorts).

Alternatively you could mess around with distance-matrix where in each (i.j)-entry encodes the weight of each edge. using https://en.wikipedia.org/wiki/Min-plus_matrix_multiplication, this can give you the precise distance as well, however this requires extra calculation.

If you want to be cheeky, you could couple my first suggestion with Van der Waerden's theorem / Ramsey Theory to give you an approximation of which "colour" (read path), however this is even beyond me. Hopefully this gives you some thought on how else you could do this - but the best suggestion by far is just to use A* or Dykstras. If you need any help, just reply and I can give you some rough work to help you along the way.

[stealthpaw]

Thanks for the replies! I'll check out an implementation of A* and see how that goes.

[stealthpaw]

Update! Thanks people, after much struggle i have implemented a simplified version of Dijkstra.

Result:

https://files.facepunch.com/forum/upload/654/a985acaa-c048-40fe-abac-a1f754e119e9/image.png