Hi, Vili here!
I'm one of the developers in Floatlands team. I will explain pathfinding and the 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.
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).
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.
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.
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:
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.
If you want to see what a mess fully drawn graph is – including free-space nodes, look here:
Then all I needed to do is input this point graph into A* Pathfinding Project made by Aron.
Examples of working path-finding:
That’s all folks, quite simple eh?
