XNA - Steering around walls

Question

In my little top-down, run-from-the-scary-ass-aliens game, programmed in C# XNA, I have some aliens and some walls (amongst other things). Something I'm having trouble figuring out is how I can steer the aliens round walls. At the moment they run into them like idiots, sliding along and MAYBE reaching their target if they poke out the other side.

Here's my professional illustration of the problem: problem http://imageshack.com/a/img829/6545/wsf4.jpg

So directly, my questions are:

1. How do i check if there is a wall between alien and target?
2. How do i steer them around along the shortest route?

Algorithm/explanations welcome, c# a bonus! :)

Some same assumptions to hopefully make the calculation easier: - Aliens and walls have AABB - walls are always vertical or horizontal

and i'm hapy to provide any additional information if necessary :)

Answer 1

When I did my research for the wp7/wp8 game that I developed, I solved this kind of issue with A* pathfinding. (www.policyalmanac.org/games/aStarTutorial.htm).

You can also use Dijkstra's algorithm for pathfinding. http://i.stack.imgur.com/VMkdl.gif

That was my first approach. I've since learned of a different way to also approach it. This builds upon A* pathfinding and makes use of AI Steering forces/behaviors. You may even be able to solve this problem mostly with just steering forces.

Steering forces, simply, compel an entity to move based on it's goal and environment. You stack movement (velocity) forces onto an entity and the sum of those forces moves the entity in a desired way.

So an entity might have the movement desire to move towards your monster, avoid the wall, and avoid the boundaries of the map. These velocities multiplied by % value (how much you want them to apply to the global force) all added together gives you the final force.

All of these individually have problems and restrictions. I think a combination of A* and steering forces might be best for you.

Example: http://i.stack.imgur.com/u7ECs.jpg'

EDIT: Dijkstra's is more node based if you want to manually place nodes. If placing nodes is not an option, I believe steering forces are your best bet.