tag:blogger.com,1999:blog-6593394955445566294.post8149611360288872805..comments2013-01-28T18:29:42.476-08:00Comments on Ruined Game: Nav-Mesh Editor Part-3Larryhttp://www.blogger.com/profile/08581882165262995233noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-6593394955445566294.post-43996919751440681762012-06-28T18:32:44.701-07:002012-06-28T18:32:44.701-07:00Thanks a lot Larry. I will start try implementing ...Thanks a lot Larry. I will start try implementing the method since this weekend. Maybe in the beginning I will just make a simple editor to draw the navmesh rather than generating them programmatically. (voxelization and triangulation drives me a little bit a crazy)Anonymoushttps://www.blogger.com/profile/06378770053395463844noreply@blogger.comtag:blogger.com,1999:blog-6593394955445566294.post-64709121786996098422012-06-28T08:46:26.761-07:002012-06-28T08:46:26.761-07:00I represent the navigation mesh very similarly to ...I represent the navigation mesh very similarly to how you would represent a 3d model. I have a list of points representing the vertices and a list of "polygons." A polygon keeps track of its indices and its neighbor polygons. A couple of tricks to know are:<br />- If you store your indices in a counterclockwise order, you can have convex polygons with a finite amount of points.<br />- Pre-calculating neighbors is easy, just find polygons that have two or more of the same indices.<br /><br />I went a little crazy with my implementation, and brought the size of each polygon to a minimum, using bit-wise operations to retrieve data from a ushort[] - all my polygons are just really ushort arrays; then I wrote my own file format to store all this data.<br /><br />Now once you have your polygons, to figure out which one the player is on, you do a downward ray-test against the polygons.<br />Since all polygons are convex, they can be represented by triangles where the first point of the polygon is the first point of each triangle. There are several little optimizations you can do to decrease the number of ray-tests.<br /><br />Next, when using A*, you can use the distance between polygons to figure out the estimated cost. Then just keep track of the total cost for each movement, finding the path with the lowest total movement cost.Larryhttps://www.blogger.com/profile/08581882165262995233noreply@blogger.comtag:blogger.com,1999:blog-6593394955445566294.post-56442666632868461072012-06-27T19:50:07.074-07:002012-06-27T19:50:07.074-07:00Hi Larry:
I am a newbie game programmer. Recently...Hi Larry:<br /><br />I am a newbie game programmer. Recently I start to work on implementing navmesh algorithm. But I have three problems that could not be solved. the first one is how to generate the navmesh programmtically. then how to know which polygon the character is currently in. and the last one is how to calculate the g,h and f in A* algorithm for a navmesh. maybe using funnel algorithm? would u please share some experience? Thx!Anonymoushttps://www.blogger.com/profile/06378770053395463844noreply@blogger.com