# Devblog 4 – Volumetric pathfinding graph

Hey guys!

Vili here, one of the developers in Floatlands team.

I will explain the pathfinding and reasons why we need this in our game.

Common pathfinding is for ground mobs only. I wanted to have also mobs that fly and walk on walls / ceilings. For this we need special path-finding, if we wish that enemies find a way to their target. I was looking for a solution and there was none, so I programmed my own.

I used oct-trees, which are really just an extension of quad-trees. I constructed oct-tree by casting cube to world for each node – if anything is hit by BoxCast, subdivide. Repeat this until you hit maximum depth of nodes. I used Unity3Ds function ‘Physics.CheckBox’.

I visualized my algorithm, and pretty pictures happened – what you see next is leafs of solid. You can see this can get quite heavy, because each subdivision generates 8 times more nodes.

Solid leafs of ground and wall (and also ceiling).

If I wanted to have a proper graph, I needed to make it also topologically correct. This means I needed to do flood-fill algorithm to separate free-space from solid-space. This way mobs can exactly know where they can walk (and can’t).

Von neumann neighborhood queue flood fill in 2D

This is the result of flood-fill. I started from free-space (top most node) and searched through whole space. This way I could separate reachable and unreachable space.

The camera is under the ground and so is the part of mountain.

Did I mention before about the resolution problem? Well, there is a big problem. Each subdivision is 8x times more expensive. Time and space requirements grow exponentially. BoxCasting becomes expensive, so does flood-fill. But there is a simple solution: subdivide only parts that need to be subdivided :). So I coded a simple trigger, which will mark space that needs to be detailed.

Green box is a collider

Each prefab gets its own trigger. It can be a box or sphere collider.

Now, we have proper nodes. Now I needed to generate points (with normals) for each node. I did it by raycasting from many directions (borders of node) and then averaging the points. Also I calculated the average normal – slope, so I can separate ground from wall/ceiling.

This is the result:

Points with normals – needles

Now another step – connect the neighbor nodes, so we get a point graph. Here, I used ‘moore neighborhood’ for connections, this way I also get diagonals.

End result

If you want to see what a mess fully drawn graph is – including free-space nodes, look here:

Quite complex structure

Then all I needed to do is input this point graph into A* Pathfinding Project made by Aron.

Examples of working path-finding:

Wall & Ground path

Air only path

That’s all folks, quite simple eh?