I’m trying to implement a path-finding technique into my game whereas enemy air-ships will need to find a safe route to the player. But the air-ships can move in 3D - rather than a single plane of movement.
I’ve been told that since I’m using wide open spaces with few, but complex (windows, multiple entries + exits, not simple shapes) buildings - that I should use a nav-mesh in 3D.
So basically I’d need something like A* but applied in 3D… Now the algorithm I can see is much the same; I just have no idea how I’d implement this in Unity?
A* can work just as well in 3D as 2D. If the airships are free to move anywhere in space, you will probably want to define a 3D cubic grid, with each cube being roughly the size of an airship. Essentially, the search proceeds as in 2D, but the neighbours of a given cube are all the others adjacent to it in 3D space. You will need to determine which cubes are impassable due to the presence of other airships and removing these from the search space.
If the airships can only occupy a set of fixed positions in space then the task is a bit simpler. An existing A* implementation designed for 2D can probably be used with little or no modification.
Do the airships just need to navigate around the buildings to find their way to the player? Also, is altitude a factor? That is, can they fly over buildings?
Finally, is there anything that they can fly both over and under? (E.g. a bridge…)
Yes, airships just need to navigate around to find the player. You can fly over buildings, and some buildings you can also fly through; (no complex inner-shape, literally just an open corridor through the building).
There are also bridges, yes.
@Rapzid - I can’t seem to find anything about Portal Pathfinding on the internet? I’ll keep looking - but do you have any links?
I searched for it too, and the only hit was this thread Anyway, I’m pretty sure there’s no specific technique by that name (I’ve never heard the term, at least).
It does seem like a navigation mesh would be a good solution here. Polygons in the navigation mesh could store information about what altitudes were accessible within the polygon. For example, the altitude information for a ‘bridge’ polygon would indicate that altitudes below the bottom of the bridge and above the top were open. Tweaking edge costs based on absolute altitude, relative altitude, and ‘maneuvering room’ would cause your airships to make ‘smart decisions’ about which path to take.
Navigation-mesh-based pathfinding systems aren’t necessarily trivial to implement, so you might start by looking for existing solutions that could be used with Unity. (I know I’ve seen some pathfinding packages mentioned here on the forums, although I can’t remember if they were navigation-mesh based.)
It might not be called that exactly… It has to do creating areas and pathfinding based on their boundaries shared boundaries. I’ll post more info later if you need. It was in a Gaming Gems book.
If you did not want to use 3d pathfinding you could do Avoidance with steering behaviors.
Just Raycast in your direction of travle and have 2 other raycast(Whiskers) off to the right/left and or top bottom of the direction your travleing and when the raycasts hit somthing in the way have it steer away from that. (OR use a collider if you dont want raycasts but its harder to get it working quickly)
Even though I have a working pathfinder/grid system I would lean more to avoidance vs 3D pathing for Air/Space units. And it also solves the air to air unit collisions.
Just for you guys, I made this. You combine things like avoidance mentioned above with this for high level pathfinding.
The premise is that when you are going from A to B, you usually make your way in high level steps. If you want to go from the living room to the bedroom, you head for the hallway entrance first, then the bedroom entrance from there. Your really only concerned with getting out of your current area into the next.
In the picture bright areas are walkable and dark areas are not. Blue represents the boundaries and the circles become the arcs in your graph(I think). Green circles are the ‘portals’. They allow you to enter the area they are connected to and most importantly, the circles in that area. This saves a ton of space over the traditional grid graph.
P.S. The book mentions making areas as square like as possible. This can help smooth out stearing and avoid the AI trying to cut corners. It also talks about attractors and repulsors but I wasn’t paying much attention to that.
@Rapzid: that’s 2D not 3D, but the principal is sound enough; that’s basically a waypoint graph. You can use that to do high-level path solving, but you’d still need something to path-find your way across the bedroom without tripping over the bed and hitting your knees on the dresser…
ackyth: simple avoidance based navigation wont get you all the way there, unless the space you’re navigating conforms to some fundamental constraints – and even then you need additional planning to avoid getting stuck in dead ends and so on…
@Jesse: I know AngryAnt’s A* framework can pathfind thorugh a 3d graph of manually placed waypoint nodes, and it supports connections between nodes with different sizes (radii?) so it can solve on the same network for different sized vehicles/agents. Not sure if Aron Greenberg’s AStar library supports that off-hand, but I think so.
@MinatureCookie: I’d suggest using manually placed waypoints plus an A* pathfinder for high-level path planning. Depending on how ‘smartly’ you want your airships to navigate, you might then want to add lower level nav meshes, avoidance and other steering behaviours, and even potential fields for other advanced refinements if needed.
Anyway, I’m pretty sure there’s no specific technique by that name (I’ve never heard the term, at least).
