Pathfinder & Organisms (AI)
As promised, here is the project experiment that I originally wrote the pathfinder algorithm for.
Here’s how it works: ‘Organisms’ (the colored moving squares) are thrown into an infrastructure (a collection of connected points, i.e. the circle/star with connected dots). Each organism is assigned a certain destination-point within the infrastructure and carries with it a pathfinder (a polished version of the algorithm I posted about some time ago).
The pathfinder will figure out which points to travel (trial and error, guessing together a route to the assigned destination, see previous post) in order to reach the destination and will then tell its organism where to go.
When two organisms happen to travel the same connection (line between two points in an infrastructure) they will share and compare their knowledge about several of the paths they have traveled, this is visualised by both organisms becoming semi-transparent.
May 24th, 2008 | Quote
Hi, nice visualisation for this
As meationed before, I guess there is a need of optimization throughout performance and the way taken by each organism. Nevertheless I would be interested in the final pseudo code, describing your algorithm in detail. 
May 5th, 2008 | Quote
Gud coding.. but needs more polishing as efficient shorter paths can be detected by human minds
.. from a birds-eye view ofcourse 
make it so that a organism can ’see’ in a straight line/path and decide upon a shorter distance as in a maize.
hope ive made some sense :p
Johl
May 2nd, 2008 | Quote
It would be nice to see what each organism knows, like if you mouse over it the lines it doesnt know fade out or something
April 30th, 2008 | Quote
I don’t get it but it looks cool.
April 30th, 2008 | Quote
this is so cool!
April 30th, 2008 | Quote
Very artful demonstration of the algorithm . . . nice!
April 26th, 2008 | Quote
this is cool! Can you apply this to routers and switches?
April 19th, 2008 | Quote
Impressive!!
April 19th, 2008 | Quote
Indeed very interesting. It would be quite the tool for game developers. Place a hundred different organisms on a level, and make them communicate, thus eventually creating sophisticated AI. Of course, it would need to be a bit more advanced. For instance, AI in most games would need to know about tactics.
April 14th, 2008 | Quote
I love how you made such a nice GUI for a pathfinder algorithm test.
April 14th, 2008 | Quote
Nice
April 14th, 2008 | Quote
Which is true , Haylestar
April 14th, 2008 | Quote
so in essence you tought them to learn?
April 13th, 2008 | Quote
this is interesting but i don’t really understand any of the writing, but I’m only a simple 12 year old girl from Australia, so what can i, and you the reader of this reply expect? All i can say is thank you to my 16 year old brother for introducing me to stumbleupon, through them i found this site and monet other interesting ones. i don’t understand some of them either.
This reply is actually pretty pointless I think but ah well. IT MIGHT ENTERTAIN SOMEONE ONE DAY!
^^hAyLeStAr^^
April 13th, 2008 | Quote
interesting
April 12th, 2008 | Quote
Great work, mate! Well done. I like it
April 12th, 2008 | Quote
Hey Banjo,
Good point, this project was much more of an experiment than anything else. Forgive me for quoting myself, I explained earlier on why I avoided having a central class:
April 12th, 2008 | Quote
I don’t quite understand why you would want the ‘organisms’ to share knowledge only when they pass.. all real-world implications of a path-finding AI would be more efficient if they shared knowledge at all times through a central server of some sort. Also I noticed multiple times that the ‘organisms’ would take a side route some three lines longer (or more) when there was a straight shot to their objective… Anyway, good job thus far, I’m not ragging on your AI.
April 11th, 2008 | Quote
@Michael: Yeah, sounds interesting, thanks
@Me:
Yes, of course it picks points at random, as you will find a great amount of pathfinder-algorithms do. When I said “is not random at all” I was referring to the fact that the algorithm does not take certain illogical steps (like a step back to the previously visited point).
So for those of you who have a particular urge to act like hair-splitters here, let me rephrase: My ’solution’ is not totally stupid, and is not entirely random.
..your name is not really ‘Me’, is it?
@Jonathan: Thanks. I can see what caused the confusion, although the organisms in fact do share data, it may take some time before this starts to show. This is mainly caused by knowledge-exchange being slowed down by the fact that organisms only share on encounters, I talked about this in another comment:
April 11th, 2008 | Quote
Smarter ants; this is fantastic!
April 9th, 2008 | Quote
To John Hectic:
as for how this could possibly save lives: this is a basic AI program. this guy is a great programmer and these kinds of programs, as well as many others will help pave the way for future advancements for better AI. You think hes wasting his time, but your the one wasting your time looking at this, thinking its stupid, then spending the time to write what you think is a witty comment, when all you end up doing is sounding like a jerk-off. Maybe you don’t know what its like to be dedicated to something, or even what learning is about, so why don’t you do us all a favor and don’t leave comments brah, and go get STDs, I mean laid…
April 9th, 2008 | Quote
I really like the idea of your ‘organisms’ sharing data, but I’m confused as to what data they are sharing. If the organisms are collecting data about paths, how come they don’t get better at path finding over time? I’ve left this page open for at least a half hour and I still see organisms traveling along three sides of a quadrilateral when they could have taken just one.
Oh, and for those people wondering what use this could have in the real world, I’m sure the military would be interested in robots that could map out a hostile area and collaborate on what they found.
April 9th, 2008 | Quote
You say: The algorithm is pretty simple in essence — it starts at one point, looks for connected/surrounding points, picks one at random…
You also say: My ’solution’ … is not random at all.
So which is it? Either your algorithm picks the next point randomly, or it is not random at all. The two are mutually exclusive.
April 9th, 2008 | Quote
I like what your doing, if you check out our galaxy or other galaxies, maybe your designs can follow the designs of the galaxies and the stars, like atrology. I’d bet that would really be sharp. Don’t you. An American inventor. Have a nice day. Mike
April 9th, 2008 | Quote
That’s pretty fascinating. I could watch for hours.
April 8th, 2008 | Quote
@John: Dude, far out, I’m like, ..ehhh, yeah. What? Brah, bla bla, peace out.
April 8th, 2008 | Quote
dude, this is totally like the most awesome thing ever uleh. How long did this take you? Youve made like dots move around a giant snow flake brah. Totally not a waste of time, this invention will like totally save lives some indirect way and produce greater efficiency of baking potatoes. Back to how long this took you, no worries you thought ahead, you weren’t gonna get laid anyway uleh.
April 7th, 2008 | Quote
Sweet piece of code! Nicely done…
Check me back anytime if you ever want to exchange thoughts. Cheers!
And I’m with Frederik: don’t worry about negative comments. Nowadays people care more about destroying others work through bad comments than showing and sharing what they got with others…
I’m also into a lot of experimenting with code related art/design and my first thought when I see someone’s goal achieved like this is not “What’s the use of this?” but something more like “Way to go! You did it!”.
So congrats! You did it!
April 7th, 2008 | Quote
Nice piece!
I wouldn’t worry too much about negative feedback. It’s part of the new social Internet. One man’s art is another man’s garbage (and both of them are absolutely right.)
April 7th, 2008 | Quote
@Ryan: First off, why so hostile? ..or rather, as a good friend of mine put it, “why’s everybody always have to bitch about things other people do instead of doing it themselves?”, I wholly agree with him. (I will not hide the fact that I also kind of like the way Joe put it to words)
That being said (and sad), to answer the big “why?”: for the sake of experiment.
I’m not all that familiar with programming AI/AL and decided to try some things out just for the sake of gaining knowledge, not for the sake of putting together the most efficient or original concept.
I agree on the fact that my approach might not be the most efficient one, but this is not at all without reason. For instance, I chose to let the organisms only exchange knowledge on encounters as opposed to having them submit it to some sort of ‘higher power’ because I felt this (the former) would make them more independant and functional as individuals (which in my opinion is important to the concept of AL). I knew up front that as a consequence of this decision knowledge would be spread less quickly among organisms. I do not feel this is as black and white as efficient vs. inefficient.
As for my original algorithm:
..without going all “are you kidding me” on you; the previously posted demo used a timed interval for testing- and demonstration-purposes. If this was actually a delay caused by dramatic memory-usage then you would’ve probably noticed at the hand of the performance of other running applications (assuming you were paying attention).
Now this really starts to sound like you looked at the source-code, you haven’t. My ’solution’ (if you want to call it that, then fine) is not totally stupid, is not random at all, and does not involve excessive amounts of time. I guess you’ll just have to trust me on this one, I don’t really feel like explaining my code to that extent.
Lastly, I am kind of flattered that you did actually bother to write a comment to something towards which you have such a negative feeling. So thanks, I guess..
@kometbomb: The natural-selection concept had in fact crossed my mind, eventually I decided not to implement that here, in an attempt not to make it all too complicated (as it is merely an experiment).
@Dan: Thanks! I don’t know actually, if you know one then be sure to let me know
@sunrsie: Thanks for the kind words
@Joe: Hahaha.
April 7th, 2008 | Quote
In response to “Ryan”…so he has duplicated the human experience…and don’t be a snobby grabastic mathematical bitch. Provide a solution or shove a banana in that pie hole you dumbass.
April 7th, 2008 | Quote
that pretty cool
(first)
April 6th, 2008 | Quote
My main question is why?
I will admit that it is quite graphically pleasing, but the entire concept is flawed.
You have essentially reinvented the path finding wheel in an extremely poor and inefficient way, and tossed some graphical polish on it.
Your original algorithm is brutally inefficient, and takes incredible amounts of processing power to find the simplest paths. Even a naive breadth/depth first search will find an *optimal solution* in fractions of the time your method takes. Something like A*, Cooperative A* or some of the more interesting variations are more efficient, generate better and more natural looking paths, and can even share knowledge across all agents for interesting emergent behavior.
You have created a random trial and error solution (Not even following a set of permutations, so you may repeat failed solutions) that outputs garbage twisted paths after beating its head against the problem randomly for an excessive amount of time.
April 6th, 2008 | Quote
Wow. That is very clever. I like anything to do with Ai in computer programming, but this is very clever because it is so simple. If that can be done by a student in their free time, then why aren’t the multimillion pound/dollar companies closer to real AI?
Anyway. Good luck with university.
April 6th, 2008 | Quote
Btw, you can very easily improve the algorithm by not choosing the next node randomly but simply checking all possible routes (avoiding nodes you already visited). This is called the breadth-first search and it’s useful for situations in which the distance (or cost) between two nodes is not important, e.g. in this case it would work because most paths are quite similar in length. It will find the route with the least number of nodes between the start and the end.
Or, you could demonstrate natural selection by using a random algorithm but somehow penalizing the organisms with the worst routes. That would keep the project in the “interesting” territory. I wanted to post a link to another Flash applet that had flying rockets that steadily improved their trajectories thanks to NS but couldn’t find the link.:)
April 6th, 2008 | Quote
Awesome! Thanks Steve
April 3rd, 2008 | Quote
Perhaps I should’ve posted this sooner….but for really awesome pathfinding, you should check out this example I saw a long while back
http://www.electrotank.com/junk/mike/ai/precomputedPathTutorial.html
Its old, but I imagine it’s still very efficient for Flash apps.
April 2nd, 2008 | Quote
@Wietse: Hahaha, thanks man, but no, you know me; use is overrated
Seriously though, this was much more of a personal experiment to polish my skills and gain some knowledge on actually programming AI.
On the other hand, routing-algorithms have actually been applied a great deal, for one thing in navigation-systems (Tom-Tom?), even though my algorithm probably does leave some optimisations to be made..
@Kevin: Thanks! Actually I thought I was done about a week or two ago, then I noticed this bug that had me making modifications for ages
April 2nd, 2008 | Quote
Ruben. Very cool. I suppose this took you a bit longer to develop than the first post.
April 1st, 2008 | Quote
That’s looking extremely cool Ruben! Great work! Have you thought of any useful ways to put this to use yet?