Ruben’s blog

That’s looking extremely cool Ruben! Great work! Have you thought of any useful ways to put this to use yet?

Ruben. Very cool. I suppose this took you a bit longer to develop than the first post.

@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

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.

Awesome! Thanks Steve

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.:)

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.

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.

that pretty cool
(first)

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.

@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:

quote from Ryan:

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.

..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).

quote from Ryan:

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.

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.

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.)

Sweet piece of code! Nicely done…
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!
Check me back anytime if you ever want to exchange thoughts. Cheers!

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.

@John: Dude, far out, I’m like, ..ehhh, yeah. What? Brah, bla bla, peace out.

That’s pretty fascinating. I could watch for hours.

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

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.

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.

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…

Smarter ants; this is fantastic!

@Michael: Yeah, sounds interesting, thanks

@Me:

quote from Me:

So which is it? Either your algorithm picks the next point randomly, or it is not random at all. The two are mutually exclusive.

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:

quote from Ruben:

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 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.

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:

quote from Ruben:

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.

Great work, mate! Well done. I like it

interesting

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^^

so in essence you tought them to learn?

Which is true , Haylestar

Nice

I love how you made such a nice GUI for a pathfinder algorithm test.

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.

Impressive!!

this is cool! Can you apply this to routers and switches?

Very artful demonstration of the algorithm . . . nice!

this is so cool!

I don’t get it but it looks cool.

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

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

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.

it’s look nice…

i think that would look great with waypoint AI. heheh.. just an idea..

That’s awesome. Methinks that the people who’re giving negative feedback are mostly missing the point .
Sure, there’re more efficient path finding algorithms that find the quickest path. But that’s not the point. The point is that this is more mimicking how real agents would have to work out the path, without direct access to the entire nodegraph.

This program is really interesting. If you pay attention, when on organism find the spot the program select a new point to put the target and in this moment the path is calculated, in this moment the program stop a little specially if the mark is far from the organism… Now imagine if the search space is bigger than this… In terms of the travelling salesman, one interesting aproach is using neural networks (again heuristics methods). You can find an implementation of this in http://www.heatonresearch.com/ in the section of AI…
Again lovely work ruben.
Congratulations…

Hey, pretty cool your pathfinder, can you seend me the codes for a try?

Thanks. See you later.