Show HN: A new A.I. Algorithm for Polygonal Mesh Mazes | Hacker News Reader

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

petercottle.com

101 pointsxxbondsxx17 comments

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!

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

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

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.

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

"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?

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.

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

-o-transform?

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

https://gist.github.com/2503989

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!

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

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

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

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

I like editing the track while the solution is running.

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

Reply on news.ycombinator.com