Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 2 of 2
05-30-2011, 01:37 AM #1
- Join Date
- Dec 2010
- 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:
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)
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!
05-30-2011, 03:00 AM #2
- Join Date
- Sep 2002
- Saskatoon, Saskatchewan
- 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