Show HN: A new A.I. Algorithm for Polygonal Mesh Mazes

http://petercottle.com/liquidGraph/yc.html?demo

by xxbondsxx • 14 years ago

101 17 14 years ago

xxbondsxx6• 14 years ago

If you guys are interested, the source is available here:

Along with the emotional roller-coaster of commit messages. The source is pretty well commented and filled with ASCII diagrams so I tried to make it digestible.

The actual AI algorithm is a standard uniform cost search, but the state exploration function is where the new work is found. I sent out different gravity transitions from each concave vertex to find where you can get to from each state. All the paths you see are parametric equations as well, so there's no error-prone Euler integration used!

Edit: Also, the class lecture videos from this semester are here:

http://itunes.apple.com/us/itunes-u/computer-science-188-001...

if you would like an introduction to AI. It's a great class, I highly recommend it!

akkartik• 14 years ago

Did you apply to YC? (http://github.com/pcottle/LiquidGraph/commit/8cf735f9a5)

MrDerk• 14 years ago

That's the page he linked to for this demo.

FreeFull• 14 years ago

"Oh no! This application uses -webkit-transform to animate the final solutions, which your browser doesn't seem to support. Everything will still work, but during the solution animation, you'll have to look at the gravity arrow in the corner that I coded just for you instead of having the part rotate in an intuitive manner."

Why not also use -moz-transform? Is there anything lacking from -moz-transform that would make it not work?

xxbondsxx6• 14 years ago

Sorry about that! It should be patched now.

Originally I was developing this on an old beat-up computer in my research lab (grad student life), so even an updated FF couldn't handle rotate3d. It seems to be working on my home computer though. Thanks for pointing that out! I try to not be browser-elitist.

ax• 14 years ago

You could also add -ms-transform, since that works as well in IE9+.

vetler• 14 years ago

-o-transform?

Eduard• 14 years ago

I like editing the track while the solution is running.

xxbondsxx6• 14 years ago

There are no gaurantees if you inject polygons during the search space exploration :D it might find a solution but the animation will be off.

Another fun thing is to watch it find the worst acyclic solution... it's pretty entertaining to see how roundabout the path can be:

petercottle.com/liquidGraph/worst.html?demo

sukuriant2• 14 years ago

Doesn't work in IE 9 :/ can't even see anything but some small lines and hidden text in IE 9

xxbondsxx6• 14 years ago

Sorry about that, it's currently just academic research right now so I wasn't able to get time to add IE support. I actually had to argue pretty aggressively just to implement it in javascript; most research papers get implemented in C and are sent off into the abyss of binaries

sukuriant2• 14 years ago

It works in other multi-operating system browsers (at least it works in Firefox on Windows), so that's good enough for most people :) I'm jut surprised it didn't show ~anything~ in IE, except the aforementioned barely-anything

tantalor• 14 years ago

I had fun foiling it. Here's my best (12 vertices) maze with "no solution found",

https://gist.github.com/2503989

xxbondsxx6• 14 years ago

Hahah very good! It would be hard to drain that piece by hand without some very quick turns.

Future work in the algorithm is going to look at rotating the piece at any arbitrary point in time (to any arbitrary angle). At first this seems like a combinatorial explosion of the search space but we have some ideas on how to make it manageable. so maybe one day that part can be drained as well!

stanfordkid• 14 years ago

This is awesome! I took a class in motion planning and we did similar things... have you heard of kinodynamic planning? (probabilistic roadmaps)... it is a cool technique if you want to do multiple queries.

xxbondsxx6• 14 years ago

Thanks, I'm glad Standford and Berkeley students can find something in common (haha)

I haven't heard of kinodynamic planning, I'll definitely look into that! I've done some basic particle filtering and inverse kinematics, but it seems that this might be exactly what we are looking for in terms of future work. Thanks again

Tomis02• 14 years ago

"Oh no! This application uses -webkit-transform to animate the final solutions, which your browser doesn't seem to support."

Web standards are so great that everyone has their own.

Show HN: A new A.I. Algorithm for Polygonal Mesh Mazes

Related Stories