Dungeons

I've stuck A* path finding on the top of my, I guess, nav mesh thing now. It let's you make a nice big convex polygon, triangulates it and finds all the triangles centroids. Then you the user can choose two centroids and A* is used to plot a path.

I started doing this thinking a little about adventure games but this nav-mesh type code is quite general and could probably be used for all sorts of things. As I was drawing some of the images it reminded me of the old dungeon maps from Ultima Underworld (it would be easy to make a 3d mesh by doubling this and add some walls and then that's a pretty quick flat 3d dungeon).

(I really didn't want to write A* again as I've done a few times before but it appears I'd lost the code ;_;, so I quickly hacked out a new one, it's not a very good abstraction at the moment but it may get tarted up at some point. Amit is still the best reference on the net for A* and seems to go into a lot more detail than I remembered from last time I looked it up.)

I think at the moment the paths would be a little unnatural for an adventure game protagonist to walk (even if I stopped them being a collection of straight lines and made them into a bezier curve). I've had a closer look at the funnel algorithm and it actually seems pretty straight forward so I may even add that to this little experiment to.


* I've also rewritten the code that finds adjacent nodes, it's just as inefficient but it's now far easier to read.