Triangulation and pathfinding implementation

[arrakis42]

Hi !

I'm using the SFML 2.1 library for a game project, my project needs to use an A* algorithm to guide a character on the map to avoid obstacles. I'm using too the Thor library (http://www.bromeon.ch/libraries/thor/) to help me for the triangulation, indeed I want to use the triangulation to create a navigation mesh in the goal to ease the task of the A* algorithm. A little bit like this :



The blank polygon represents an obstacle

I work with the Thor library to have a similar result,



The black areas represents obstacles

1) I generate 4 points which represent a rectangle (it may be polygon later), I put these points in a vertex container and I put the 2 triangles which compose the obstacle in an obstacle container.

if (mouseEvent.button == sf::Mouse::Left)
        {
                AURORA_CITR_FOREACH(itr, _vertexContainer)
                {
                        if (*itr == clickPos) // Don't insert the same obstacle twice
                                return false;
                }

                _vertexContainer.push_back(*pt1); // insert the 4 points of the obstacle (which is a rectangle for now)
                _vertexContainer.push_back(*pt2);
                _vertexContainer.push_back(*pt3);
                _vertexContainer.push_back(*pt4);
                Obstacle triangle1 (pt1, pt2, pt3);
                Obstacle triangle2 (pt1, pt4, pt3);
                _obstacles.push_back(triangle1);
                _obstacles.push_back(triangle2);

                return true;
        }

2) I compute new triangulation for points of the vertex container

 this->_triangleContainer.clear();
 thor::triangulate(_vertexContainer.begin(), _vertexContainer.end(), std::back_inserter(_triangleContainer));

 

I run throught my obstacle container and through my triangle container and I remove the triangles that are part of obstacles.

std::vector<Obstacle>::iterator it = _obstacles.begin();
std::vector<thor::Triangle<sf::Vector2f>>::iterator it2 = _triangleContainer.begin();
                                       
while (it != _obstacles.end())
{
        it2 = _triangleContainer.begin();
        while (it2 != _triangleContainer.end())
        {
                if ((*it2)[0] == *(*it)._pt2 && (*it2)[1] == *(*it)._pt1 && (*it2)[2] == *(*it)._pt3) // I compare the obstacle's points with the triangle's points
                {
                        it2 = _triangleContainer.erase(it2);
                }
                else if ((*it2)[0] == *(*it)._pt3 && (*it2)[1] == *(*it)._pt1 && (*it2)[2] == *(*it)._pt2)
                        it2 = _triangleContainer.erase(it2);
                else if ((*it2)[0] == *(*it)._pt1 && (*it2)[1] == *(*it)._pt3 && (*it2)[2] == *(*it)._pt2)
                        it2 = _triangleContainer.erase(it2);
                else if ((*it2)[0] == *(*it)._pt1 && (*it2)[1] == *(*it)._pt2 && (*it2)[2] == *(*it)._pt3)
                        it2 = _triangleContainer.erase(it2);
                else if ((*it2)[0] == *(*it)._pt3 && (*it2)[1] == *(*it)._pt2 && (*it2)[2] == *(*it)._pt1)
                        it2 = _triangleContainer.erase(it2);
                else
                        ++it2;                
        }
        ++it;
}
 

At least I run A* algorithm with the different points (ends and midpoints of the sides of triangles).

But as you can see this is not optimized, and I don't know what is the better way to use the triangulation algorithm as navigation mesh. For now my code works with rectangles, but it doesn't work with polygons.... Could you give me some advices about this ?

Thank you in advance.

[Ixrec]

My understanding is that the pathfinding map is usually created by hand for each level rather than by an algorithm, partly because there really is no one algorithm that makes a nice map for a truly arbitrary set of obstacles and desired behavior, but also because tweaking it manually makes it a lot easier to adjust AI behavior in a specific level without changing how every enemy in the game moves.

[Janacek]

Actually the map is Procedurally Generated, so we can't possibly have different maps :x

We've managed to implement a path finding, but it takes so much resources that it slows the game down. I still think it's possible to generate that navigation mesh.

The map is generated at the beggining of the game, the navigation mesh will also be generated during this step. We don't have different levels, just a map which can be huge :/ The main issue is that it takes a lot of resources...

[arrakis42]

Janacek is working too on the project, and he's right, obstacles are Procedurally Generated so  the navigation mesh will be dynamic to avoid obstacles ...

[Ixrec]

Ah, I see.

I'm pretty sure there is no general solution for this and you'll have to figure out what works for your program through a lot of trial and error.

The only suggestion for generalizing I know of is that instead of tying the navigation mesh to the obstacles, perhaps use a simple square grid for the first A* pass (probably with ray-casting collision detection for excluding paths, since that should be easy to implement for arbitrary obstacle shapes) and then do successive passes to refine the path, possibly only on the part of the path currently in use.  Again, I have no idea if you want these paths to be computed once or change depending on who knows what, and I have no idea what kind of map geometries you're after so that's all I can really offer.

[arrakis42]

Thank you for your answer.

The obstacles are only polygons, we thought that the triangulation helps a lot the A* path finding (the polygons are composed of triangles, if we don't create triangles into the obstacles and if we detect if the player is in a triangle or not, we could avoid obstacles). The ray-casting collision detection can also be a viable solution we'll look further at this, but for the square grids, obstacles are not only rectangles, the player will never go diagonally ....

 Do you know if there is a library to facilitate pathfinding with sfml?

[Ixrec]

I've never heard of one and I'm quite sure it's not possible anyway.  The algorithm for pathfinding is always going to be some version of A*, and the whole point of A* is that you use a custom heuristic and node map, which always have to be designed for each individual program in order to not suck (otherwise it'd be no different from a brute force search, which is what libraries can and do implement).

If you like we can discuss possible implementations more, but I'd have to know a lot more about what you want your game to do (I don't even know if you have more than one entity doing pathfinding, for instance) and what you want the generated environments to look like.

[Janacek]

Actually one of the solution is to generate the whole navigation mesh at the beggining, but it uses a lot of memory :p (My map is already taking a "bit" of memory).

[zsbzsb]

Why don't you generate the map in chunks, I see no reason to keep the entire map in memory when your only using part of it at a time. Or if you really want to generate the entire map at once, maybe save the generated map in chunks to a file and then load the chunks you need.

[Nexus]

To account for polygons inside your mesh, try Constrained Delaunay Triangulation. The edges of polygons that represent obstacles can be specified as constrained edges using thor::triangulateConstrained(). Out of the resulting triangles, you have to get those inside the polygons in order to remove them. You can do that by traversing the constrained edges in a directed way (i.e. a cycle around the polygon), select for each edge the 1-2 adjacent triangles, and choose always the triangle on the right (or left, depending on the orientation). Finding which of two triangles is on the right side can be done using the cross product: When e is the edge vector and c the vector from the edge's first point (w.r.t. traversal) to the triangle's center, then the sign of thor::crossProduct(e, c).z determines the side.

Concerning optimization, you should avoid std::vector::erase(), especially while iterating. Instead, use the STL algorithm std::remove_if(). Or directly use a different data structure such as std::set (where finding and removing elements is relatively fast, using std::set::find() and the iterator overload of std::set::erase()). Furthermore, combine all the different conditions in your if statements using the logical or operator ||.

For graph problems, the LEMON graph library is interesting. An alternative is Boost.Graph, but I find it far less user-friendly due to its template overengineering. I'm not sure whether LEMON provides A* search, but there are some extensions, and implementing A* using LEMON is still more efficient than doing it from scratch.

[Janacek]

The map is an agglomeration of polygons, they are generated using the Fortune's Algorithm. I store them in a container.

After this I place them in a 2d array, it represents the chunks and then I display only the chunks that have to be displayed.

Only the generation of the map takes time.

We will try the ray casting solution

[arrakis42]

Thank you for clarifying this ! We will work hard to make it work.

[arrakis42]

@Nexus, I tried to apply the Constrained Delaunay Triangulation with your method "thor::triangulateConstrained", I put in the arguments  the points to triangulate ( the corners of the obstacle) and the edges of my obstacle, like this :

std::vector<thor::Edge<sf::Vector2f > >         _edgeContainer;
std::vector<Obstacle *>::iterator it = _obstacles.begin();
while (it != _obstacles.end())
{
        thor::Edge<sf::Vector2f > *edge = new thor::Edge<sf::Vector2f >(*(*it)->_pt1 , *(*it)->_pt2);
        _edgeContainer.push_back(*edge);
        ++it;                                                                          
}
this->_triangleContainer.clear();
thor::triangulateConstrained(_vertexContainer.begin(), _vertexContainer.end(), _edgeContainer.begin(),_edgeContainer.end(), std::back_inserter(_triangleContainer));
                                       

Here I gave each edges of my polygon. So for a polygon like this one :



I've created the edges A-B, B-C, C-D and D-A. But an error occured during the execution "Expression: list iterator not dereferencable"...  I think I didn't understand the usage of "triangulateConstrained", can you clarifying this to me ?

[Nexus]

You have a memory leak. Don't use manual memory management, it's (almost) never necessary. And iterate in a for loop, as it makes code more readable and keeps the scope of iterators small. When possible, use auto or range-based for loops, as I stated earlier.

for (Obstacle* o : _obstacles)
{
    thor::Edge<sf::Vector2f> edge(*o->_pt1, *o->_pt2);
    _edgeContainer.push_back(edge);
}

thor::Edge<V> stores pointers to two vertices of type V, thus you have to make sure the referenced vertices stay alive as long as the edge exists. If you use std::vector<sf::Vector2f> to store the vertices, pre-allocate enough storage with reserve(), in order to avoid reallocations that invalidate pointers to the elements. Alternatively (if you don't have a meaningful upper bound on the number of vertices), you can use a different container such as std::deque.

[arrakis42]

I've changed my loop with your guidance.

std::vector<thor::Edge<sf::Vector2f > >         _edgeContainer;

for (auto Obstacle : _obstacles)
{
        thor::Edge<sf::Vector2f> edge(*Obstacle->_pt1, *Obstacle->_pt2);
        _edgeContainer.push_back(edge);
}
_edgeContainer.reserve(_obstacles.size() * 2);
this->_triangleContainer.clear();
thor::triangulateConstrained(_vertexContainer.begin(), _vertexContainer.end(), _edgeContainer.begin(),_edgeContainer.end(), std::back_inserter(_triangleContainer));


 

I have some difficulties to understand the method "triangulateConstrained" . The values of the referenced vertices are good when I create my edges (I get the value of each vertices like this : "rectangle.getPoint(i).x + mouseEvent.x"). I reserved some memory  for the edge container, I've tested with different size of memory albeit without an outcome .... Moreover if I clear the edge container before the call of the method triangulateConstrained, the triangulation works well. I tried also to put some deque containers to replace the vector containers,  albeit without better outcomes.

  Can you help me one more time :x?

Thank you again ...