Alex Rivera | Logout

AI navigation around a 2d map - avoiding obstacles

Asked 2010-05-01T23:21:31.723
9

I know my question seems pretty vague, but I can't think of a better way to put it, so I'll start off by explaining what I'm trying to do.

I'm currently working on a project whereby I've been given a map and I'm coding a 'Critter' that should be able to navigate its way around the map; the critter has various other functions, but those are not relevant to the current question. The whole program and solution is being written in C#.

I can control the speed of the critter, and retrieve its current location on the map by returning its current X and Y position, I can also set its direction when it collides with the terrain that blocks it.

The only problem I have is that I can't think of a way to intelligently navigate my way around the map; so far I've been basing it on what direction the critter is facing when it collides with the terrain, and this is in no way a good way of moving around the map!

I'm not a games programmer, and this is for a software assignment, so I have no clue on AI techniques.

Here's a link to an image of what the maps and critters look like:

Map and Critter image

I'm in no way looking for anyone to give me a full solution, just a push in the general direction on map navigation.

c# algorithm artificial-intelligence path-finding
Edit
Report

1 Answer

3

A* Search

Take a look at the A* pathfinding algorithm. It's essentially the standard approach for stuff like this.

Amit Patel's write up on pathfinding for games has a pretty good introduction to A* as well as popular variants of the algorithm.

You'll find a C# implementation here, and here

Dynamic A*

Let's say the terrain you'll be searching is not known ahead of time, but rather is discovered as the agent explores its environment. If your agent comes across a previously unknown obstacle, you could just update the agent's map of the terrain and then re-run A* to find a new path to the goal that routes around the obstruction.

While a workable solution, rerunning the planning algorithm from scratch every time you find a new obstacle results in a sizable amount of redundant computation. For example, once you're around the obstacle, it might be that the most efficient route to the goal follows the one you were planning on taking before you discovered the obstacle. By just rerunning A*, you'll need to recompute this section of the previous path.

You can avoid this by using Dynamic A* (D*). Since it keeps track of previously computed paths, when the agent finds a new obstacle, the system only needs to compute new routes in the area around the obstacle. After that, it can just reuse existing paths.

answered 2010-05-01T23:33:00.767

Your Answer