playMaker

Author Topic: Aircraft/Flight AI and pathfinding  (Read 22949 times)

Lane

  • Administrator
  • Hero Member
  • *****
  • Posts: 2488
  • Yup.
    • View Profile
    • Cleverous
Aircraft/Flight AI and pathfinding
« on: November 06, 2013, 10:33:20 AM »
I have locomotion working acceptably on an aircraft. It simply follows a target object wherever I move it. How should I approach local avoidance and/or pathfinding for a 3d space with no floor? Ideally I'm thinking I want to use the local avoidance algorithm to give the Locomotion FSM a target and move that along a path or something as the agent gets closer.

There are literally tons of pathfinding solutions but they are all for ground-based agents. Are there any 3d systems available? It may be possible to do A* on a cubical grid, but I'm worried that would get too expensive for a bunch of individual agents.

I also considered very rudimentary local avoidance, like moving the target point and using raycasts outward to detect any objects, then using the hit normal to plot away from it. This would probably give me very stupid AI, though.

Suggestions?

jeanfabre

  • Administrator
  • Hero Member
  • *****
  • Posts: 14119
  • Official Playmaker Support
    • View Profile
Re: Aircraft/Flight AI and pathfinding
« Reply #1 on: November 06, 2013, 11:59:36 PM »
Hi,

 yes, that's a problem indeed... I contacted Unity years ago on this topic and they said they would investigate upgrading their pathfinding to work in 3d, but I guess it never happened, and their last move to offer it for free is not a good sign... as it means it's not used or very controversal, as many other solutions where cheaper and work somehow better or at least not worth...

Have you searched for an existing solution? maybe some ai framework can do it, I would make a asset store shortlist and contact them authors to see what can be done on that front.

Else, the best way is to go full physics and implement raycastings. but the actual pathfinding is going to be trickay, avoidance is ok if obstacles are convex more or less.

Bye,

 Jean

Lane

  • Administrator
  • Hero Member
  • *****
  • Posts: 2488
  • Yup.
    • View Profile
    • Cleverous
Re: Aircraft/Flight AI and pathfinding
« Reply #2 on: November 07, 2013, 05:22:22 AM »
Hmm that's a bummer.

I've been looking extensively and haven't been able to find a Unity based package, UAnswers had some threads on the idea but nothing solid. I haven't looked for an external library or anything because I doubt I'd be qualified to make use of it.

Good idea contacting the authors of the existing packages, I'll give that a whirl and see what their input is on the matter.

I have been leaning toward the full physics/raycasting and gave it a try with mediocre results, it can work but I think it would might be a real challenge to make smart ai rather than ai that just avoids rocks immediately before crashing with this method which is why I'm looking for a proper package to handle it.

I'll update with findings.

Lane

  • Administrator
  • Hero Member
  • *****
  • Posts: 2488
  • Yup.
    • View Profile
    • Cleverous
Re: Aircraft/Flight AI and pathfinding
« Reply #3 on: November 07, 2013, 02:07:03 PM »
Alright from what I can tell there needs to be a different implementation to get pathfinding in 3d space that is acceptably efficient and there seem to be a lot of inherit issues with 3D pathfinding in the first place..

So far it's been recommended that I continue experimenting with what I'm currently working on: raycasting for a robust local avoidance system.

The mian problem with 3d pathfinding apparently isn't that difficult to develop but is significantly worse for performance in relation to world size which means you'll likely be using a very chunky node graph with low fidelity. The alternative is using point graphs which are custom placed nodes that the agent can path between but it only works properly in a mostly static world where objects aren't moving on top of the nodes that you've placed. If they did, the agent would try to path to them and crash into something dynamic, potentially. This is a huge problem if you're in space with orbiting mechanics or any other number of dynamics.

One trick I thought of was using a smaller 3d graph that follows the agent and updates per frame. Basically bigger, 3D local avoidance since its too expensive to scan the whole game area, or even potentially just to your target.

Another thought was using a low quality point graph over the game zone for major pathing and then again, a robust local avoidance method to handle the up close encounters.

But, either way it seems that the local avoidance is the key. It's somewhat opposite of shooter AI it seems, since plotting the path is the major load, then handling local avoidance is a smaller issue depending on how many agents are involved. If this were aircraft in the atmosphere it would be super easy, locomotion with a target and an FSM for combat behaviors. But in space there are likely many dynamics in the game space like asteroids moving, large dynamic debris, gravity agents, and any solutions have to work and be optimal for 3d use.

So it seems like the solution winds up being: A vague path plot to the target (cheap, large block graphs), a robust local avoidance system(rays, normals, delta positions), and then potentially VO/RVO considerations (velocity of dynamic agents that could hit us) depending on how expensive it is at that point.

I learned a lot today, mostly don't try to make 3d pathfinding work :P

jeanfabre

  • Administrator
  • Hero Member
  • *****
  • Posts: 14119
  • Official Playmaker Support
    • View Profile
Re: Aircraft/Flight AI and pathfinding
« Reply #4 on: November 07, 2013, 11:00:16 PM »
Hi,

 I would explore the following:

-- create a layered space, made out of flat layers, as you go up and up you have more layers,

-- use offmesh links to move from one layer to the other. OffMesh links are used for ladders and jumps to move from one navmesh spot to another without continuity.

 then, you will get a sense of 3d navmesh space, because offmesh links will be understodd during pathfinding algorythm, and to if you are at the highest level and want to go to he ground level, it will find the closest offmesh link to move down in layers.

 Does that make sense?

It may be impractical if you expect a total freedom of movement, but I think you can get pretty near a good result if you place enough off meshlinks.

bye,

 Jean

Flying Robot

  • Sr. Member
  • ****
  • Posts: 293
  • Od ton yebo redro
    • View Profile
    • Flying Robot Studios
Re: Aircraft/Flight AI and pathfinding
« Reply #5 on: November 08, 2013, 06:36:33 AM »
@Lane. Wow. Thats a huge amount of research. This never occurred, but 3D pathfinding should really be an interesting challenge.

Quote
The alternative is using point graphs which are custom placed nodes that the agent can path between but it only works properly in a mostly static world where objects aren't moving on top of the nodes that you've placed. If they did, the agent would try to path to them and crash into something dynamic, potentially. This is a huge problem if you're in space with orbiting mechanics or any other number of dynamics.

I think this may be worth exploring.

May be you'd need to add something like adding triggers to the path nodes and disabling them (exclude them from the search list) when they are triggered by asteroids (colliding objects). So, when an agent would try to pathfind he would find a path around it.

Sounds like a solution?

Lane

  • Administrator
  • Hero Member
  • *****
  • Posts: 2488
  • Yup.
    • View Profile
    • Cleverous
Re: Aircraft/Flight AI and pathfinding
« Reply #6 on: November 08, 2013, 08:00:41 AM »
@Jean
I didn't know about Off Mesh Links but it sounds like it could be promising.
http://docs.unity3d.com/Documentation/Components/class-OffMeshLink.html

I wonder what the practical differences are in using off mesh links instead of just generating a low quality 3d point graph on the whole game area, though. The built in Nav features would probably be convenient to use, but I'm not convinced that would be better than using a solution with points.

@Flying Robot (the guy with the ironic name for this thread) :P
Yeah I thought about that, it probably wouldn't be too much more complicated to add in, I think its kind of required if most of the space is dynamic. If the Agent tries to path to the other side of the station and the station is floating around then it would fly up to it and rely on LA to path around it unless the obstructed nodes were disabled for pathing. It's probably something that would need to be added if point graphs were used.

I thought a little more about using raycasts for the long destinations. Worst case scenario in open space is navigating around a huge space station, everything else is either fairly small or an agent for combat targeting. So I thought it might work if the destination was set on the other side of a station, then a ray cast straight to it, and if it hits something then it rotates in a circular motion until it finds some clear area and then paths to a spot near there (basically kind of looking for a tangent point). The circular expansion of the ray would keep it working in 3d space and it would at least get to the edge of the problem object and eventually around it.

Flying Robot

  • Sr. Member
  • ****
  • Posts: 293
  • Od ton yebo redro
    • View Profile
    • Flying Robot Studios
Re: Aircraft/Flight AI and pathfinding
« Reply #7 on: November 08, 2013, 08:52:05 AM »
Now, this is becoming something personal :D

Your pathfinding trick sounds ingenius. I guess it can be a practical solution in open space. If the agent and the destination is rotating around a common center. But it may not provide solution to more general cases, particularly in cases when a vehicle has to navigate through an asteroid field or something.

Lane

  • Administrator
  • Hero Member
  • *****
  • Posts: 2488
  • Yup.
    • View Profile
    • Cleverous
Re: Aircraft/Flight AI and pathfinding
« Reply #8 on: November 08, 2013, 09:14:07 AM »
Hah! ;)

I figured if the agent had got into a really congested area then I would need some way to weight its direction choices toward the "far" destination to prevent him from repeatedly avoiding locally in the wrong direction. It needs a feedback loop. Kinda stuck on that one for the moment... there is definitely some low level stuff in there to figure out, but I think I could make the ray idea work at least for open space. If there were to be an interior area I would definitely want to go with more traditional methods.

Flying Robot

  • Sr. Member
  • ****
  • Posts: 293
  • Od ton yebo redro
    • View Profile
    • Flying Robot Studios
Re: Aircraft/Flight AI and pathfinding
« Reply #9 on: November 08, 2013, 09:27:15 AM »
You really need to see this
http://en.wikipedia.org/wiki/Dijkstra's_algorithm

if you haven't already.

As it's not dimension based. I think it can work equally in 3d space.

jeanfabre

  • Administrator
  • Hero Member
  • *****
  • Posts: 14119
  • Official Playmaker Support
    • View Profile
Re: Aircraft/Flight AI and pathfinding
« Reply #10 on: November 08, 2013, 10:05:36 AM »
Hi,

 Uhm... indeed, if you would set your "free space" with evenly spaced nodes ( like the light probes unity uses for lighting) then it could work.

Bye,

Jean


Lane

  • Administrator
  • Hero Member
  • *****
  • Posts: 2488
  • Yup.
    • View Profile
    • Cleverous
Re: Aircraft/Flight AI and pathfinding
« Reply #11 on: November 13, 2013, 03:10:45 PM »
Okay, some basic raycasting with local avoidance is working like... like a rock falling down a cliff.

FSMs consist of Brain, Aim and Move.
  • FSM Move just pushes the ship with force, later the speed var will be manipulated remotely by the brain.
  • FSM Aim turns the ship with a torque-based action toward a target point, that target is constantly moved by the Brain FSM
  • FSM Brain constantly raycasts and looks for obstacles, when it finds one it looks for clear space which is done by using the raycasts didHit bool, it animates in a direction until the bool is 0 which sends and event to move the target point by bouncing off of the last hitPoint by a specified gap float, which turns the ship away from the object..... Sort of.

Thats basically all it does for the moment. It is very difficult to control but the agent will avoid colliders decently while sometimes going postal and getting confused. The logic for moving the target is not good yet and doesn't consider any kind of physical area context that needs to be considered if we want a smart placement of the targetPoint.

In addition to the (local) Target Point for the agent there is an Anchor Point which if it gets too far away from it will turn around and try to go back. There isn't any weighting to deciding the raycast direction for pathing around objects so once he turns around he'll just start avoiding however he can and eventually fly into oblivion and trigger the Anchor distance U-turn.

Let me know what you guys think.

http://dl.dropboxusercontent.com/u/38606641/AI/AITest-r1.unitypackage
« Last Edit: November 13, 2013, 03:13:44 PM by Lane »

Lane

  • Administrator
  • Hero Member
  • *****
  • Posts: 2488
  • Yup.
    • View Profile
    • Cleverous
Re: Aircraft/Flight AI and pathfinding
« Reply #12 on: November 14, 2013, 02:47:56 PM »
WebPlayer Demo (Camera Following AI Agent with a few other Agents flying around)
http://dl.dropboxusercontent.com/u/38606641/AI/AI-test/AI-test.html

It's slightly boring to watch, but the Agent does avoid the asteroids consistently now. With some more work I can sort out directional weighting and acquiring targets for combat. For now, this local avoidance method needs a little more work with the local rays. It seems when they get very close to an obstacle they tend to not be able to see it clearly because of the raycast spread being too narrow at the nose of the craft.

[edit]

it also flies around in circles if it has enough space, this is because of how I'm projecting its path to wander, and needs to be randomized with some variety.
« Last Edit: November 14, 2013, 03:04:15 PM by Lane »

Lane

  • Administrator
  • Hero Member
  • *****
  • Posts: 2488
  • Yup.
    • View Profile
    • Cleverous
Re: Aircraft/Flight AI and pathfinding
« Reply #13 on: December 19, 2013, 07:56:28 AM »
Ok so he's still got problems, but I think it's going in the right direction (no pun intended :P )...

http://dl.dropboxusercontent.com/u/38606641/AI/AI-test/AI-test2.html

He bumps into a lot with this method but it seems to perform more consistently than the first method.

I'm thinking the next move is going to be getting the agent to interpret when it should be looking for a new position, because currently it's storing and using every single new position the math computes and its a little bit unnecessary and makes his movement appear jerky/frantic. Plus he fails to avoid properly if the position isn't to the side of him since I'm using Normals from this ray

Some good news is that with this update I can't seem to completely trap him.

Got some ideas to improve this one...
« Last Edit: December 19, 2013, 08:11:16 AM by Lane »

shyfox

  • Playmaker Newbie
  • *
  • Posts: 7
    • View Profile
Re: Aircraft/Flight AI and pathfinding
« Reply #14 on: December 22, 2013, 07:04:21 AM »
Very nice. I saw your work and I like it. Also may you post your last post AI test package? I´m also looking to develop an object evade solution in an open space.