• Register

Floatlands is a lowpoly survival-exploration fps game where you play a robot as the main character, going up against other robots in a procedurally generated world.

Post news Report RSS Floatlands devblog #4 - pathfinding

The process of creating volumetric pathfinding - how mobs/enemies find their way to targets in the game.

Posted by on

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.

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.

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?

Post a comment
Sign in or join with:

Only registered members can share their thoughts. So come on! Join the community today (totally free - or sign in with your social account on the right) and join in the conversation.

Follow Report Profile
Icon
Floatlands
Platforms
Windows
Developer
6Pills Games
Engine
Unity
Contact
Send Message
Homepage
Floatlands.net
Release date
Game watch
Follow
News
Tags
Dev Diary
Browse
News
New
Post news
Report
Report
Share
Related Games
Floatlands
Floatlands Adventure
Related Engines
Unity
Unity Commercial
Related Groups
6Pills Games
6Pills Games Developer
Indie Devs
Indie Devs Hobbies & Interests with 1,649 members
Steam Greenlight
Steam Greenlight Entertainment & Press with 216 members
Unity Games
Unity Games Hobbies & Interests with 1,807 members