Monday, March 15, 2010

Trivial navigation mesh generation II

This one better not turn out as long as the last one or I will have to split this out over even more articles. The reason I allowed the last article to become so long is because I wanted to leave you with enough meat to implement it so that if you wished you could have it done by this post and then start refining it.

The meaning of Updating

The reason I always refers to updating is because you can’t just set a triangle to being blocked or unblocked. Well you can do that but what if the same triangle gets blocked by more than one obstacle for example and then that obstacle is destroyed. If you just set the triangle to unblocked you will be able to drive through one of the objects. And if you don't then you can't make objects that you can destroy dynamically at all.

This one better not turn out as long as the last one or I will have to split this out over even more articles. The reason I allowed the last article to become so long is because I wanted to leave you with enough meat to implement it so that if you wished you could have it done by this post and then start refining it.

The meaning of Updating

The reason I always refers to updating is because you can’t just set a triangle to being blocked or unblocked. Well you can do that but what if the same triangle gets blocked by more than one obstacle for example and then that obstacle is destroyed. If you just set the triangle to unblocked you will be able to drive through one of the objects. And if you don't then you can't make objects that you can destroy dynamically at all.

Another case is if you are laying down a bridge. A bridge is an object that opens up an earlier blocked triangle (preferably one that was blocked by water) what should we do with the case where there is an object standing in the water blocking our way (well don't allow it to build a bridge in that case but some borderline cases will be hard to detect) if we just allow it to open up a triangle that was blocked it could be used to make earlier unpassable areas passable no matter what was blocking them and so on. You could try to catch all these cases with outside code but in the end you would be fighting a loosing battle. Wouldn't it be nice if the navigation mesh system could support all these things? Well of course and that's what updating it all about, you don't just set the triangle to blocked or unblocked. Instead you update its internal data state and allows it to make its own decision about if it is going to be blocked or not after the update.

This allows for quite complex dynamics in the code that determines the state of a triangle instead of just being a simply on or off flag we can make a complex structure that takes into account multiple data sets to make a decision. There are many sets of data that can achieve this and I'm not going to cover all of them. I will show you a simple way which will not be very memory friendly but if you only have like 10-20 000 triangles in your meshes then it won't really matter but we will also look at an easy way to perform memory optimization to carry it into a usable range.

The two lists

The first step in the solution I propose is that for every triangle you have a list of all the objects that are blocking that triangle. The basic idea is that if that list is empty the triangle is passable and if it isn't empty then the triangle is blocked. So if we have a triangle that gets Updated with "Add House1" and then with "Remove House1" then it will be blocked between these two updates but after the remove House1 update it will again be passable.

However if we first have a "Add House1"  followed with "Add House2" for the same triangle (meaning that triangle is blocked by both the houses) then updating with "Remove House1" won't make it passable because the triangle is still blocked by House 2.

So far all makes sense and it easy to follow I hope but there is as problem with this approach and that is the reason this section is called the two lists... Before we venture any further in this I just want to make clear that the "Add House1" etc command's doesn't mean I would communicate with text based update messages I would probably make one RemovingUpdate and AddingUpdate but writing in this article I have chosen to leave all messages as text based to make it easier to read and follow the steps of the algorithm.

So why two lists? Well it's because of the following problem if I have an object that should open up the path list for example I am building a stair over a fence. Then that stair should call a "Remove Fence" update on the triangles inside of the stair. But what happens when we want to remove the stair? The stair isn't in the list, and we have no way of knowing what objects it has removed either so we can't add them back.

It seems clear that we need an extra list to handle objects that clear a path through other objects not by removing them but by bridging over them and that is removable/destroyable. Please note that things like open up destroyed buildings removing trees etc and most common actions in a game does not fall under this category that is simply removing an existing block we are talking about things that open up a path through a block without removing it like a bridge over water, or a stair over an obstacle. Or any other object that allows access over earlier impassable areas.

If we call the first list the blocked list we can refer to this list as the opening list. However what information should we put there. We can't just put the openers ID there because we need to know what it opened so we can close it or even that it does open something. If you place a stair over a triangle that is blocked by both by a house and a fence you should only open for the fence while the house still stands there you should not be able to pass through.

So each object added to the opening list should also contain a list of which objects it opens through (is this getting complex? well slightly but this code path will be executed very seldom so it's ok). So to detect whatever a triangle is blocked we first take the list of blocking objects and makes a copy of it. Then we iterate through the opening list. For every object in the opening list we iterate through what it opens. If we find an object that it opens in the temporary blocking list we remove it. If the temporary blocking list is empty after this has been performed for every object in the opening list then the triangle is unblocked. In reality this code will only be run if the opening list isn't empty which is most of the time.

bool Triangle::IsBlocked()
      /* This is the code that will be executed except in very special cases those we only add an extra compare and as this code shouldn't be evaluated every frame instead it should only be called when the triangle has been updated to select the value of a flag in the triangle this won't matter */

    /* Assumes we can make a straight copy like this of whatever data type we are using */
   for(int i=0;i


         /* This assumes that the remove functions works even if the object isn't present in the list)


One interesting question remains what is it that we store in those lists? Well you could store a string based name of the object in question but that would be quite expensive. So I would suggest an unique ID for that object for example a hash ID of it's name or any kind of unique ID you want to use. This way the comparisons are only int comparisons which cut's down drastically on performance but especially makes the memory usage of the algorithm a lot more humane. And since you get a 100% flexible path finding system for blocking and unblocking that can be considered cheap.

Some of you might notice that if every object has a unique ID how can we for example make a stair that allows us to move over fences if every fence has it's own unique ID. This is an interesting question and can be resolved in two easy ways. One is that expect for it's unique ID a block also has a typeID and the opener is allowed to remove any objects with the same type ID as it's opener. This allows easy handling of multiple objects etc but it means the blocked list will take twice the memory while this probably won't affect the memory consumption of the algorithm overall it might feel too much for some persons. They can go for the way of actually detecting which objects that are near the stair and of the correct type in the game code and add their ID's to the opener list.  I would side with the first option in most cases because it is elegant and easily extendable and doesn’t need any special code anywhere except for 1 line or so in the IsBlocked function.

That’s all for the two lists so I think it is time to move on.

Complex objects
All the examples in the earlier post were about single triangles. How does the algorithm really cope when dealing with complex objects of hundreds of updating polygons? Well obviously the fewer the better simply because there are less calculations to perform that way. Well you can actually call the system one triangle at a time you will perform a lot of unnecessary calculations but it will work.

So let’s look at what we can do to speed it up a bit. One obvious step is to make sure that every cutting line is only used once. This means that if you have a square you should only use the centre line for the first triangle and skip using it as a cutting line for the second triangle. This might not sound as that big a saving but as the objects get more complex it can really help a ton.

Of course you can take that one step further since any edge that is internal to the object so that it doesn't affect the outside it will hit a point where two other edges also meet. So there is guaranteed to already be a split there. This means that you can actually discard all internal edges and not even use them for splitting at all. So how do I detect if an edge is internal? Well if your complex object is built with the same rules as the rest of the world which means that if two triangles share a edge it is the same edge and it contains booth triangles it means that any edge connected to two triangles in the object is internal and doesn’t need to be calculated. This means that if the object is complex because it was sloppily modelled that all those completely internal polygons won't generate any splits.

You can also make some optimizations in selecting which triangles to get the edges to be split from by first getting all triangles near the complex object using a circle or another structure and then only make the tests vs. those. Also only those triangles that are interacting with a triangle that has outer edges are relevant for splitting.

You can probably do even more funky stuff in selecting which triangles to do what with and how to perform the culling. But this is starting to get case to case dependant as in all optimization matters play around a bit with it and measure besides make sure that it is a performance problem before you spend all this time trying to fix it.

Building ComplexObjects From a Heightfield
A normal case for a lot of games is that the terrain is based upon a height field and you want to select what is passable and not passable based on this height field. In our case it means that areas of the height field that is supposed to be unpassable should generate complex objects that are used to update the world with to add them as block. But an interesting question is how to build these objects.

If you just make every tile a square with two polygons it would obviously work but it wouldn’t be very efficient for generation and also it would cause the edges of the passable world to show tile jaggies. A more efficient way would be if you could smooth over these jaggies to create an object with a smooth edge and with a lot lower complexity.

It's just a matter of selecting how to do it but the important thing is to create an outer hull and then create a new triangulation of it to reduce triangle complexity. If people comment that they want to know more about this I can go through it in detail but for now I am going to skip it by in order to allow this article to focus in the meat of the method.

Storing Extra information in the Triangles
So far we have talked about updating as only updating the two lists that decides if a triangle is blocked or not. And if this is all the information you needs to store then that is fine. But a lot of the times when working with games you want to store extra data in your navigation mesh.

This might be other path finding related data as the cost to travel inside this area. For example if the triangle is apart of a road then you would expect travel to go faster on that triangle than on one that is inside a swamp. They way you do this is to store a cost multiplier inside the triangle that tells you with what factor the current cost for travel inside the triangle should be multiplied. Of course you need to have a reliable way to know if a triangle is part of a road and if you have just generated your navigation mesh chances are big that some of the triangles that cross the road will also have parts that are outside the road and the same for the swamp.

Thankfully updating is again a big help since updating guarantees to respect the edges of the updating triangles. So far we have only made updates that change the blocked lists but there is no problem to make an update that changes the cost values of the triangles inside the update instead. This way you can easily layout a road and get a cheaper cost inside it or a swamp to increase the cost of the triangle. The power of updating is that you can store any value in a triangle and you can change it anywhere as long as you can make a shape of triangles that represent the area you want to affect.

You can store information like that this triangle is composed of hot coal and does one point of damage to any player that is inside it. Or a healing area that is holy to your tribe. You can store any data you want into the triangles. And update any shape without worrying about it.

A word of warning goes out here however if you get crazy with updating you might increase you’re triangle count to a level where it will start affecting the actual path finding which would be counter productive. So there might be a good case for only embedding data relating to the path finding in the mesh. But there is nothing to stop you from making another mesh containing game play area effects. I'm not saying you should do it, but it does contain intriguing possibilities but most of the time we will probably just be better of faking it.

Precalculating destructability
Well I promised quick dynamic updates especially for removals of objects that block the path which is the most standard case in games still. So how am I going to come through on that promise? Well obviously there is no free lunch so there are some gotchas with the method. Not in the result mind you but in the process one you are possible generating more triangles in the navigation mesh that didn't need to be there until after the block has been removed (This will not happen in all cases but it might in some) There is also some work involved by the programmer in a pre processing step. This should not come as a great surprise as pre-processing is involved in a lot of optimizations the basic idea is so simple if you can calculate it in advance do it!

And that's what we are going to do, we will precalculate the data for the destroyed blockers. Before we go into detail I just want to talk about the two possible cases for what can happen when a blocker is destroyed.
  • The path blocking influence of that blocker is completely removed leaving no trace of it ever having been there
  • The path blocking influence is removed. But in it's place a new blocker appears representing the remains of the destroyed blocker it will normally block a much smaller area but it will still be there.
Let's start with the first case, so basically all we have to do is to remove the influence of the object well that sounds easy. We should just perform an update on the area it occupied with the input to remove its influence. While this would no doubt work it would result in creating more triangle sin the area unless the update perfectly matches up with the original area. Which of course we can easily make it do. But then we will instead perform an update that forces multiple polygons to detect which polygons are inside them to select which polygons to update and that would not be free while not to expensive either I said quick updating and that seems to expect something better.

Of course I can do better what about just finding all triangles within a radius of the object, that sounds pretty fast and pretty quick. And then just remove the ID from all triangles you get in that list. Well we are getting pretty fast now triangle inside circle for these cases where we can assume the circle is a lot larger than the triangles can be optimized down to point inside circle which is pretty damn fast. This would definitely be workable but we can do even better. What if we during pre-processing when we create the original navigation mesh, we also for every object generate a list of every triangle it is affecting? Then all we would have to do is that when we remove the object we run through its triangles and removes it from the lists. Well that would be lighting quick, there is however a catch like always. But this one is rather small it is if a triangle that is on one of the objects list is split we have to update that list but since every triangle already has an ID for every object affecting it we can do it quite simply by having the triangles themselves call the object with two new triangles and telling it to remove the original. Also this is a special case since we will be precalcualting almost all updates anyway so it will happen very rarely.

The second case is a bit tougher, we can't just remove the influence from the object we also have to add the wreck object's influence too. The method I propose is shockingly simple, what if you add all the wreck objects in advance too directly at the beginning? This way the triangles inside the object that is going to be occupied by the wreck object has the wreck object added from the start making the act of removing the original object as a full   modification since it won't open up the areas that are still blocked by the wreck. So booth removing the original object and adding the wreck is accomplished by just running through the list of the original object and remove it. This might cause more triangles to be generated of parts of the wreck object is close enough to the edges of the original object to affect it's edges but we will look at ways to optimize this later on.

This will only work properly if the wreck is smaller than the original object though. What to do if the wreck extends outside of the original object? Well we can still solve that case with precalculations it's a little bit more work but still perfectly manageable. Inside out triangle we add a third list called the passive blockers list. We allow updates that add data to the passive blockers list. And updates that moves an ID from the passive blockers list to the blockers list. This way we can still precalculate everything by adding all the wrecks as passive blockers. And just as for the original objects we also store in each wreck which triangles it has been added to as a passive blocker. And now we first run through all the triangles in the original objects list and remove them from the blocking list. And then we run through all the triangles in the Wrecks list and move their ID from the passive blocker list to the blocker list.

As you can see the concept of updating allows for a high degree of flexibility in working with solutions like this. Even seemingly complex problems yields easily. But again I give the warning of trying to do too much with it. If all you have is hammers everything might look like nails but they aren't. So while this is powerful use it with caution, but to get free path finding updates for most cases we can be prepared to do a little work after all.

Optimizing for runtime.
To wrap it up before this post turns into another monster I have been talking about possible optimizations that can increase the performance of the algorithm without turning it into a monster of numerical stability. Like trying to perform all calculations on convex hulls instead of triangles would do. It is possible to do of course, it's a bit tougher to do it well so that you don't get unnecessary hull splits But going through that topic would require another lecture perhaps called "Non Trivial navigation mesh generation" anyway that's way beyond our current scope what I wanted to do was give you something that is simple yet powerful and just basically works and won't take weeks to implement.

So what can we do to optimize it? Well the problem is still obviously the triangles. A triangle isn't the most efficient primitive to describe certain shapes or let's be honest any shape that isn’t triangular a quad would take 2 triangles a hexagon would take 4 it's just more efficient to use more complex shapes if we can, but down that path lies a lot of work so can't we fake it somehow ?

Fortunately we can, we can reap some of the benefits of using convex shapes while maintaining the simple update code for the triangles, now bear in mind that just won't be as good as complete correct convex hull code would be we won't be bale to perform as many merges (20-30% less when I ran tests) but we can improve our node code by cutting it into at least half or more and this without risking it all (which isn't very interesting unless you are a professional studio in which case you should already know all that I am telling you. Because in that case it is worth it spending some extra time to make it perfect but for students or independents this will be plenty).

The basic idea is the following, what if we could keep our data as convex hulls when path finding but as triangles when updating? Then we would get the advantages of both the sides. Of course as always there are no free rides. What you do is that after you have made an update you go over the triangles and merge them into convex hulls. And before you does an update when you select which triangles you are going to take the edges from to split you triangulate the relevant convex hulls. So the process goes like this.

  1. Detect which convex hulls are intersected by the updating triangles (don't do this for every triangle that would be madness)
  2. Triangulate those hulls.
  3. Run the updating algorithm a usual using those newly created triangles as data.
  4. Merge back into new convex hulls all triangles that can create a convex hull and has identical lists and cost.
That last paragraph of identical list and costs are important. When you merge back to a convex hull you can't merge together triangles that have different data because then you will either loose some data or the entire hull will contain all the data in which case the data for some areas will change. So you have to preserve the edges between objects with different data sets so they don't break down. Of course if you have precalculated all of this you wouldn’t need to run the algorithm during runtime. But if you have to you have some issues to consider.

What data should you have links to from your objects? The convex hull or triangles? Well you have to have whatever form is accurate now. But the good news is that while you are performing an update nothing else can change the data so you can keep the original convex hull in the owner and then after the final step remove it and add any new hulls created during this process.

Obviously this process does make updating more expensive. But you do get a lower path finding cost and the compromise is something you have to decide for yourself.  While this last step isn't trivial it is very possible to perform in a reasonable amount of time.

Well that's all about navigation mesh generation for now and remember to come back next week.

No comments:

Post a Comment