🔒 Locked

Advanced Pathfinding Algorithm

Started by KlimBo_BG Jan 20, 2005 at 1:41 PM 2 replies 950+ views

Original Post

Jan 20, 2005 at 1:41 PM

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

MePHyst0

Jan 20, 2005 at 2:01 PM

so, i think the best solution is :

- before you can start the pathfind, you must find the starting square.
you have a pattern(the 8 squares around you), you query a function which will search the map for the parameter pattern (this could, in some cases, be terribly slow).

- then you could start patch findig. i advice you to use Dijkstra's pathfind

Tjoppen

Jan 20, 2005 at 2:36 PM

Why not A* instead of Dijkstra's? Surely it makes more sense to use that for the "findings" of the different cases..

markr

159

markr

Jan 20, 2005 at 5:15 PM

Because you don't know where you are, you can't tell whether you're at the goal, so you have no solution whatsoever.

If of course, you actually do know where you are, but you just don't know the topography of the map entirely, there is a method.

Because you don't know the entire topography, you won't be able to find the best route without exploring all avenues - which is bound to be more expensive than even quite a poor route.

You could draw the map in memory (what you know of it), and plot a route based on what you know, assuming that all unknown squares are passable. continue on that route until you find a square which is blocked, then recalculate the route based on what you now know.

Mark

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.