2d array Brute force test

Hey all,

Just worken threw an assignment and i have some working code that will get me the marks i need but just out of curiousity i would like to see if anyone here can think of an algorith for my problem.

Problem:
I created a program called map creator. It asks user for dimentions of the array [rows][cols]. Then it goes threw and makes sure the user has filled it all up with one of the terrain types from a key posted in the menu.
When the user is selecting the terrain type, they will also assign a cost to the area of terrain they just created.
Once filled the user saves it into a text document.

Now ive created a program called Pathfinder. Pathfinders purpose is to start at a point entered by the user and end at another given by the user. All it has to do is to find the least costly path(that is ignoring the terrain type and simply adding the cost assossiated with the x, y cords). It has to be able to bactrack (that is go backwards and forwards in the array position) and ensure while checking you doent go over teh same position twice in the same loop.

So far ive got some good code that will find a very cheap path, but not nessisarily the cheapest.I think the only way is to test every possibility (brute force) but i just cant seem to write any code that does that.

Any info or links you have will help, thanks.

Have a look at Dijkstra's Algorithm. That's one of the standard algorithms to do this sort of thing.

QuantumPete

Sounds like a straight-forward shortest path problem in a directed graph of weighted edges.

You can translate your terrain map to a graph like this:
1) Every grid element is a node.
2) Every node has a directed edge to the four nodes that correspond to the neighboring elements.
3) Every edge's weight is that of the terrain of its target element.

Now you can apply any graph algorithm you want to it, like Dijkstra's Shortest Path.

Alternatively, you can use the A* algorithm, which is frequently used in game path finding.

If you know enough about generic programming, you can even write adapters so that these algorithms run directly on the grid. Shouldn't be too hard.

cool, thnx for the help

hey, can some one write the algorithm (in simple english)?

Quote:

---

Originally Posted by vpshastry

hey, can some one write the algorithm (in simple english)?

---

For this problem, (as I don't think you want all paths, which dijkstra's Algo solves), A* would be the best solution. Check out Cornered Bee's link and the external links on it for some pretty good resources on the A* algorithm and how it works. (it even includes a java example)