For this 2d grid (black square are not penetrable, white square are):
I want to find path who permit to move an object to a start point (x:18, y:18) to a end point (x:1, y:1), square by square. Imagine this object is an ant or a robot, so:
It can only know the direction of its objective, distance from its objective and if around (1 square distance) square are penetrable or not. Object can keep memory of its path, if it is bypassing because previously blocked, etc ...
- At (x:18, y:18), ant know X direction is (x:-1, y:-1) vector, distance from X is 18 square, vector (x:-1, y:-1) is penetrable).
- At (x:17, y:17), ant know X direction is (x:-1, y:-1) vector, distance from X is 17 square, vector (x:-1, y:-1) is penetrable).
- At (x:11, y:11), ant know X direction is (x:-1, y:-1) vector, distance from X is 11 square, vector (x:-1, y:-1) is not penetrable).
But it can't know other things. So we can't use here an A* algorithm or Dijkstra's algorithm. Imagine object is a robot in your house. It can test every position like Dijkstra's algorithm but it will take two week to bypass a chair.
Which algorithm can be used to find path from S to X without "walking" on a black square, according to "ant"/"robot" limitations ?
I write some, but with some problems like difficulty to follow "wall" and
go round in circles ...
UPDATE: After Karl Bielefeldt response, i write alogithm available here and procuding: EDIT: I finally not use A* inspiration, but "follow wall inspiration"
You are free to fork and suggest enhancement !