Jump to content


Photo
- - - - -

New Path-finding Algorithm?

Computer Software AI Path Finding Programming Algorithm

  • Please log in to reply
2 replies to this topic

#1 TeddyBauer

TeddyBauer

    Curious

  • Members
  • Pip
  • 1 posts

Posted 03 September 2014 - 09:26 AM

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?



#2 phillip1882

phillip1882

    Thinking

  • Members
  • PipPipPipPipPipPip
  • 654 posts

Posted 07 September 2014 - 11:48 PM

i find 6 steps very difficult to believe. i can't wait to see the code, if you publish it here.



#3 Buffy

Buffy

    Resident Slayer

  • Administrators
  • 8946 posts

Posted 29 September 2014 - 03:17 PM

Hi Teddy, welcome to Hypography!

 

"Path-finding" is a very general class of problems and doesn't just apply to mazes, but is incredibly useful in navigating networked databases (which by the way, links in web pages are an excellent example).

 

Not really sure what you mean by "6 steps" but you should note that differences in algorithms aren't always about efficiency but about whether they handle "hard" and "anomalous" cases. As an example, in negotiating mazes a "hand to wall" algorithm fails in mazes that have isolated finishes that do not have wall connections to the start (that is they are not "simply connected"):

maze.png

 

Of course to be truly significant, the algorithm needs to be more than a linear improvement over existing algorithms, it should have a higher order of performance.

 

Would be nice to see this in any case, but if it's really significant, you might want to patent it first!

 

 

The competent programmer is fully aware of the strictly limited size of his own skull; therefore he approaches the programming task in full humility, and among other things he avoids clever tricks like the plague, :phones:

Buffy

 


  • Poppins likes this



Also tagged with one or more of these keywords: Computer, Software, AI, Path, Finding, Programming, Algorithm