TIGSource Forums

Hello Guys,

I need to make a game for college and I need a function that receives two positions (2D), a beginning and an end. That function has to return a list/array with every path's that can go between each positions. Can Anyone explain me an algorithm that can generate every possible paths that can go between two positions. Thanks  :beer:

Hmmm... To get paths between two points you probably have to use pathfinding algorithm such as A* or Jump Point Search. You can implement those algorithm in such a way that they return all the possible path instead of just the optimal one. You should find lots of information about A* on the internet, just do a google search.
Here's more about Jump Point Search algorithm: http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf

All the vector work could be handled in Pymunk, a very handy library for working with physics. Otherwise, as the previous poster said, you can make you own algorithm with your own vector classes. There are some A* pathfinding examples on pygame.org.

Finding every possible path seems nontrivial? Like what does that even mean? Even just in the 1d case say i want to go from 1 to 4... here are possible paths:
1234
123234
12323234
...

Or is the question about finding all shortest paths? Paths without cycles?

Thanks guys I'm going to try to use something like A*

I was thinking the same thing...Finding EVERY possible path...?
Maybe it's every path without retracing steps.

Yes, you are right. Every possible path without going back.

That's still a lot of paths.  Hopefully you'll be working on a small grid, as finding all possible paths is the definition of brute-force and I'm pretty sure it will be O(n^3).

It's at least 2^(n^2) on a size n grid. E.g. if there were n^2 obstacles, then you could choose whether to pass to the left or right of each one.

de grid goes 5x5 to 7x7. But still it may be better to find a path, test it and then find another. I'm still trying to implement the algorithm.