Pathfinder (AI)
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.
July 19th, 2008 | Quote
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..
May 24th, 2008 | Quote
Hi there,
Cheerio bechte
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.
April 26th, 2008 | Quote
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).
April 14th, 2008 | Quote
This is Dijkstraaaaaaa!!!!! ( and not using backtracking only worsens the performance )
April 13th, 2008 | Quote
Hey jack, thanks! I had a look, very interesting
April 13th, 2008 | Quote
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
April 12th, 2008 | Quote
Haha, yes, I guess so, thanks.
April 12th, 2008 | Quote
that’s a lee algorithm, right?
April 10th, 2008 | Quote
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?
April 7th, 2008 | Quote
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.
April 7th, 2008 | Quote
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)
April 7th, 2008 | Quote
Hey Andy, check out the experiment I created this mockup for in the first place, here you go:
rubenswieringa.com/blog/pathfinder-organisms-ai
April 7th, 2008 | Quote
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.
March 14th, 2008 | Quote
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
March 14th, 2008 | Quote
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.
March 13th, 2008 | Quote
very nifty stuff man…
grtz, Arno
March 12th, 2008 | Quote
Hey Lauret, I sent you an email, so check your inbox
March 12th, 2008 | Quote
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
March 7th, 2008 | Quote
@Berber: Oh for sure I will, you’re probably gonna hate me for it
March 7th, 2008 | Quote
bloody brilliant! keep up the good work, I hope you will teach me your nerd skills some day:)
love and kisses, berber
March 5th, 2008 | Quote
Awesome! Looks great!