0
101 Jan 20, 2005 at 20:13

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

1. Goal coordinates: x=4, y=4
2. 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

4 Replies

0
101 Jan 21, 2005 at 05:43

http://en.wikipedia.org/wiki/A-star_search_algorithm

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

0
101 Jan 21, 2005 at 13:55

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

0
101 Jan 21, 2005 at 15:42

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.

0
101 Jan 24, 2005 at 16:05

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.