Thread: 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.

cool, thnx for the help

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

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)