Good ai with no need for path finding

[omaremad]

im trying to make some wall avoidance code for ai without the need for navigation nodes

its basiclly wall avoidance i can get the normal of the obstacle trinagle and the distance to it

please help

[elander]

This method will work more easly if you separate collision geometry from presentation geometry. Collision geometry would have to be as simple as possible.

[Guest]

good idea but my levels are simple any way
does any 1 have a formula to work out this stuff in 3d space

[Electron]

i think there's a raycast function to retrieve the triangle a ray collided with. Terribly slow to do every fram of course. Plus only gives triangle with 3 points, no normal. easy to create normal (crossprod of two vectors formed from points) as long as ur not worried about front-facing vs back-facing triangles.

[bitplane]

good idea, but if your target is behind a wall you'll always end up stood on the triangle's normal.
i think you should do it in steps, you start by taking a number of steps towards the target. if something is in the way, you remember the angle would like to go to and push it on a stack.
if you can't go in that direction, you take the direction from the collision's triangle and head that way, and push the last direction on to the stack.
If you can go in the last direction, then you change to that direction and pop it off the stack. it wouldnt stop you getting stuck and going round and round in circles though, but it would navigate round most things and usually find a way to a moving target
another way would be to pick a direction and follow the wall circling the current object until the line to the destination collides with a different object. thats not without its problems either though, pathfinding is the best way

[omaremad]

thanks
i will look in to the the open steer sorce since it an do obstacle avoidance without paths nodes

[omaremad]

hi
found some code here on the forum
the theory is nearly the same as mine but the final destination is the normal not parrall to the triangle

Code: Select all

 //**********  Enemy Collision Avoidance  *********** 
      core::vector3df calc2Vector; 
      calc2Vector.X = speed.X /(GameSpeed*0.02001f); 
      calc2Vector.Y = speed.Z /(GameSpeed*0.02001f); 
      calc2Vector.Z = speed.Y /(GameSpeed*0.02001f); 

      //Enemy collision check ground 
      core::vector3df start = pos;     //Enemy position 
      core::vector3df end = start + calc2Vector*80.1f; //Enemy1 vector 
      core::triangle3df triangle;         //holds information about the triangle hit 
      core::line3d<f32> line(start, end); //line to test for collision 


      // check for collision with terrain 
      if (smgr->getSceneCollisionManager()->getCollisionPoint( 
      line, selector, end, triangle)) 
      { 
         collision = true; 

         // angle of impact 
         core::vector3df out = triangle.getNormal(); 
         out.setLength(1.0f); 

         //rotate enemy ship to face away from impact 
         calcVector.Y = atan2 (out.X, out.Z); 
         calcVector.Y *= RadToDeg; 
         calc = sqrt(pow(out.X,2)+pow(out.Z,2)); 
         calcVector.X = atan2 (calc, out.Y); 
         calcVector.X = calcVector.X * RadToDeg - 90; 
      } 
      //**********  End Enemy Collision Avoidance  ********** 
       
      //rotate model smoothly based on game speed 
      dir = int(calcVector.X-Drot.X)%360; 
      if(dir<0){dir+=360;} 
      if(dir>180) 
         Drot.X = Drot.X - 25.0f/GameSpeed; 
      else 
         Drot.X = Drot.X + 25.0f/GameSpeed; 

      dir = int(calcVector.Y-Drot.Y)%360; 
      if(dir<0){dir+=360;} 
      if(dir>180) 
         Drot.Y = Drot.Y - 25.0f/GameSpeed; 
      else 
         Drot.Y = Drot.Y + 25.0f/GameSpeed; 

      rot = (rot*smoothing+Drot)/(smoothing+1.0f); //Rotate the ship 

it solves the problem that bit plane said about forever bouncing on the normal by turning the thing gradually

however i dont understand the variable "gamespeed"
is just any number
or is it the timer

[delscorcho]

Just FYI, if your levels are simple, pathfinding is also simple. If you represent your world with tiles (i.e. a grid), you can apply A* or any search alg to easily generate paths. Pathfinding is really quite easy!

[Electron]

A* does not need a grid or any such regular structure. Of course, a grid is useful to generate the A* nodes.

[omaremad]

a major problem with a* is that how would ir know if that square is part of the bsp or not

unless there are predefined nodes

[delscorcho]

A* can path anything... but he mentioned that he had a simple map, but didn't want to use pathfinding. If your map is simple, you can break it up into a simple grid and easily use A*, and it's not hard to implement.

a major problem with a* is that how would ir know if that square is part of the bsp or not

unless there are predefined nodes

Not sure I understand what you mean. From your original post, it seemed like you were in need of a good way to avoid walls. If you flag grid positions as being "too close to a wall" your heuristic could just reject those nodes/grid squares and your AIs would avoid the walls.

[bitplane]

i think thats what omaremad is getting at is the need to draw your a* map as another part of your workflow. That's the main advantage of not using real pathfinding imho.
I think what we need is an automatic a* node generator that you call on a mesh, something like smgr->createPathFindingNodes(mesh, startvector, downvector), and it uses collision detection to decide which parts can be reached from neighbouring nodes, if hills are too steep, etc,

[delscorcho]

Yeah, I'm trying to imply that there is no explcit 'drawing' of your navigation grid. If your map is simple, just generate the grid. You DON'T have to use something sophisticated like a nav mesh.

[Electron]

I generate my A* nodes on a pseudo grid (modifying height where necessary), then the user can move nodes around as desired, if the grid does not quite fit. It definitely beats having to draw the map of nodes out by hand.
With regards to the original topic, avoiding walls, AI Game Programming Wisdom 2 has a very good article about dynamic obstacle avoidance. Essentially, get the distance to nearby obstacles, generate a repulsion vector for each, calculate the total repulsion vector, and create a movement vector by combining the repulsion vector with the desired direction. I have yet to implement such a system myself because I am waiting for the closest distance function in Newton 1.35. Using irrlicht raycasting for the closest distance would be terribly slow, so I think a physics engine would be better suited here. Even without a closest distance function, it could be done with the raycast capabilities of the physics engine.