Pathfinder (AI)
by Ruben
In an attempt to kickstart my graduation-project I decided to throw together another AI-experiment (I'll post something about it later), after staring out of the window with a blank glare for some time I figured I'd need a pathfinder algorithm so I sat down and wrote/typed it down.
The algorithm is pretty simple in essence -- it starts at one point, looks for connected/surrounding points, picks one at random, and repeats these steps until it reaches the destination-point (success) or comes across its own trail (failure). In the latter case it'll start all over again from square 1, so to speak 
.
Check it out, when the destination-point has been found click the demo to start over.
Comments (also one trackback, click to show)
Trackbacks:
Awesome! Looks great!
bloody brilliant! keep up the good work, I hope you will teach me your nerd skills some day:)
love and kisses, berber
@Berber: Oh for sure I will, you’re probably gonna hate me for it
Hello , i’m working on flex project wich consist one Pathfinding on a map , and i would like to have your source. Thanks a lot
Hey Lauret, I sent you an email, so check your inbox
very nifty stuff man…
grtz, Arno
Impressive Ruben. Here is my what if.
What if the Algorithm kept track of previous failures. Doesn’t repeat failed paths.
or
What if it kept running until if found the best path to the node. The one with the least amount of steps.
That would be pretty simple to keep running multiple times and track the steps.
If you are going to do an AI model then it would be neat if it can somehow learn as it ran.
Thanks,
Kev.
Spot on! Actually this was the base of an experiment/demo I’m working on right now and strictly viewed this one might not even be considered actual AI (as it doesn’t learn anything).
I’ll post the final demo once it’s done, so keep an eye out
It’s pretty awful as a pathfinder because of failed attempts and no optimization. A far easier method would be as follows:
Call start node node 0.
Map all conected nodes as Node 1
Map all connected nodes from node 1 as node 2 etc
When a node reaches the end point, go back through the nodes (like node 8 to node 7 to node 6 etc) until you get back to the start point. You don’t even need to select one but can just pick the first as it will be the same length.
This method also moves around obstacles of ANY permutation, as long as there is a possible route somewhere, and is the shortest route possible as well.
Hey Andy, check out the experiment I created this mockup for in the first place, here you go:
rubenswieringa.com/blog/pathfinder-organisms-ai
Yeah I saw that. Without knowing the dest points it’s hard to see how optimized the routing is via the current pathfinder, and if you want some randomised movement so that some agents follow the same path as others then fine, but strictly as a pathfinding algorithm it’s poor. Not poor coding or poor execution (no slight intended), but poor concept.
Imagine the contral box as no go areas in your example, but your pathfinder doesn’t KNOW they are no go areas – how would it cope? It would still work, but only after many iterations of trial and error. A different implementation is definately an improvement (purely from a pathfinding perspective)
Here is an image of what I mean:
Start is top left, target is bottom right. X represents a no go area. Algorithm simply increments naighbours until it hits the target, then follows it home via the least energy path.
I maybe have found in issue in your pathfinder’s logic. If we consider the directions as a compass and it chooses the path:
East
East
South
South
West
North
it will fail rather than choose West to continue what could turn out to be a totally valid path. Is this something it was intended to do?
that’s a lee algorithm, right?
Haha, yes, I guess so, thanks.
If you google “god’s algorithm” you will find a path optimizer algorithm.
I haven’t looked for it in awhile but check it out.
Cool stuff you are working on.
Jack
Hey jack, thanks! I had a look, very interesting
This is Dijkstraaaaaaa!!!!! ( and not using backtracking only worsens the performance )
An A* algorithm would be much more practical. If you have no information (heuristic) about where the target might be, use dijkstra shortest path (essentially the same as A* with a constant heuristic).
Hi there,
I think backtracking is potencial a possible first idea, but in the end you will end up in bad performance with high memory allocation for your stack, just if the map you are trying to find your way out becomes bigger as 5×5.
Have you been looking for other path finder implementations, such as the A* Pathfinder algorithm. I think this is what you really need.
Cheerio bechte
i agree with bechte to some degree.. a* forgets about paths that didn’t work in the past – but they could work later – so starting over again from scratch when reaching a deadend maybe isn’t such a bad idea under some circumstances..
HI
I have an Confusion that if the dist of an object(TARGET).is same in any sense from the start possition then please tell me how he can choose its path
when he has more that minimal path in its sequense.
Thanking you
Ashwinkumar
Hi!
Really want to do some AI stuff myself and I’m pretty newbie.
Your algorithm as you explained is pretty straight forward, random. In what ways could this algorithm be improved?
On a very large scale would it not be better trying to find the “exit” bruteforce and then calculate the shortest path?
On a very large scale the complexity is also very high and the brute force is always a bad idea for problems of this nature. The idea of an automaton mechanism like this is a very way (and the best in my opinion) to solve the problem. If you search in the literature for the Travelling salesman problem (http://en.wikipedia.org/wiki/Travelling_salesman_problem) you’ll see that this is a particular case of this classical problem. You’ll find also that bruteforce is inadequate in the real world…
Nice work Ruben.
Sorry, when I say automaton mechanism I’m referring to an heuristic perspective..
By the way sorry for my bad english but I’m a Portuguese guy
hi..i like your work. actually im graduating this year so i think this is going to be good as my topic for my thesis. i hope i could get a copy of your source. thanks! =)