# MendAndDefend

Member

5

1. ## 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.

3. ## 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. ## 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. ## 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.