Jump to content
  • Advertisement

MendAndDefend

Member
  • Content Count

    5
  • Joined

  • Last visited

Everything posted by MendAndDefend

  1. MendAndDefend

    Nav mesh determining neighbours efficiently

    I increased the efficency by unioning all the nav meshes into a single polygon and then changing the line-of-sight check to determine if there's any intersection between the two points and checking if a point along the two points is in the nav mesh. It's probably not the best solution but it did manage to cut two minutes of preprocessing down to less than a second and should be good enough.
  2. Hey guys, I decided to play around with navigation meshes since I didn't know much about them. I have it working, however when the number of nav meshes grow, my algorithms' lack of efficiency begins to show itself. So I'm looking for advice to either make my current code better or simply better ways to do it.   My current code looks like this:   On startup: Store the various vertices that make up the navigation meshes into an array and use the index as an ID (to provide fast access to the points and to reduce the memory footprint (I can reference vertices by IDs rather than having their data copied everywhere)). Store the various vertices that make up the various points-of-interest's polygons in the same array. Determine the neighbours for all of the points. This allows the A* pathfinding to be snappy as all of the neighbours have been pre-calculated. The 'determine neighbours' function is the bottleneck. It iterates through all the points to check if they have line-of-sight (can be navigated to) all the other points (O(n2) time). I've done a simple speed up by choosing the ending point to be the point just after the starting point and beyond, so that I'm not checking the same two points.   The line-of-sight function is homemade, which is why I'm not surprised it's not that efficient. It calculates all the navigation mesh intersections between the two points and then checks if the intersection are at an 'external' boundary by checking if the points just before and just after the intersection are located within a navigation mesh. IE, I'm iterating through all edges of all navigation meshes to calculate the intersection point (if there is one) and if there is I'm checking the point just before the intersection if it's located inside a nav mesh (another iteration though the nav meshes) and then checking if the point just after the intersection is in a nav mesh (another iteration through the nav meshes). Yeah, pretty bad.
  3. MendAndDefend

    Nav mesh determining neighbours efficiently

    I've begun attemting to implement my altered half edge design but I have ran into a snag.   My pathfinding system is handed the polygon information upon startup. It converts the polygon information it is handed into something more useful (in this case, the half edge data structure). Right now I am iteration over each polygon and converting them, however I do not know how to handle shared edges. Currently my code simply iteraters though all the polygons, converts them such that the interior half edge points to their corresponding polygon and makes the exterior half edge face point to null.   Lets use the following diagram as an example: ----------------- |     1    |  2 | -----------------   Right now the result of my code would be as if there was a gap between polygon 1 and polygon 2. I need a way for my code to detect that, when converting polgon 2, that polygon 2's left edge is the same as polygon 1's right edge and connect the half edges appropriately so that polygon 1's right interior half edge is polygon 2's left exterior half edge, polygon 1's right exteriror half edge is polygon 2's left interior half edge and have polygon 2's  next/previous/pair half edges point the correct half edges.   Once I figure this out I will have to expand it so that it can handle t-intersections:              ------ ----------|      | |     1    |  2  | ----------|      |             ------- As well as multi polygon intersections:              |------|              |       | ----------|   2  | |     1    |------| ----------|   3  |             --------     As Dirk Gregorius pointed out, half edges don't seems to be designed for these kinds of cases; so if this can't be done (or is a total pain in the butt to do so) I will appreciate alternative approaches as I will be back to square one and my original post.
  4. MendAndDefend

    Nav mesh determining neighbours efficiently

    It sounds to me that using half edges for navigation meshes isn't a proper solution. From my understanding it works well for 3D or 2D graphical modeling; however with navigation meshes there will be times where such 'T-intersections' occur (and times where overlapping will occur for manually created navigation meshes) which half edges do not handle.   *** Edit ***   I may try to do half edges but alter the face member variable from an index / pointer to a data structure of some kind that states 'from 0 to 0.25 the face is null, from 0.25 to 0.75 the face is <some index / pointer> and from 0.75 to 1 the face is <some other index / pointer>. I'm not sure if this is a good idea though. When I'm learning a new concept I like to go as 'pure' and correct as I can to learn it and then slowly alter it as reality dictates for real life usage.
  5. MendAndDefend

    Nav mesh determining neighbours efficiently

    Looks interesting. I'll give it a go as it does look like it can simply a lot of things. I do have a couple of questions about implementing it.   Question the first: When an edge is shared between two polygons what is the best way to detect that so I can update the half edge? EG: Say I have two rectangles like so: ----------------- |     1    |  3  | -----------------  I take the polygon information from rectangle 1 and create the half edges. I do the same with rectangle 2 (not pictured) and then I get to rectangle 3. What is the best way to detect that the face belonging to the shared outer half edge on rectangle 1 is now no longer null but belongs to rectangle 3? Off the top of my head , I'm thinking that I will have to do a collinearity test for each new edge against all existing edges and update as required. This sounds like it's not that efficient.   Question the second: What do I do in the following situation?              ------ ----------|      | |     1    |  2  | ----------|      |             ------- The face for the shared outer half edge for rectangle 1 is rectangle 2, but what about the partially shared outer half edge for rectangle 2? It's both a boundary and a shared face. Or even in this situation:              |------|              |       | ----------|   2  | |     1    |------| ----------|   3  |             -------- We're talking about navigation meshes so these scenarios will happen. I likely won't be able to do a 'clean, unadulterated' version of half edges, which is fine; but I've only heard about half edges yesterday so I don't know how to alter it to account for these (and other) cases.
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!