Hey everyone,
Domen Koneski (game designer and programmer) has been working on the island generator, he added every asset that our 3D artist had for him – from a small firn to a huge tree. With this he also successfully implemented a LOD system and found a cool ambient occlusion system which was also added.
Resource gathering system is now improved, you can now harvest wood, wool, experience points and rocks.
Vili (programmer) explains 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 pathfinding, 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.
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. Then all I needed to do is input this point graph into A* Pathfinding Project made by Aron. That's all for now.