2d array Brute force test

This is a discussion on 2d array Brute force test within the C++ Programming forums, part of the General Programming Boards category; Hey all, Just worken threw an assignment and i have some working code that will get me the marks i ...

  1. #1
    Registered User
    Join Date
    Aug 2007
    Posts
    22

    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.

  2. #2
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Have a look at Dijkstra's Algorithm. That's one of the standard algorithms to do this sort of thing.

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  4. #4
    Registered User
    Join Date
    Aug 2007
    Posts
    22
    cool, thnx for the help

  5. #5
    Registered User
    Join Date
    Nov 2009
    Location
    Mysore, Karnataka, India
    Posts
    12
    hey, can some one write the algorithm (in simple english)?

  6. #6
    Registered User
    Join Date
    Jun 2008
    Posts
    62
    Quote Originally Posted by vpshastry View Post
    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)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 10:54 AM
  2. two dimensional dynamic array?
    By ichijoji in forum C++ Programming
    Replies: 6
    Last Post: 04-14-2003, 05:27 PM
  3. 2D dynamic array problem
    By scsullivan in forum C Programming
    Replies: 3
    Last Post: 12-30-2002, 10:02 PM
  4. Comparing a 2d Array (newbie)
    By Cockney in forum C++ Programming
    Replies: 12
    Last Post: 12-08-2001, 12:15 PM
  5. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 10:48 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21