Tag: SVO

So it begins…

Hello there, you just arrived to the first post in the series, so let’s start with a brief introduction:

I am Camilo Ruiz Casanova, I am currently in grad school at FIEA and I like to write code. There, we have something called PPP, which stands for Personal Programming Project, and is pretty much the final project for the programmers. This project is topic free (programming related), so everyone chooses something different to work on an then makes a proposal with a presentation, which happened last week. So yes! I already decided what I will be working on, and I will be documenting my progress on this blog as I go. Hmm? What? You want to know what my project is about? Well you’ll have to wait until next post… just kidding, I will be describing all about it right away.

Before I start talking about my project, I want to talk a little bit about my inspiration. I really like AI, and is what I want to specialize in as a game programmer, so I knew what the domain of my project was going to be, but AI is a really extensive and broad field, so I had to find just a tiny bit inside it to give it all I’ve got. Thus, I started thinking about games I like and have recently played, there aren’t many really, as grad school is really unrelenting, specially FIEA, so I thought about one of my favorite games, and probably the one the most hours I’ve put into throughout my life *drum roll*: Warframe, yes Warframe, I’ve been playing since it came out back in 2013, and I just love how you can see the dedication and effort its developers have put through all the years of evolution and growth, I do think it is an amazing feat to stay relevant and fun, as well as to continue growing even more after all that time. Okay enough Warframe (as if that were possible), so I had a field and a game, what could I possibly come up with having both things in mind?, I did some research and I found they actually have a couple GDC talks about their AI in Warframe, pretty lucky right? So I watched them and found something that really sparked my interest: 3D Pathfinding.

3D Pathfinding means finding a path between two points in 3D space, and is mostly used for entities that need to navigate in a 3D space, for instance birds or space ships. In Warframe, there is a subset of game modes called Archwing, which takes place in outer space, thus, the enemy needs to be able to traverse such space and fight the player, this is where 3D Pathfinding comes into place. Regular 2D pathfinding works by mapping the walk-able surface of an area into a graph, which is then used by a pathing algorithm like A* to find a path (optimal in the case of A*) between two nodes in the graph. So this means that A* doesn’t care about the space or world itself, it just needs a graph of nodes to work with. Thus, the problem is how to map the 3D space we have now into a graph. There are some techniques that can be used, as described in the GDC talk, but one of the best is by far using a Sparse Voxel Octree. An SVO, is a common rendering technique used mostly in graphics to represent space. It basically fills up a volume with cubes, which can be filled with 8 cubes depending on the desired precision, this way only cubes where more precision is required are split, saving resources. Thus, the SVO creates a graph of nodes, which then can be used by the pathfinding algorithm to perform the path planning.

Very Small Sparse Voxel Octree

For my project, I will be replicating the work presented in the GDC talk, and in the Game AI Pro 3 book chapter about Flight Navigation by Warframe’s Lead AI Programmer Daniel Brewer at Digital Extremes. Thus, I will be working first on creating the graph by using an SVO and then I will implement different versions of A* with different heuristics to compare their performance in different environments. I will be setting up a demo to showcase the SVO creation and also the path planning process and solution. For this, I will be implementing different debugging visuals to correctly show the different outputs of the project. Finally, -and I almost forgot- I will be trying to export this a plugin for the Unreal Engine, which is the engine I will use for my project.

The proposal presentation went well, and I had some feedback that I would like to share. First, my professors asked me if I was planning on doing any avoidance for the agents, which could be implemented as a steering behavior or even more related to my project, as dynamic obstacles that trigger recalculation of the SVO so affected agents replan their path accordingly. This introduces even more the concept of optimization, since creating the SVO can be very expensive, triggering recalculations during runtime could come up pretty heavy if no optimizations are performed. The other piece of feedback that I had referred to how I was planning on demoing all this. I initially thought about just assembling a whitebox level using simple shapes, but maybe I will try to get some assets either from the store or even better, asking a co-student in another track like art or design to help me set up a nice looking demo, which would be pretty nice.

I already started doing some deep research about SVOs, and found something pretty interesting I hadn’t heard before: Morton Codes, a technique to map 3D vectors (from the SVO for instance) to an array of integers so data locality is preserved, which is very important. I will go deeper into this in future entries.

I hope I didn’t bore you with all these text, I usually don’t talk or write much, I guess that’ll be changing for the following weeks. I have to say that I am really excited about this project, I guess that was expected given how much I like both programming and Warframe, so the idea of working on something related to it it’s just amazing.

Have a good one and I hope to see you on my next update! –wait, why do I feel like I am forgetting something? Hmm…– Oh that’s right, here are the references I used: