I would like to start today’s update by summarizing all the different features I worked on during this project. First, let’s remember what the initial idea of the project, to implement a solution for 3D Pathfinding using a Sparse Voxel Octree for representing the space and A* for finding a path between two voxels in the SVO. The main objective for using an SVO was to get an optimized way of representing the space, mainly because other approaches likes a uniform grid might incur in a heavy memory consumption. Thus, with these ideas in mind, I started working on the project.

My first step was to create the SVO structure that would hold all the data, and then generating that data, following these steps:

• First pass rasterization: check collisions at the layer previous to the last one, to determine which nodes had to be created
• Iterate from the bottom up creating all the nodes and setting the parent-child links
• Iterate from the top down, setting all the neighbor links

Visualization was a very important feature of this project, so I implemented the ability to draw the voxels in space so they could be seen in real time, as well as their identifiers and corresponding links. This was definitely of great relevance during development as it helped me debug much faster. Seriously, I can’t emphasize enough how important and necessary this is, so make sure you always have a debugging mechanism in place during your development, and also, the sooner the better!

With this, the SVO was ready for path finding and following, I implemented a version of A* that considered heuristics like manhattan and euclidean distance, and also some weight modifiers like the size of the node and the effect of the selected heuristic. With the solution in place, then I needed a way to follow that path, thus, I plugged my navigation component with Unreal’s following component, and surprisingly it was very smooth, I created a navigation task that the AI could use at any time, both in code and in blueprints.

Additionally, navigation implementation, I developed an async version of this, which would enable to have multiple agents and high cost pathfinding calls. This wasn’t exactly easy as there is little to nothing documentation on Unreal’s async tasks library, but I managed to get it working, and improvement were significant.

After that, I worked on the serialization of the SVO, so it could be baked before runtime and used until it needed to be baked again. I have to say that this turned out to be a really helpful feature, since until this point I always had to generate the SVO during runtime for my tests, adding support for serialization allowed me to work faster in general, specially for debugging purposes, where I could generate the SVO while in editor and have it drawn without having to run the game. As for the implementation side, it wasn’t that hard, thankfully, Unreal has already support for serialization, to which I only had to create some overloads for my custom data types and explicitly enable the serialization for the SVO data.

When that was done, I started working on the final big feature of the project: dynamic obstacles. I am going to be honest, it was quite the challenge, but it was definitely worth it. So the idea basically was to enable support for dynamic updates on the SVO data, because, for instance some obstacles could be moving, so they would be affecting the navigation space, and because of this, the SVO data needed to be updated accordingly. One approach was of course, to regenerate the whole SVO when needed, which could be a very expensive operation depending on the resolution of the data. Therefore, a better approach was needed, thus I worked on a solution to only update the parts of the SVO that were marked as “dirty”, keeping track of these nodes and then updating them when needed, greatly reducing the problem space and overhead. I managed to finish a first pass at this feature and the performance improvements were huge compared to the naive solution.

With everything in place, I created a small themed demo, featuring all my work on the project, which I will be showing in my last presentation. I really enjoyed working on this project, I honestly love every bit of it, and of course I learned a lot. I am really proud of the results and I hope I can keep working on things like this in the future. Speaking of future, there is still much room for improvements and new different features related to this project, for instance, to further optimize the generation of the SVO, one could stream its data, when requesting a section for the first time it is generated but then it can be unloaded when not needed and reloaded when needed, which would be much faster than regenerating that part, this would basically be an improved version of my solution for the dynamic obstacles.

Oh, I almost forgot, I made another video of the demo with a larger Pac-Man to demonstrate the ability of the pathfinding to go through or around holes, depending on its size. Here it is:

This will probably be my last content update, I worked on the final demo and some metrics recollection for comparison and demonstrating why SVOs are so awesome.

So for the demo, I wanted to do something simple that used all implemented features at some degree: static SVO generation, pathfinding and dynamic SVO updates. I got this from my professor, making the agent a Pac-Man that would navigate a 3D environment a probably chase the player, so I worked on that idea to create the demo. I looked for some Pac-Man models and animations but turns out those are very scarce, not even paid, I guess it’s because it’s proprietary, but thankfully, I got help from one of my fellow artists, Alina, who modeled, rigged and animated a very nice Pac-Man for me to use in the demo. Below are some images of the level.

So the goal is to get as much fruit as possible without the Pac-Man catching you, he will also get fruit but if you’re close enough he will start chasing you, there are some moving obstacles around and some small entrances so that the 3D Pathfinding can be fully tested. Below is a video that better shows the demo.

Assembling this demo took a little bit longer that I had expected, making sure everything looked good and in place for the final presentation. I think it looks nice and shows everything that I worked on.

Now for the metrics recollection, I tested again the generation time and memory consumption of the unreal sample level as well as this new level assembled for the final presentation. I also estimated the data generated for other two solutions, a regular octree and a uniform grid. Below are the results of the collected data. The first table shows the data for a regular octree implementation where all the nodes are always present, and uses the same structure for the SVO in term of node and link size, remember that each node has a size of 40 bytes and each link has size of 4 bytes, additionally, each leaf node has an overhead of 8 more bytes due to the extra resolution leaf nodes used. The second table shows the data for a uniform grid implementation, where there are no layers and all nodes are the same size, for achieving the same resolution of an octree for a given number of layers, the uniform grid has 64 nodes per leaf node, for instance, if with 1 layer (0 and 1 really) there are 8 leaf nodes, in a grid there would be 8 * 64 = 512 total nodes, and if each node has six pointers for its neighbors and a flag for blocked or free, it would have a size of 25 bytes in a 32-bit system architecture or 49 bytes in 64-bit environment. The third table shows the results for the final demo level using the implemented SVO solution.

Layers	Total Nodes	Total Memory (MB)
4	4,681	0.21
5	37,449	1.68
6	299,593	13.43
7	2,396,745	107.43
8	19,173,961	859.43
9	153,391,689	6,875.43

Layers	Total Nodes	Total Memory (MB) – 64 bits	Total Memory (MB) – 32 bits
4	262,144	12.25	6.25
5	2,097,152	98.00	50.00
6	16,777,216	784.00	400.00
7	134,217,728	6,272.00	3,200.00
8	1,073,741,824	50,176.00	25,600.00
9	8,589,934,592	401,408.00	204,800.00

Layers	Total Nodes	Total Memory (MB)	Octree Improvement (%)	Uniform Grid Improvement (%)
4	4,009	0.18	14.6	97.13
5	15,033	0.66	60.8	98.68
6	51,033	2.22	83.5	99.44
7	188,251	8.23	92.3	99.74
8	708,833	31.01	96.4	99.88
9	2,796,329	122.60	98.2	99.94

The third table also shows the estimate for the memory consumption improvement over the other two solutions, and from it we can conclude that the gains are evident, using a grid for large sparsely populated environment is definitely a bad idea, simply because there would be too many unnecessary nodes, likewise for the full octree solution. Nonetheless, if an environment is heavily populated, then it would get pretty close to the full octree solution, but then it wouldn’t make sense to have this in the first place if no space is available for navigation. Therefore, SVOs are clearly superior for sparsely populated environments that are intended to have some space available for navigation.

Next week will be my last blog update, I won’t be working on new features, but I will keep working on testing this implementation and fixing any bugs should they appear. I will also be testing the plugin externally, ensuring it is as plug-and-play as possible. For my last blog post, I will be writing a summary of all the work done, my thoughts and conclusions from working on this project and a little bit about future work. As always, thanks for coming by and see you next week!

Yes!, as the title implies, I finally got the dynamic obstacles working (heck yeah!), but seriously, I must admit it was quite difficult. I really want to talk about all the details, so let’s get started.

Before getting to it, I want to discuss a little bit about an optimization relevant to both this new feature and the baked generation of the SVO. In some cases, I needed to get a certain node where I only had its layer and morton code, since I didn’t have a link to it, which would make it just an offset operation (O(1)), I was actually lineally iterating over the layer to get the node corresponding to the morton code I had. This is not that bad for lower resolution SVO where there aren’t many nodes in a single layer, but as the resolution and volume occupancy increase, it can get real bad. Thus, while I was working on the dynamic obstacles, I realized I was going to need a way to reference or find a given node even after the layers were modified and potentially reallocated, invalidating all links to them, therefore, I came up with a solution, which was to essentially save the morton code of the node, while it is not quite an index into the layer it can be used to find a node in a layer. I realized I was going to need to do this quite a lot, and doing O(n) searches was definitely not the way to go, then, I remembered how the octree was built, layer by layer, in ascending order from its morton code, What? Yes, the layers are already sorted by the morton code of their nodes, allowing for binary search (O(log n)), greatly improving performance. I collected some data for comparison with linear and binary search, which can be seen in the table below. The data represents, the time taken to generate the SVO for my whitebox demo map, with different layer configurations. An improvement can be seen, which increases even more the more layers or nodes in single layer there are.

Layers	Linear Search Time (s)	Binary Search Time (s)
4	0.037000	0.036000
5	0.175000	0.162000
6	1.070000	0.962000
7	6.922000	4.993000
8	83.878006	28.800001

With the binary search in place, I started working on the dynamic obstacles, I remember I spent a lot of time just thinking how to accomplish this, I must say it was very difficult, but it was also worth all the effort.

First, before even getting to the naive solution, which basically is just generating the whole SVO again (bad), I implemented a way of communication between dynamic obstacles and the volume they belong to. For this, I created an actor component that can be attached to any actor that might be a dynamic obstacle at some point. This component then has settings for enabling its dynamic behavior and send messages to the volume for requesting a recalculation. This is done via a timer event which fires at the provided rate, this is so it can be adjusted and tinker with, since different SVO configurations may or may not allow for faster/lower update frequencies. Thus, each dynamic obstacle sends a request for recalculation and then the volume handles these, marking the tree as dirty and updating itself in the next frame.

With the communication system in place, I was ready to test the naive solution and just regenerate the whole SVO again. It worked as expected, with poor performance for higher resolution octrees. I will be presenting a comparison after I go through the optimized solution.

In the better solution, I am tracking the nodes that the dynamic obstacles are currently affecting, that is, all the nodes that overlap with the bounding box of the dynamic obstacle, there is handy function for that already, which I am currently using, it gets the box that contains the collision components of the owner actor of the dynamic obstacle component, then I test for intersection for all the nodes, but since this is a sparse voxel octree, the obstacle is going to be contained in a single node, and some or all of its children, for instance this could be the entire volume, as to then the obstacle will be affecting the whole tree, or just a smaller node and some of its children.

The obstacle keeps track of these nodes and when it requests an update, the volume calculates the new set of affected nodes and updates the union of the two sets (previous and current). With this, we have all the nodes that need to be updated, so we proceed to the magic.

To update a node is basically to rasterize it again if it is currently blocked, or to remove it is no longer needed. First, if it is currently blocked, it is possible that we need to create children nodes for that node since it is now required, if the current node has no children and is being blocked, then we know it needs its precious children. When creating these, we will be essentially adding nodes to layers, remember that this invalidates all links so I am using the other referencing technique I describe earlier. But, we can’t just add these new nodes to the end of the layer, it would completely break everything, remember that we are now depending on the ordering of the data, therefore each node has to be inserted according to its morton code, luckily for us, finding the insertion index, is still fast since we can use binary search for the same thing, still slower than adding the node at the end, but definitely worth it. Luckily for us, the insertions can grouped by children of the same parent, since these are always contiguous, saving a bit on memory reallocations. Moreover, if the node being updated is a leaf node, it just needs to be rasterized for its 64 mini leaves and no new children need to be created.

Now, if the node being updated is not blocked anymore, it needs to say good bye only if its parent is not blocked either, which basically means that there is no need for that precision at that location anymore, this way, these nodes are calculated and removed, again potentially invalidating any links to current nodes. Removing nodes is also done in batches of 8, since these is an octree, if the parent is not blocked anymore then its 8 children need to disappear.

After all removals and additions are done, we need to restore the consistency of the SVO, specifically fixing all parent-child and neighbor links, it is possible that this can be done in a more efficient way, but for now I am traversing all the nodes and restoring their links. For parent-child links, they can adjusted easily since you can calculate the morton code of a child or parent having the other one, using simple bit magic, you can get the morton code of child by left shifting and that of a parent by right shifting, both by 3 (2 ^ 3 = 8). With the morton code, we can just binary search for the corresponding node in the layer, it must exist, if it doesn’t, it means something went bad when inserting or removing nodes in the update stage. Next, for the neighbor links, I am making the same call used on full generation, I am sure there is a more efficient way of doing this, since probably not all of the links were invalidated (probably), but for now this suffices.

I performed two experiments with the dynamic obstacles, the first one with a volume containing a dynamic obstacle and a few static obstacles, and the other one in my regular whitebox level, with many static obstacles and the dynamic obstacle. The results are presented in the tables below.

Layers	Naive Time (s)	Optimized Time (s)	Times Faster
5	0.053000	0.019000	2.7
6	0.290000	0.107000	2.7
7	1.510000	0.681000	2.2

Layers	Naive Time (s)	Optimized Time (s)	Times Faster
5	0.181000	0.012000	15
6	0.989000	0.082000	12
7	5.078000	0.495000	10

From the results it can be seen that where the optimized approach really shines is in the cases that there are also various static obstacles in the volume, as to which the naive approach will regenerate, while the optimized one won’t. From these results, it is evident that the performance gain is really good, and makes it more suitable for environments with combined types of obstacles, since if you only had dynamic obstacles, then both naive and optimized solutions would be identical. Therefore, for levels that contain both static and dynamic obstacles, the optimized approach is definitely the way to go. Below are three videos showing the optimized solution.

With this, the final feature of this project is done, the remaining work now is finalizing the demo and the final presentation, also collecting some metrics to demonstrate why SVOs are so awesome. See you next week!

If you recall, I mentioned last week that I was having problems with continuous async pathfinding and following, because if the Move To task was called on tick, the agent would continuous spawn an async task and abort it for the new task, leading to no pathfinding at all. I solved this by making sure it was done only if the target had changed and made sure to safely abort the current async task to use its resources for the new one. Obviously it wasn’t as simple as it sounds, I had trouble cancelling the current async task, it was crashing due to an assert inside the cancel function, which verified if the task was part of queue, so I had to step through the library’s code to see why it wasn’t letting the task go, even when the work was already done. My first approach was to synchronize the task, which completed the work if it wasn’t done and released the task, but that introduced another problem, if I had to synchronize the task to cancel it, I basically wasn’t really any cancelling, since it did the work anyway, which could be very expensive, and ultimately was equivalent to a synchronous call. Therefore, I had to come up with a workaround while I figure out why the queue is not letting me cancel the task, I am basically keeping an array of tasks while still having the current task, since I can’t reuse the tasks I instantiate a new one that runs on the async task library. All tasks are then deleted when the agent is destroyed, usually when the game ends. This is not ideal but works for now, and the improvement is quite noticeable as I no longer get blocked during pathfinding while moving through the environment in the demo. You can watch a comparison of the synchronous pathfinding (first) vs. asynchronous one (second) below.

The other part of this week’s progress is the serialization of the SVO data so it can be baked and reused as many times as needed, instead of rebuilding the whole tree every time in game. I have to admit this has been quite useful since now I don’t have to wait for the generation every time I need to test something in the map, I probably should have done this earlier, it really helps save on testing time.

Before getting on the serialization itself, I wanted to talk a little bit about some features I added to the editor details of the SVO volume, I created some custom buttons for the user to use for baking and clearing the SVO data. For this, I had to learn how to actually modify the editor details for any kind of actor, since it is something rarely used, there is little documentation, but there is definitely some. I added a new module to the plugin, this was a bit tricky since there is not an actual option in the engine to add a new module to a plugin, so what you have to do is manually added it to the .uplugin file like the main module and then add the files it would generate as it were a new plugin. This way, the engine will recognize the new module and add it to the solution when you rebuild these files. Once you have the new module, you just make it an editor module and create a class to customize the details of another class. All the buttons do is just call functions inside the volume.

To achieve serialization, you can use the serialization system already built into actors. I didn’t know how it worked, but now I do, any member variable marked as an UPROPERTY will be serialized since it needs to persists after the engine is closed to be used when the engine starts again. Therefore, these properties are already being serialized, but, I can’t simply mark as UPROPERTY the SVO data, since it is not public it can’t be exposed to the editor. That doesn’t mean we can’t serialize though, if you override the serialize function in your custom class, you can define custom serialization for you custom properties, so I do that. Additionally, if you need to serialize custom types, you have to create an overload for the << operator that takes in the custom type.

FORCEINLINE FArchive& operator<<(FArchive& Ar, TDPNodeLink& link)
{
	Ar.Serialize(&link, sizeof(TDPNodeLink));
	return Ar;
}

The above code snippet shows one of the overloads I created for supporting serialization of my custom types. Typically, if you have multiple data members, then you would serialize those as well.

Whatever you serialize on the function override will be stored on disk when you make changes to the properties in the editor and read when you start up the engine again. Remember that the data needs to be baked again if there are any changes in the generation settings or in the environment.

With this, we go into the final weeks of this project, I will start focusing on the dynamic SVO generation, so we can have moving obstacles in the environment, which is definitely not trivial and I will have to find various ways to reduce the problem space, so the complexity decreases but the results are still acceptable. That and setting up a nice demo for all these features will be the last epics for this project, I hope time goes easy on me for all the work that still needs to be done. See you next week!

This week was I gave a presentation about the current progress of the project, I would say it was fine, although I did take more time than I was supposed to, I really tried to keep it as short as possible, but I also wanted to share with everyone how the stuff I am implementing works because I really believe that it is a very interesting topic applicable not only to AI but to many other fields too. So yeah, I went a little overboard on my passion about the topic and tried to explain to everyone not only on a general basis but also the nitty-gritty details of it. It was absolutely worth it though.

So this week’s topic is Path Following, now that we have the path or list of points, we just have to follow them in order, right? It might look like a simple task and it could be done by just setting the current target and lerping between the two positions, but the goal was to integrate with Unreal’s AI system which uses a path following component with its AI controller. Therefore, I created a custom AI Move To tasks that is practically identical to the built-in one, with just a different way of requesting the path, which calls the custom path finding functionality in the navigation component of the AI controller. This custom path finding functionality refers to the selected algorithm (currently only A*) and finds a path between the two points. Then, when the algorithm is done, the results are translated to the structure Unreal uses for its path following component and then the movement is requested based on the found points. This is how I found a terrible bug inside the path finding process. See the image below.

If you watch closely, you’ll notice that the path is telling the agent to go from node 4 to node 5, but there is something strange with it, yes, there’s a huge obstacle in the middle and the poor agent is trying desperately to complete its task. Since I didn’t want this agent to keep suffering, I started trying to fix this situation. Most of the time spent solving this was actually finding the place the error was coming from, that is why I cannot recommend enough to always have debug helpers of any kind, visual ones are even better, anything to help in this kind of situation. After placing more debugging visualization for the path planning step, specifically the evaluated neighbors for every expanded node, I finally found it.

From the above images, it is clearly seen that the neighbors for that current node weren’t quite right, it was getting a non-adjacent node as a neighbor, which is definitely in this occasion. The actual solution was not event that hard, it was kind of dumb actually, I was using the wrong variable for getting the neighbors down the hierarchy, in other words, I was using a parent’s instead of the current node’s neighbors when getting the lowest possible neighbors, so I just changed the name and it started working like a charm.

†††††For the AI Move To task, I implemented the ability to choose either synchronous or asynchronous. For the async part, I am using Unreal’s async task library which uses its internal thread queue. To use this library, you only have to create a class which inherits from one of their base classes and then implement some functions so it can be used by the thread queue. Specifically, there’s a DoWork function where the work that the task’s supposed to do is supposed to be placed. †Here is where the path planning is located for the async version.

For demo purposes I ended up calling the AI Move To task every frame to follow the player around the map. This works normally for the synchronous version, if the path planning is not that expensive then you can’t really notice the difference, but when it gets like that then you can definitely notice it. The async version works as intended but the problem I am currently facing is calling it on tick. It ends up doing nothing because it is starting a new thread every frame, discarding any previous work. I will iterate over this and hopefully find a way of having the async version capable of executing periodically as much as on tick. You can see a demo of the path following in the video below.

As for work to come, I will be focusing on the async version like I said. I will also be working on a way to serialize the data generated for the SVO, since that is static data, it can be calculated before game execution and then just loaded in game instead of calculating it at runtime, which can take some time depending on the complexity of the SVO and blocks the game execution. I am also planning on tackling dynamic obstacles inside the volume, which would trigger recalculation of some of the areas in the octree, so the hard part is to find how to efficiently update the octree and not just update it as a whole, which would be pretty expensive and ultimately useless for complex SVOs. An updated version of the remaining schedule can be found below.

Week 7 (We’re here!)	Addition of multiple heuristics for comparison Path Following Project Status Update
Week 8	Path Following adjustments and iteration Continuous Async Path Planning SVO Serialization
Week 9	SVO Serialization (cont.) Dynamic SVO
Week 10	Dynamic SVO (cont.) Polishing, bug fixing and demo preparation
Week 11	Plugin export and external testing
Week 12	Final Presentation

Yes! I am finally doing pathfinding and it’s awesome, but first, I would like to discuss some things about the SVO and its generation. There’s actually a lot to cover in this update so let’s get started.

I don’t think I ever mentioned how I am telling if a given voxel or octree node is blocked or partially blocked, which makes it split into children nodes, until the desired resolution is reached. I am using Unreal’s built-in functionality to tell if there is any geometry collision inside a given collision shape. You can find additional information about this function here. Basically, the function receives a shape, its size and its origin to create it, and test if there’s any blocking geometry like meshes or blocking colliders that overlap that supplied collision shape. Since octree nodes are voxels, the shape I am using is a simple box which exactly resembles its debugging visualization, therefore, if there’s any blocking objects inside the voxel, it should be marked as blocked and the corresponding logic should follow. While testing the generation in different environments, I found that the collision function has an additional argument for choosing between simple and complex collision for the test. If we refer to Unreal’s documentation, simple collisions use primitives like boxes, spheres, capsules, and convex hulls, while complex collisions use the trimesh of the given object. Whether you choose simple or complex greatly affects the outcome of the SVO generation.

• 

• 

The difference can be seen in areas like the stretched sphere on the left and the two nut-like shapes that are completely ignored with simple collision. I added an additional parameter for the SVO generation to decide whether or not the collision test should be simple or complex. If the environment contains mostly simple shapes then simple collision should be enough, but if there’s a bunch of complex geometry and you want to make sure that all of that is navigable then complex collision should be used instead, but don’t forget that this means more overhead for the engine internally (for handling complex collisions in the game) and for the SVO generation that potentially would need to create more nodes, increasing processing time and memory usage.

Just like I said last week, I worked on some metrics recollection for the SVO generation in different environments, I tested my whitebox level as well as a full sample level from Unreal’s marketplace. Below is some of that data. The first table refers to the whitebox level and the second one is for the sample level.

Layers	Total Time (s)	Total Nodes	Leaf Nodes	Memory (B)
4	0.096	3,841	3,264	179,752
5	0.454	18,897	15,056	876,328
6	2.640	80,721	61,824	3,723,432
7	31.567	328,673	247,952	15,130,536
8	460.118	1,320,161	991,488	60,738,344

Layers	Total Time (s)	Total Nodes	Leaf Nodes	Memory (B)
4	0.096	1,569	1,224	72,552
5	0.602	7,633	6,064	353,832
6	3.723	41,153	33,520	1,914,280
7	26.900	222,441	181,288	10,347,944
8	359.642	1,144,209	921,768	53,142,504

The data shows the tendency of the quantity of nodes and time takes is exponential, which makes sense since the each node splits into 8 eight more if blocked, and the same happens to every subsequent node. To calculate at most how many nodes would be in a given layer, you can use the following formula:

nodes = 8 ^ (total_layers - layer)

Or you can just use layer instead of the subtraction if you take the 0th layer as the outer-most layer instead of the inner-most one. That will yield the maximum amount of nodes in a given layer, that is, if all nodes are blocked, as if the whole volume was blocked. If that were the case, it would actually be worse than a fixed size grid. This is why and SVO if superior to grids, they don’t waste resources when they’re not needed, like in open space areas. Now that we’re talking about quantity of nodes in layers, I want to clarify something about a statement I made a couple of posts ago, I said that because of the way links worked, where I have 22 bits of a 32-bit integer to represent the node index, I could only support up to 7 layers since 2^22 = 4,194,304‬ and 8^8 = 16,777,216. This last number represent the amount of nodes you would have in layer 8 if all nodes in the octree where blocked and thus had to be generated, but since that is not always the case, you could probably have more layers if the blocking objects inside the navigation volume were not that many. Therefore, there is actually space for 2^22 nodes per layer, which actually applies to the last layer, since it is always the one will have the most nodes in the octree. If you’re last layer has at most 2^22 nodes then you’re safe! Below are some images I took from the data recollection I did.

If you payed attention to the tables I placed above, you might have noticed that there is actually less data created for the sample level than the whitebox level, if you’ve been paying attention to my explanations and I hope I am being clear ans simple enough (I am trying my best here!), even if the volumes are of different size, like a small whitebox level and full size sample map, the resource consumption actually depends on the number of layers (precision) you choose. Make the volume bigger only means that the nodes will be bigger, and will potentially decrease the amount of the generated nodes since it is possible the there will be less occupied (blocked) space, so there will be more empty space, which translates in less nodes (less memory and processing time). Therefore, for the same number of layers, if you have a smaller navigation volume but with most of its space blocked, it will actually consume more resources than a bigger level with a smaller occupied/free space ratio.

Alright, now we can start discussing this week’s main topic, yes, Pathfinding, I finally got to the part where I could perform the path planning, but before, I needed a way to get all the neighbors from a given node for the pathfinding algorithm. Thankfully, we already did most of the work last week. Every node has a link to its neighbors, but like I mentioned last week, nodes have neighbors in the same or upper layers, not in lower layers, therefore, there is additional work needed when getting the neighbors of a given node. Basically, what this means is that I need to get the inner-most children of the stored neighbor if there are any, otherwise that same node is added to the neighbor list. To better explain this, when getting the neighbors of a node, you either get the direct neighbor if it has no children, which means it is empty, or you get the inner-most children until it is a leaf node, which then means that it has the extra 64 highest precision nodes, and 16 (face) will be evaluated to see which are not blocked (ith bit set means that it is blocked), and thus added to the neighbor list.

There is also an issue or concern that raised during the neighbor calculation, I realized that I am not considering the size of the agent for this stage of the pathfinding, so if the size of the agent surpasses that of the node, even if that node is empty (traversable), the agent won’t be able to navigate it. This is an actual issue that will become evident when I integrate the pathfinding with Unreal’s pawn and AI controller system. As a temporary measure, I added another variable for the SVO generation that serves as additional clearance for when determining if a given node is blocked by an object, which makes the collision shape bigger, and the nodes that might not normally be blocked are now blocked, therefore, smaller empty spaces are now not traversable. This is not ideal, but works for now. The alternative would be to actually discard neighbors based on the size of the agent, which I will try to address when integrating the pathfinding with the Pawn and AI system.

I am using plain old A* for the pathfinding algorithm, getting the neighbors like described above. Since I can’t store information like parent, path cost and heuristic value in the nodes themselves (this would increase memory usage significantly), I am using maps for storing these values. Also, for the priority queue, it turns out that Unreal’s TArray actually supports heapifying the collection, using the less operator of the data type or using a predicate passed in an argument. Since I need to use the maps to get the values for the path cost and heuristic, I created lambda function that captures these maps and calculates the total cost for a given node. I also added some configuration values for the pathfinding:

• Using Unit Cost for the nodes, and its corresponding value. If Unit Cost is not used, the traversal cost from one node to the other is the euclidean distance between them.
• Heuristic Weight, which is basically a multiplier for the heuristic value. Setting it to be different from 1.0 will make the algorithm either ignore (< 1) or prefer (> 1) the heuristic estimation.
• Node Size Compensation, a multiplier for both the heuristic and the path cost. Making this value greater than 1 will increase the cost and heuristic for smaller nodes, making bigger nodes more appealing to the algorithm.

I made some initial tests and I also implemented a basic version of the debugging visuals for the pathfinding result, currently, only the final result is drawn, but I want to try and add a more detailed visualization of the path planning stage. Some images of the tests are displayed below:

As you can see, the agent is still not navigating, so that’s what I will try to do next, besides preparing for next week’s Status Update Presentation, for which I will have to prepare a presentation and a demo with my current progress. Also, while implementing the navigation, I don’t think I have mentioned this but currently, the call for finding the path is in the game’s main thread, which makes it a blocking call and halts game’s execution while doing path planning, certainly not ideal. Therefore, I will also look into making the path planning asynchronous so it can be integrated with Unreal’s Pawn and AI system.

Make sure to come by next week when I’ll be talking about how my presentation went!

So I want to start by commenting on the strange bug I had last time with the plugin compilation. I followed the same steps I did on my machine on another machine with the same version of the engine and got exactly the same weird bug. So I guess it is an actual issues with the latest version (4.22.2), which always fails on build when you create a new plugin to work with within your project. I found a temporal workaround that I discuss in my previous post if you are interested. That being said, I will also be filing a bug report on Unreal Engine’s forums.

I also would like to explain a bit more about my debugging visualization before getting into the main subject, what you see in the image below is each voxel (octree node) in the octree drawn as a box with a specific color that represents the layer the belongs to. Thus, you can see that wherever there are blocking objects inside the SVO volume, there are more voxels or nodes to around the blocking object to effectively determine the navigable space with higher precision (smaller voxels).

As I mentioned, each color represents the layer the node belongs to, for this I have an static array of colors for all possible layers and then I just get the corresponding color when drawing each voxel layer by layer. The colors I am currently using are:

• Yellow for layer 0 or inner most layer (highest precision layer)
• Blue for layer 1
• Red for layer 2
• Green for layer 3
• Orange for layer 4
• Cyan for layer 5
• Magenta for layer 6
• And black for layer 7

Alright, now that we got that out of the way, we can finally get started on the progress for this week’s update. If you recall my last post, I mentioned that some work was remaining for the octree to be fully traversable, which basically included the setting of the parent-child and child-parent links, as well as the neighbor links for each node in the octree.

First, for the parent-child and child-parent links, I followed the book’s idea to set these while creating the octree layer by layer from the bottom to the top. This process has to be separated for handling the 0th layer and the rest of the layers. For layer 0, when a node has to be added to this layer because its parent is blocked (in layer 1), the node is rasterized to set all the 64 extra precision leaf nodes inside this octree leaf node. In this same step, its first child link is set to the current leaf node index in the list of extra precision leaf nodes. After that, for all the other layers, I check the previous layer to see if the hypothetical child node (using left shifting) was added to that layer during its rasterization, if the child node does exist, then that means links between the parent node (current node) and its children have to be set. Remember that setting a parent-children link is just setting a link to the first child since you can get the other ones by offset. Thus, the first child link is set in the parent, and for each child (always 8), its parent link is set to the current node. If no child is found then the link is invalidated. The code excerpt below shows this logic.

// set parent -> first child link
auto& firstChild = node.GetFirstChild();
firstChild.SetLayerIndex(layer - 1);
firstChild.SetNodeIndex(firstChildIndex);

// set children -> parent links (exactly 8 children)
auto& octreeLayer = mOctree.GetLayer(layer - 1);
for (int32 childOffset = 0; childOffset < 8; ++childOffset)
{
    auto& parent = octreeLayer[firstChildIndex + childOffset].GetParent();
    parent.SetLayerIndex(layer);
    parent.SetNodeIndex(nodeIndex);
}

The image above shows the visualization of parent-child links, as well as the morton code for each node. Remember that the purpose of morton codes is to map a set of 3D coordinates (position of each node in this case) into a linear array. Therefore, for each layer, each node has a unique morton code which represents its index in the array. As you can see in the image, for layer 2 (red) there is only node (the volume itself) and its morton code is 2:0, 2 for the layer and 0 for its index in the layer. Similarly for layer 1, there are 8 nodes total (children of layer 2’s only node), which codes go from 1:0 to 1:7. So on and so forth for the rest of the layers. Moreover, the parent-child links are drawn from the origin of the parent to the origin of the first child. Thus, in the image, one can see that the node 2:0 has a link to its first child, which is node 1:0. Likewise, for node 1:7, which has children leaf nodes (yellow voxels), a link was set to its first child, node 0:0.

After the octree is completely rasterized and all the required nodes are in place, I proceed to set the neighbor links for every node. Since the nodes are cubes, they can have at most 6 neighbors, one for each face. The process of setting these neighbors is done traversing the octree from top to bottom. The highest layer is ignored, since it only contains one node (the volume itself), so it has no neighbors. The process of finding a neighbor for a given node goes as follows, first, while in the same layer, each of the possible neighbors is evaluated to see if it’s valid, getting the possible neighbors is done by offsetting the current node’s morton code by the six possible directions (left, right, up, down, forward, backward). The resulting morton code is located either before or after the current node in the sequential array of the layer. This way, the neighbor morton code is looked for in the corresponding array by going to the right or the left, and if found the link set, otherwise, we have to start looking in the next layer up the hierarchy. This ensures that every node has a link when it has no direct neighbor in the same layer but might have a neighbor with a node in a higher layer. To do this, when a direct neighbor is not found, I get the parent node of the current one, luckily we already set all the parent-child links in the previous step, so we have all that information ready to be used. Since we were unable to find a direct neighbor, the neighbor then becomes the closest valid neighbor of any of the parents in the hierarchy (parent, grandparent, …), until we get a valid neighbor or simply there isn’t one, as to which the neighbor link is invalidated. The image below shows the visualization of the neighbor links.

In the image above, you can see the neighbor link as straight lines from the origin of one node to the origin of the other node. You can visualize both same layer neighbors as well as different layer neighbors. For instance, in layer 0 (yellow), node 0:7 has neighbors 0:6, 0:5, 0:3, and 0:11; and node 0:1 has neighbors 0:3, 0:0, 0:5, and 1:1, this last one, it’s in layer 1, but was still set as a neighbor since it has no children, and is the closest in the hierarchy to be a neighbor for 0:1 in that direction. To clarify, 0:1 has neighbor 1:1, but 1:1 doesn’t have 0:1 as a neighbor, since it has a direct neighbor which is 1:3 in the same layer. I also added the possibility to visualize invalid links, the image below shows an example.

The invalid links in the image above are basically the ones to nodes out of the bounds of the octree.

With this, the octree is finally ready to be traversed by a pathfinding algorithm like A*, thus, I will begin the implementation of said algorithms with different heuristics for comparison. I would also be working on metric recollection for the generation of the octree in different sized environments with variable amount of blocking objects to measure their influence and the generation performance.

No new referenced material this time, I am still following the Game AI Pro 3 book, which I’ve found really helpful not only for this specific topic but for many others as well. If you’re interested in any AI related subjects, I would strongly recommend getting the book, you can check the discussed topics on their webpage. Alright, that’s all for now, I can’t wait to get started on the octree traversal and pathfinding implementations. See you next week!

Hello there, glad to have you here again. So I finally started the development of the project, and guess what, problems sprung out right from the start. Yes, I had trouble creating the initial project setup.

Since I am targeting a plugin export I tried creating a plugin project from the unreal editor, yes, you don’t have to do this, you can also just work on a normal project and then migrate all the library code to a plugin structure so you can export it, but this only means dealing with the plugin part later on, so I decided to just get started with that sorted out. The issue I was having was trying to recompile in editor would throw an error every time because it couldn’t find the files of the plugin output even if it was compiling everything successfully and creating all the files. After looking for a solution for quite a while, I found two that were able to solve the problem. The first one is to compile on Visual Studio and reopen the editor which will then magically say that everything’s fine, but reopening the editor every time you want to test your changes is just absurd so that solution was a no go. The other one was to use the modules window under Window -> Developer Tools -> Modules, and recompile just the plugin module, which will be alongside the other modules in the list. With that said, there is still an issue that happens sometimes, compiling the plugin will not always hot-reload the objects in the editor so you’ll have to check the Output Window to see if the module was unloaded and loaded again, if it was not, then you can just recompile the plugin again in the modules window until the output says that it reloaded the module. Oh, I forgot to mention I am using UE4 4.22.2.

With the plugin stuff sorted out, I finally got started on implementing a first pass of the Sparse Voxel Octree. I am using Daniel Brewer’s article on Flight Navigation in the Game AI Pro 3 book as a reference, where they say how the SVO is structured and generated. They start by talking about how they encode each node data, introducing the concept of Morton Codes. That is something I had never heard before and is a really interesting and smart technique. It basically maps three-dimensional coordinates into a one-dimensional sequence. There are plenty resources online about Morton Codes, I specially found useful this article from Asger Hoedt, and this article and library from Jeroen Baert. So then, why should we even care about how the node data is stored? Well, if you’re levels start getting really big with an increasingly number of obstacles, then the SVO starts consuming a lot of memory, therefore any memory optimization that can be made to the octree structure is very much welcome and needed. Moreover, an additional problem arises with a heavy use of memory… did you guess it? No? Wait, I am going to let you think for a moment… still no clue? Alright, we get a performance hit if the data is not locally coherent, imagine traversing your octree with thousands of nodes, each one sparsely residing in memory, definitely not okay! Luckily for us Morton Codes exist, and they can be used to flatten the entire three-dimensional octree into a linear, one-dimensional array. If you want to know more about why preserving data locality is important, I would recommend watching this talk by Mike Acton.

Following the article, the nodes then require a position (Morton Code), a reference to their parent, a reference their children and reference to their neighbors. Wait, that looks like a lot of pointers, right? Let’s count them: 1 (parent) + 8 (children) + 6 (neighbors) = 15, which might not seem a lot since their are just 4-byte addresses, but consider that you will likely have a ton of these nodes, so these kind of things start to matter, also remember that address size depends on the system architecture and can also have a size of 8 bytes, doubling the memory required for the nodes. Therefore, the way this addressed in the article is by using links, which is just a 32-bit integer that stores the reference data for a given node. Thus, nodes have a link to their parent, a link to their first child, which is enough since nodes are stored in Morton Code order, making them accessible via offset, and a link for each neighbor. Let’s see: 1 (parent) + 1 (children) + 6 (neighbors) = 8, which is already way better than before. Leaf nodes are handled differently. They have children nodes that are not part of the octree but are only used for collision purposes, which means we only need to know whether they are open or blocked, thus, making one bit just enough to store their data. This way, leaf nodes have an additional 64-bit integer to store their additional children, where each bit determines if a given highest resolution voxel is blocked (1) or not (0).

struct Link final
{
    uint32 LayerIndex : 4;
    uint32 NodeIndex : 22;
    uint32 SubnodeIndex : 6;
}

The above code snippet shows how the links are structured, you can see all the data fits nicely in a 32-bit integer, however, this constrains the octree to have no more than 16 layers, no more than 4.194.304 nodes per layer and no more than 64 subnodes (which only apply to leaf nodes). If you see the restriction for the node quantity, you’ll notice that at most you’ll be able to have 7 layers (8^7 = 2.097.152 and 8^8 = 16.777.216).

Now, with all the infrastructure done and ready to be used, we proceed to actually creating the SVO, detecting collisions inside the bounding volume, and generating all the required nodes based on different parameters such as maximum layer quantity. The process presented in the book describes a bottom-up construction, doing each layer at a time, thus preserving memory coherence and allowing for parallelization to speed up the process (It might be worth looking into the latter in the future).

For the bottom-up construction, the first step is to calculate how many leaf nodes (layer 0) are required, therefore, we rasterize at a layer 1 resolution, performing the collision checks with voxels from layer 1, which size depends on how many total layers there are. I am doing the collision queries with the built-in Unreal method for checking overlaps by collision channel and shapes. If a node at layer 1 is blocked, then it means that node will have 8 children which will be leaf nodes. After rasterizing layer 1, we can find all the other nodes higher in the tree that are also blocked, because for every highest resolution node blocked, all its ancestor nodes will also be blocked. We can get the parent Morton Code by just using bitwise operations (right shift by 3 to get the parent Morton Code for a given node). All these codes are stored in a set by layer to avoid duplicating parent nodes in the blocked group (the 8 children’s Morton Code will yield the same parent Morton Code). After the this first rasterization, the number of leaf nodes required will be 8 times the number of blocked nodes at layer 1.

With the information from the first rasterization, each layer is then rasterized from highest to lowest (0-Max). For layer 0 (leaf nodes), an octree node and its respective leaf node are created, the leaf node is blocked, it needs to be rasterized to get the additional 64 voxels for higher precision. The process of rasterizing the other layers is just going through all the possible nodes and checking whether or not they are currently blocked, which is when a new node is added to the list. To do all this process, I needed a way of calculating the three-dimensional position from a Morton Code and the information available from the bounding volume (origin and extents). Once decoded, the Morton Code will provide a uniform position inside its parent node, and then the world position could be calculated using the origin and extents from the bounding volume and the size for voxels in the current layer. The formula looks like this:

position = Origin - Extents + (size * mortonPos) + Vector(size / 2);

With this, the position of any node in the octree can be calculated from its Morton Code and its corresponding size according to its layer. To calculate a node’s size according to its layer, remember that when a node has children, they are always 8 and thus have half their parents’ extents in every axis.

Without further ado, I present the first results of the octree construction.

All the images were taken using an octree generation with 5 layers. The last 4 images show also the extra precision leaf nodes inside each real leaf node. Enabling the debugging visualization for the extra leaf nodes can rapidly affect performance due to the large amount of these leaf nodes, but I think it looks cool, seeing that these leaf nodes are trying to match the blocking shape.

That certainly was a lot of work, and there’s still much to be done, the octree generation is not yet finalized, I am still missing the setting of the various links inside each node, needed for actually traversing the SVO. I feel like trying to explain a lot of things required for this part was not that easy, heck I don’t even know if I understand it fully myself, I hope we both can get better at this as go forward. Thanks for reading and expect more very soon!

As usual, here are my cited works and references:

• Game AI Pro 3
• Libmorton v0.2
• Fast Parallel Surface and Solid Voxelization on GPUs, Schwarz and Seidel
• How to Write Code the Compiler Can Actually Optimize, Mike Akton

Yeah I forgot to post my schedule and add a link to the repository for the project, so here they are:

Week 1	Proposal Research and Presentation
Week 2	SVO Research and Design
Week 3	SVO Implementation
Week 4 (We’re here!)	SVO Implementation (cont.) SVO Debugging Visuals
Week 5	SVO Implementation (cont.) Testing and Debugging
Week 6	A* (& Greedy) Research and Implementation
Week 7	Comparison of various heuristics and algorithm variations Project Status Update Dynamic SVO
Week 8	Debugging visual for Pathfinding Dynamic SVO (cont.)
Week 9	Pathfinding testing and debugging Dynamic SVO (cont.)
Week 10	Demo preparation
Week 11	Plugin export
Week 12	Final Presentation