# Basic pathfinding struggles

This topic is 3727 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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.

##### Share on other sites
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

##### Share on other sites
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.

##### Share on other sites
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".

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
I'll definitely look into it, then. Thanks for the suggestion!

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by brobstIf 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

##### Share on other sites
Quote:
 Original post by OremLKThe 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 ?

##### Share on other sites
Your method is very basic and will fail in any situation where the npc faces a concave obstacle between it and its target.

You can speed up your implementation by using the Distance Transform algorithm. This is basically a flood fill and gradient descent movement algorithm and should save you some clock cycles (as it sounds like you are worried about performance).

Ultimately though, as you are concerned with performance, I don't see why you wouldn't compute and offline solution to the all-pairs pathing problem and simply store this as a lookup table. This will give you the best performance online along with optimal pathing (no getting stuck in local concave regions), at the cost of some storage capacity.

Cheers,

Timkin

##### Share on other sites
Quote:
Original post by errolian
Quote:
 Original post by OremLKThe 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 ?

It's a little bit expensive, but that can be limited by only checking on units within a certain distance of the player. Essentially I just have a function that tests whether two given line segments (as two pairs of points) intersect.

It should be pretty obvious how you could then use that to test against rectangles or polygons if that's the form your collision boxes take.

If you're interested in a method for doing the line segment intersection, one can be found here:

Quote:
 Original post by TimkinYour method is very basic and will fail in any situation where the npc faces a concave obstacle between it and its target.You can speed up your implementation by using the Distance Transform algorithm. This is basically a flood fill and gradient descent movement algorithm and should save you some clock cycles (as it sounds like you are worried about performance).Ultimately though, as you are concerned with performance, I don't see why you wouldn't compute and offline solution to the all-pairs pathing problem and simply store this as a lookup table. This will give you the best performance online along with optimal pathing (no getting stuck in local concave regions), at the cost of some storage capacity.Cheers,Timkin

Well, keep in mind that I do know exactly how my levels are going to be designed--concave obstacles should rarely if ever come between an enemy and the player, and the distances traversed should be relatively short. This is, after all, a top-down shooter, not a real-time strategy game. I'll look into Distance Transform though, thanks.

[Edited by - OremLK on December 8, 2007 1:38:40 AM]