At the moment I've been scribbling out an AI pathfinding manager,
and I've been looking for a good tutorial online for navmeshes.
EDIT:
Found a good section on navmeshes in 'AI Game Programming Wisdom'[8D].
Ah, all those graph algorithms like Dijkstra and A*.
This is the first time I've tried something like this
(aside from graphs for a couple of uni alg. courses).
The navigation mesh idea sounds good because it reduces
the search space into a minimal set of large convex
polygons (the walkable floor is divided into the least
number of rooms possible, or thereabouts). It's a bit
complicated so I might look at simpler methods first.
I downloaded an interesting paper about the algorithm
used in Baldur's Gate pathfinding; HPA*. HP there
stands for 'heirarchical path' - as in the heirarchies
you mentioned.
Progress is slow, but I'll get there in the end [}:)].
Yeah, I just came up with stuff off the top of my head from different articles that I've read. You could perhaps try www.generation5.org, that is a decent AI site with links to articles. Gamasutra should have something along these lines also (but I figure you would have tried that out already).
quote:Originally posted by Daemin
Yeah, I just came up with stuff off the top of my head from different articles that I've read. You could perhaps try www.generation5.org, that is a decent AI site with links to articles. Gamasutra should have something along these lines also (but I figure you would have tried that out already).
That generation5 site appears to be an excellent resource- thanks.
On a side note one thing that you could do would be to break up the traversable mesh into disjoint nodes and just make a graph out of them. Then pathfinding would just be as simple as finding the shortest route through a graph, and therer are many algorithms and much work that has been done on that. Going further you could subdivide the traversable mesh into a hierarchy and use different algorithms (at different rates) for navigating the world.