Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 2 of 2
  1. #1
    New Coder
    Join Date
    Dec 2010
    Posts
    36
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Pathfinding - A simple solution needed!

    Hi, I am trying to create an algorithm that will help me find a path from one location to another. I have looked at other algorithms such as A* however that seems very complex for my needs!

    I constructed a small demo of what I am trying to make.


    That is a small area that I am using as a test scenario, I drew on start and finish points (start at green, finish at red)

    My theory was to have a database to store 'room' data in that would look something like this:
    Code:
    1(3)
    2(6, 3)
    3(1, 2, 4, 7)
    4(3, 8)
    5(6)
    6(5, 2, 7, 10)
    7(3, 6, 8, 11)
    8(4, 7, 9, 12)
    9(8)
    10(6, 11)
    11(7, 10, 12, 13)
    12(11, 8)
    13(11)
    Each new line being a new record. So room 1 holds all possible destination room numbers, my problem is that I can't figure out a way to solve this and would really like some help with it!
    What I had thought was to do a loop for every location of every room, so starting in room 1 and going to room 5:

    1 only leads to 3, so we must go there
    3 has 4 destinations, start with 3:2, then 3:7, 3:4, 3:1
    so now we are effectively trying 4 routes, 1-3-2, 1-3-7, 1-3-4 and 1-3-1
    then take the first route, 1-3-2, see where room 2 leads to (6 and 3)

    This may eventually find a successful route though I think that if there is a large area to cover, it will continuously go back on itself and waste a lot of time.

    Any thought on this matter would be greatly appreciated as it is by far the most complicated thing I've ever attempted with programming!

    Many thanks,
    David.

  • #2
    God Emperor Fou-Lu's Avatar
    Join Date
    Sep 2002
    Location
    Saskatoon, Saskatchewan
    Posts
    16,978
    Thanks
    4
    Thanked 2,659 Times in 2,628 Posts
    This is the job of a graph, an advanced datastructure. It stores edges to nodes, which would essentially compliment the compartment idea you have right now. Graphs can also be weighted so a shortest path can be done to determine the shortest route. From what you have, without a weight I would expect that the shortest path would be determined as 1 -> 3 -> 2 -> 6 -> 5. Unfortunately you always need to backtrack in graph traversal or at minimum store a backwards path so that if a path fails it can follow the next. Graphs are also used to both build and solve mazes.

    There are several implementations for graphs. I sacrifice datastorage for the quicker lookup of the adjacency list.
    Look into the graph datastructure on wiki for some implementation ideas: http://en.wikipedia.org/wiki/Graph_theory


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •