I've been working on a 2D game for the past couple of months--a free-roaming top-down shooter that takes place in simple mazes of corridors. (Think Gauntlet in basic navigation.) After spending hours beating my head against the wall last night trying to figure out different methods for pathfinding, I finally came to the conclusion that I need some help. The map editor I coded allows me to place AI nodes, and I can check for line of sight using a line segment/collision box test. My difficulty is that I just can't seem to think of a workable way to get the AI to move to the node closest to them that will also carry them towards the player, and then repeat the process along the path until they get into LOS with the player again. This is what I have so far for a basic "move towards the player when he's in LOS" function. This is in XNA, by the way.

   if (GetIsInLOSOfP1(enemiesActive[l].Position) && p1Destroyed != true)
   {
      Vector2 moveVel = playerOne.Position - enemiesActive[l].Position;
      moveVel.Normalize();

      if (enemiesActiveRefs[l] != 777)
      {
         EnemyList[enemiesActiveRefs[l]].Position += moveVel * (float)gameTime.ElapsedGameTime.TotalSeconds * 200;
         EnemyList[enemiesActiveRefs[l]].Rotation = (float)Math.Atan2(moveVel.X, -moveVel.Y);
      }
   }

Forgot to mention--when I say "basic", I mean that I don't particularly want to take the time and effort to learn something as complex as A*. Though if that's the only decent solution, I'll do it.

Assume for a moment that your player and npc only reside at nodes (rather than anywhere in the domain) and that when they move they may move to any adjacent node (any node directly connected to their current node).

If the source (npc) and target (player) nodes are in the same graph then the problem is solvable. Assuming that it is...

You can find a path using either a search or simply taking a guess. The latter is the easiest to code but will result in the worst performance and not very intelligent 'AI'. Most people interested in solving this problem want to find the shortest path from the source to the target. To solve this problem you will need to implement a search algorithm. A* is useful if you only care about a single source, single target search and you want to do it online. If you care to compute the results offline and store them, use Dijkstra's all-pairs algorithm.

If you need help understanding either of these algorithms there are plenty of people here (myself included) that would be happy to help. Do some reading first and then toss up your questions! 8)

Cheers,

Timkin

Thanks for the reply. I ended up looking into A* a little, as well as Dijkstra's and some others, but I wound up deciding that none of them sounded quite right for my project--they would've been too resource-intensive for what I'm doing if I wanted them to work with an adequate level of accuracy. They would have also, quite frankly, required too damn much coding.

But this isn't a plea for more help--I solved my problem my own way, actually, grabbing a couple of the ideas from the other algorithms I read about.

I ended up making my own pseudo-graph of rectangles placed only on the "walkable" parts of the level. Each rectangle intersects with up to four other adjacent ones, though more often only two (most of my game takes place in straight corridors).

My algorithm polls through all of these rectangles within a certain range of the player and tests to find out which rectangle each active enemy is in. It then finds out which 2-4 rectangles are intersecting (adjacent to) the enemy's rectangle. At that point it tests to determine which of the 2-4 adjacent rectangles is closest to the player (the center of them, actually). The enemy then moves towards the center of the adjacent rectangle nearest to the player. When the enemy makes it into the next rectangle, the process is repeated.

Upon getting within line of sight of the player, the enemy moves directly towards their position until the player leaves line of sight again.

That solution sounds less like a path finding algorithm and more like obstacle avoidance combined with a seeking behavior. If that's all you're looking for then you could try always having the enemy run toward the player, and right before the enemy would run too close to an obstacle add another movement vector that would prevent them from doing so. It would likely give you a bit smoother movement, and I would think it would be simpler and faster, but I can't say for sure since I don't know how you implemented your method. If you want more info try a search for "obstacle avoidance" and "steering behaviors".

Would such a solution really work over long distances in an environment with lots of 90 degree turns? Mine does seem to be working out properly even from across the map. Although I doubt it would work in a more complicated situation, it does seem to be a perfect fit for this type of level design.

Well, it would never go away from the player, but it should be able to zig zag through obstacles and go around a few corners as long as they were all in the direction of the player(ie (playerposition-aiposition).aimovementvector >0). I would think that is pretty similar to the capability of your method.

I'll definitely look into it, then. Thanks for the suggestion!

If you want reactive behaviors, like the obstacle avoidance idea mentioned previously, take a look at Craig Reynolds stuff here: http://www.red3d.com/cwr/steer/

The problem with using strictly reactive obstacle avoidance in your maze situation is that it has no look-ahead. This means you will be likely to get either stuck in a dead end, or oscillating between two positions as it tries to seek to the target. Purely reactive obstacle avoidance only works when all of your obstacles are convex, otherwise you risk getting stuck.

It all depends on your environment layout, as to whether reactive behaviors will work properly or not.

You mention corridors and 90 degree turns, so my guess is that no matter what you will need some kind of path-planning.

Quote: Original post by brobst
If you want reactive behaviors, like the obstacle avoidance idea mentioned previously, take a look at Craig Reynolds stuff here: http://www.red3d.com/cwr/steer/

The problem with using strictly reactive obstacle avoidance in your maze situation is that it has no look-ahead. This means you will be likely to get either stuck in a dead end, or oscillating between two positions as it tries to seek to the target. Purely reactive obstacle avoidance only works when all of your obstacles are convex, otherwise you risk getting stuck.

It all depends on your environment layout, as to whether reactive behaviors will work properly or not.

You mention corridors and 90 degree turns, so my guess is that no matter what you will need some kind of path-planning.

Thanks for the help.

I should probably at least combine some sort of obstacle avoidance with the method I'm using now. It's not exactly AI-related, but would anyone care to demonstrate a code or pseudo-code example for this function? I'm mostly confused about how the vector math would work.

http://www.red3d.com/cwr/steer/Obstacle.html

Quote: Original post by OremLK
The map editor I coded allows me to place AI nodes, and I can check for line of sight using a line segment/collision box test.

Any chance you can share, or tell me how you did your line of sight algorithm ?