Create a 3D navigational mesh for flying/pathfinding

Create a 3D navigational mesh for flying/pathfinding

Cancelled

Job Description

I am currently leveraging Recast + Detour to enable 2D navigation in a game world. I now need a solution for navigation/pathfinding in a 3D world.

I'm looking for a developer that has the expertise to take input geometry (normals/indices/vertices) and create an algorithm/solution that can get from (x1, y1, z1) to (x2, y2, z2) through flying in this same world.

Input Geometry:
• You can download a sample continent here: https://dl.dropbox.com/u/15806454/Northrend.zip (991MB) An example file is here: https://dl.dropbox.com/u/15806454/17_37.obj
• Each file in the above archive represents a tile of size 533.333 x 533.333 x Z (Z is variable, you can calculate this)
• The entire continent is within the range: (-17066.66656, -17066.66656, Z) to (17066.66656, 17066.66656, Z)

Requirements:
1. Console application to: Convert geometry into navigational mesh files (the output file will match the name of the input, but with a different extension)
a. A settings header file must exist to allow easy changing of parameters (such as a walkable slope angle, etc...)
2. Console application to: Read in a continent (mesh files created by your first solution) in a thread safe fashion, store the information in memory and calculate a path between 2 points
a. It is very important that the calculating from A to B is thread-safe. After your work is complete, I will use a client/server model with multiple threads to handle calculations from A to B.
b. It needs to be fast, calculating a route needs to happen in less than 50ms
c. See the attached document (CaclulateRoute.docx) for more detailed requirements on the CalculateRoute function, there are more

You can design the solution, but I assume your mesh files would be a data structure storing information on what is traversable/flyable, potentially by storing flood fills, etc… Then you will know what areas are flyable vs. not flyable due to things like trees, mountains, buildings, water, etc…

Note: I'm not the expert here, at all, that's why I'm trying to find someone :) So I'm open to whatever solution you think would work.

I just need an end state where I can load in the nav mesh files created from the input geometry and get a path from A to B (using something like A*).

I'm using http://code.google.com/p/recastnavigation/ for 2D pathing right now, feel free to leverage this an adapt if you’d like. Here is an example of what it returns (for 2D pathing): http://admin.ceilingfansoftware.com/pathing/

I can provide the 2D solution as a starting point, but the mesh generation is a combination of objective-C and C++, and requires you to own a mac to run it (as I created a GUI).

Summary of Requirements:
• Written in C++ (to be compiled on unix, do not use windows specific code)
• 2 Console applications
o 1 to create mesh files
o 1 to calculate A to B by reading in the above mesh files (thread safe) in less than 50ms

---
Skills: unix, design

Open Attachment