# Pathfinding

4 replies to this topic

### #1KlimBo

New Member

• Members
• 2 posts

Posted 20 January 2005 - 08:13 PM

The solution of following problem is very important for me:
I have a square map with size N x M (4<N<129, 4<M<129) and it's
divided into N X M squares. Each of this squares have value (0, 1, 2, or 3):
0 - this squares are impassable (something like wall).
1, 2, 3 - the cost of passable squares.
I also have a goal point on this map with coordinates (x,y) and I must go to it.
I don't know where I am on the map, but I can view an eight squares around me.
I'm able to move in four directions (up, down, left, right). If you can help me
with an algorithm, which finding shortest(costless) path to goal, I'll be much thankful.
I don't know my start position and it's the huge problem for me.
Thank you!
This is one examle of map with size 10 x 12:
1. Map:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 0
0 1 1 2 1 1 2 1 1 0
0 1 1 0 1 1 0 1 1 0
0 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 0
0 1 1 2 1 1 2 1 1 0
0 1 1 0 1 1 0 1 1 0
0 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0

2. Goal coordinates: x=4, y=4
3. My view (I can view an eight squares around me, i.e. I'm in the middle of this showed below):
1 1 1
1 1 1
1 2 1

### #2Ed Mack

Senior Member

• Members
• 1239 posts

Posted 21 January 2005 - 05:43 AM

http://en.wikipedia....earch_algorithm

That's one of the best search algorithms when implimented well (ie with an accurate heuristic)

### #3KlimBo

New Member

• Members
• 2 posts

Posted 21 January 2005 - 01:55 PM

I don't know where I am on the map and it's the main problem

### #4Ed Mack

Senior Member

• Members
• 1239 posts

Posted 21 January 2005 - 03:42 PM

Can you lookup anymore of the map around you? If you can, just use A* search

If you can't change the design, then run through every position on the map and see if it matches the 9 tiles you know around.

Senior Member

• Members
• 785 posts

Posted 24 January 2005 - 04:05 PM

A* will work just fine, you cannot use a good heuristic but that is ok. The A* algorithm is meant to work when you dont know where the goal is. In essence this is what you have. Consider you base all your locations as the distance from where you started, then your start is always (0,0). Now it is the end you do not know as far as the algorithm is concerned. You can still check to see if you have found the end, however, which is the important point.
Jesse Coyle

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users