Hello and welcome to our community! Is this your first visit?
Enjoy an ad free experience by logging in. Not a member yet? Register.

# Thread: Pathfinding - A simple solution needed!

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

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