...

# Pathfinding - A simple solution needed!

david56connor
05-30-2011, 02:37 AM
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.
http://i53.tinypic.com/jh817d.jpg

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)

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

Fou-Lu
05-30-2011, 04:00 AM
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