3

For this 2d grid (black square are not penetrable, white square are):

enter image description here

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"

AntStar pernal slgorithm

You are free to fork and suggest enhancement !

  • Do you have any memory of where you've been? – Karl Bielefeldt Jul 8 '15 at 17:38
  • Yes, memory of path, memory of "i'm blocked" etc ... are authorizeds – bux Jul 8 '15 at 17:38
  • 1
    So you're essentially looking for a maze solver? – Ordous Jul 8 '15 at 17:52
  • @Ordous It look like a solution yes. I don't know all maze algo. If one or more of them can resolve it in "robot"/"ant" conditions it will be good ! – bux Jul 8 '15 at 18:03
  • How far can the ant/robot see? n distance units? Neighbouring tiles? Only the forward tile? You are looking for some algorithm that takes into account that only limited knowledge about the problem is available. It is clear that a local algorithm will not generally find the globally optimal solution, since it would likely be a “greedy” algorithm and thus be prone to “get stuck” in dead ends. This also reminds me of the “fog of war” in many computer strategy games. – amon Jul 8 '15 at 18:19
5

If you are allowed to remember past data, A* is indeed your best bet. I used it on Google's Ant AI challenge, which only has a small radius of view.

The main difference with a limited field of view is you do a lot more walking around just to explore, but that's unavoidable. A* will give you a pretty good list of where to explore, without having to visit the entire map.

For fun, I coded a solution for your example. The following is the output:

(18,18)
(17,17)
(16,16)
(15,15)
(14,14)
(13,13)
(12,12)
(11,11)
(11,10)
(10,11)
(9,12)
(8,13)
(8,14)
(8,13)
(9,12)
(10,11)
(11,10)
(12,9)
(13,9)
(13,10)
(13,11)
(14,12)
(15,11)
(15,10)
(15,9)
(15,8)
(14,7)
(13,6)
(12,5)
(11,4)
(10,3)
(9,2)
(8,1)
(7,0)
(6,1)
(5,1)
(4,1)
(3,1)
(2,1)
(1,1)

real    0m0.404s
user    0m0.727s
sys     0m0.040s

It's even more efficient than I anticipated. Only 40 moves, when the ideal with an omnipotent view of the map would be 25. You can see it follows your arrows at first, explores along the wall to the Northwest a little, then turns around and follows the wall until it escapes the indentation, after which it's almost a straight shot. It could maybe be improved even further by tweaking the weights on unseen cells to be proportional to distance from your current position.

  • Hi, thank's for your answer ! I'm working on Ant AI program ... github.com/buxx/intelligine . I will work on your solution and go back here to more information or check your answer ! – bux Jul 8 '15 at 20:37
  • What is the behavior of your algorithm in dead end ? – bux Jul 9 '15 at 13:52
  • Can you be more precise about what you mean by dead end? – Karl Bielefeldt Jul 9 '15 at 14:10
  • I would consider your original example a dead end, just a fairly wide one. As soon as you've explored enough to see all the obstacles in the dead end, the next time you run A* it will plot a course out of it and avoid reentering. – Karl Bielefeldt Jul 9 '15 at 14:17
  • If there's truly no path at all to the goal, A* will exit with an error. – Karl Bielefeldt Jul 9 '15 at 14:20
1

It looks like you are looking for an A* or Dijkstra algorithm.

Depending on the language you are working with, there is likely already libraries built that you can use for these. Here is a some Pseudocode for A* algorithm and an example for Dijkstra's algorithm

EDIT: Although Dijkstra would technically work, it wouldn't nearly as efficient as it should be.

  • Hi, according to my question we can't use an algorithm like A* or Dijkstra. we can only use information around object in movement. – bux Jul 8 '15 at 17:32
  • @bux So it can know where it's objective is (It knows direction and distance, so it can know the location). It can know what it can or can't cross over. Why can't it use one of those algorithms then? – Zachary Dow Jul 8 '15 at 17:36
  • Object can't "know what it can or can't cross over" on all positions. It can know this only for near squares. It add this precision in my question. – bux Jul 8 '15 at 17:38
  • That doesn't matter. Look at an example of Dijkstra's algorithm in action. As long as it has the ability to analyze every move it can take, it shouldn't matter. upload.wikimedia.org/wikipedia/commons/2/23/… – Zachary Dow Jul 8 '15 at 17:40
  • 1
    @bux that would make for a hilarious scene in the Termintor 25 movie, with aged characters. – null Jul 8 '15 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.