Using A star algorithm for a thief

E5b1a5dcd0249230412e39d3d1b42079
0
burakkilic 101 Nov 15, 2006 at 17:36

Hi… I have a maze project. In this project, there are one thief and one police. When you start the program, police tries to catch the thief. In my code, I did it for the police with the A star algorithm. I found the shortest path,then i return the first step of this path to catch the thief. And now I come to my question: Can I do the same for the thief’s code, but finding the longest path and run away from police? For example, police will be my target, but i will find the longest path,and return its first step to run away. Can anybody help me with this?

4 Replies

Please log in or register to post a reply.

6f0a333c785da81d479a0f58c2ccb203
0
monjardin 102 Nov 15, 2006 at 21:07

When the police officer is in a dead end the longest path will be the same as the shortest path. If you’ve already calculated the shortest path then go the other way. Of course, you would want a way for the thief stay out of dead ends…

E5b1a5dcd0249230412e39d3d1b42079
0
burakkilic 101 Nov 16, 2006 at 13:33

@monjardin

When the police officer is in a dead end the longest path will be the same as the shortest path. If you’ve already calculated the shortest path then go the other way. Of course, you would want a way for the thief stay out of dead ends…

you mean that find the shortest path but go to the other way? And do you have an opinion to recognize the dead ends?

D619d95cddb1edb227f51ef539d15cdc
0
Nautilus 103 Nov 16, 2006 at 14:30

The cheapest solution would be for you to manually mark these dead-ends, so that the algo will recognize and deal with them.

With a bit of preprocessing you can do so even if the maze is autogenerated at runtime.

Ciao ciao : )

6b7e1a4b42e4b47d92fdef8bf2bd8e2c
0
Jare 101 Nov 19, 2006 at 11:01

The problem with finding the longest path is that you have to explore the entire set of possible paths. A* works by finding an optimal list of steps that reach a known goal, and “get as far away as possible from policemen” isn’t properly known in advance.

You could set a “comfortable” range where you consider yourself “safe” from policemen. If your policemen’s A* heuristic function is “Distance to target” (where target is the thief), then your thief’s heuristic would be “SafeRange - Distance to target” (where target is the policeman).

Now, since you have several policemen, you’d have to get distances to all of them, and possibly use the closest (most dangerous) one in the heuristic, or maybe add all of them together, or some smarter combination.

These are all ideas you can give a thought or try out. The best solution really depends on the way the maze is designed, and what other goals the thief has.