2 replies to this topic

[ken_brigid]

Hi!

I'm new here. I'm doing an advanced programming course at the University and I've been given my first project. I think I've to solve it with the A* algorithm, but it's giving me some troubles.

Let's say "0" is equal to a wall, "1" is equal to a moving cost of one and "2" is equal to a moving cost of two. S means the start and E the end.

The input will be something like this:

1 1 1 1 1 1 2 2
0 0 S 1 1 0 2 2
0 0 2 1 0 0 0 E
2 1 2 0 2 2 2 1

The idea is to find the cheapest path from S to E and the code must be efficient. The input matrix will be of 600*600 and the answer must be given in less than a minute.

We were told while we were having classes that the best way to solve it was using an algorithm discovered in the sixties. So my friends and I think it's using the A* algorithm (we found it on the internet). The problem is that we have two different moving costs so we don't know how to implement it.

So, is it right A* algorithm is the best option in this case? If that's right, could somebody put me a link to a webpage were is described how to use the algorithm or explain it to me here?

Sorry if it's not written in correct English but I try doing my best.

Greetings!

[zoranh]

Learning is better than guessing - it takes you to correct answer more often.

I would suggest you to use Dijkstra's algorithm (which is not from sixties).

[gaylo565]

The A star algorithm is the one your professor wants you to use. You need to choose an appropriate heuristic that never overestimates the actual paths moving cost. This can be done using a simple distance to your finishing point since there is always a moving cost of at least one (or you can get more complicated if your processing times aren't fast enough but that bumps up the difficulty a bit.) Other than that yours is pretty much an example case of when to use this algorithm.

The link below is a pretty good explanation of the algorithm, although you probably already looked at it, as it is the first one that came up for my google search. Unfortunatly his source code is in c++.
A* Pathfinding for Beginners

Here is a solid c# example:
Path finding in C# - CodeProject
This is the best example I found that explains the coding side of your project. There is one on MSDN and several other solid coding examples out there as well, but I like this one (seemed the easiest example but its worth looking around for one you like.)

I remember having to do this in shcool and it took me a good chunk of time to adapt the algorithm to fit my exact needs, otherwise I would attempt to do it for u. I looked throuhg my old source code files and don't have that project anymore or I would post it for you (wasn't exactly the same anyway, probably no closer than the C# example above).

Edited by gaylo565, 13 August 2010 - 11:44 AM.