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?
1
Using A star algorithm for a thief
Started by burakkilic, Nov 15 2006 05:36 PM
4 replies to this topic
#2
-
- Members
-
- 1033 posts
Senior Member
Posted 15 November 2006 - 09:07 PM
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...
#3
-
- Members
-
- 2 posts
New Member
Posted 16 November 2006 - 01:33 PM
monjardin said:
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?
#4
-
- Members
-
- 351 posts
Senior Member
Posted 16 November 2006 - 02:30 PM
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 : )
With a bit of preprocessing you can do so even if the maze is autogenerated at runtime.
Ciao ciao : )
-Nautilus
(readin' this? you ought to get out more)
#5
-
- Members
-
- 247 posts
Valued Member
Posted 19 November 2006 - 11:01 AM
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.
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.
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users
