Jump to content

New Path-finding Algorithm?


zeon23445

Recommended Posts

So I am really into algorithms and i have been researching pathfinding and the various algorithms and methodology behind it.

After some very intruiging research i have gotten down to the nitty-gritty of making my own algorithm and I am happy to announce i have a working algorithm for any obstacle and [in theory] it takes less steps and time than traditional pathfinding algorithms (such as A* and Dijkstra's algorithm) .

for ex.) I had set up a 100x100 "tile" maze and after 6 steps into the algorithm it had a definite path from the start to finish. As far as i know 6 steps is very impressive-

Its not completely worked out, however most of the algorithm is complete! I wont release any code [today] , however I would like to know: Do we really need more efficient or faster path-finding algorithms? Clearly its good for AI movement in real world situations but do other algorithms meet the criteria for a sufficiently moving AI?

Link to comment
Share on other sites

I guess that largely depends on your implicit assumptions you make when speaking about "path finding". One thing that immediately comes to my mind is reaction and protein folding paths in organic chemistry. You might think of finding a reaction path with a minimal energetic barrier as a path-finding issue, but in a possibly high-dimensional space with a complicated cost function (and in my case without actually knowing much about chemistry). Generally, I think one could fantasize about many different optimization problems being describable as path finding. The first limit to such fantasies will probably be the actual constraints/assumptions of your solution.

Link to comment
Share on other sites

  • 2 weeks later...

 

So I am really into algorithms and i have been researching pathfinding and the various algorithms and methodology behind it.

 

After some very intruiging research i have gotten down to the nitty-gritty of making my own algorithm and I am happy to announce i have a working algorithm for any obstacle and [in theory] it takes less steps and time than traditional pathfinding algorithms (such as A* and Dijkstra's algorithm) .

for ex.) I had set up a 100x100 "tile" maze and after 6 steps into the algorithm it had a definite path from the start to finish. As far as i know 6 steps is very impressive-

Its not completely worked out, however most of the algorithm is complete! I wont release any code [today] , however I would like to know: Do we really need more efficient or faster path-finding algorithms? Clearly its good for AI movement in real world situations but do other algorithms meet the criteria for a sufficiently moving AI?

 

Well, path finding is related to a computer science problem known as the P vs. NP problem. The question asks whether problems that can be verifiable in polynomial time, but solutions not found in such time could eventually be solved in polynomial time. It somewhat relates to the Traveling salesmen problem, where the whole point is to find the fastest(shortest) route possible to get to all locations. Maybe, it is related to path-finding?

 

Can't wait to see your code, if it does what you say it does.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.