Pathfinding

14b76efc949dab1a2b4fb8c055fad9a8
0
KlimBo 101 Jan 20, 2005 at 20:13

Exuse me for my bad english, please.
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

Please log in or register to post a reply.

065f0635a4c94d685583c20132a4559d
0
Ed_Mack 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)

14b76efc949dab1a2b4fb8c055fad9a8
0
KlimBo 101 Jan 21, 2005 at 13:55

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

065f0635a4c94d685583c20132a4559d
0
Ed_Mack 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.

7543b5c50738e23b200e69fe697ea85a
0
NomadRock 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.