1

I'm coding a simple game and currently doing the AI part. NPC gets a list of his 'interest points' which he needs to visit. Each point has a coordinate on the map. I need to find a fastest path for the character to visit all of the given points.

As far as I understand it, the task could be described as 'finding fastest traverse path in a strongly connected weighted undirected graph'.

I'd like to get either the name of some algorithm to calculate that or if there is no name - some keypoints on programming it myself.

Thanks in advance.

bezmax
  • 25,562
  • 10
  • 53
  • 84

4 Answers4

2

This is very similar to the Travelling Salesman problem, although I'm not going to try to prove equivalency offhand. The TSP is NP-complete, which means that solving the problem exactly may be impractical, depending on the number of interest points. There are approximation algorithms that you may find more useful.

David Thornley
  • 56,304
  • 9
  • 91
  • 158
  • +1. For NP complete you would want to use some kind of greedy algorithms. – Petro Semeniuk Dec 16 '10 at 22:57
  • 1
    IIRC, problems similar to the TSP are not necessarily all NP-complete; this property can be quite sensitive to the exact scope and requirements of the problem. – comingstorm Dec 17 '10 at 01:10
  • @corningstorm: You're completely correct, and I miswrote. I don't know if this problem is NP-hard or not. I suspect it is, but I'm not going to take the trouble to prove it. I've corrected my answer to what I mean. Thank you. – David Thornley Dec 17 '10 at 14:35
1

See previous post regarding tree traversals:

Tree traversal algorithm for directory structures with a lot of files

Community
  • 1
  • 1
Bnjmn
  • 1,973
  • 1
  • 20
  • 34
1

I would use algorithm like: ant algorithm.

Pietro
  • 1,815
  • 2
  • 29
  • 63
0

Not directly on point but what I did in an MMO emulator was to store waypoint indices along with the rest of the pathing data. If your requirement is to demonstrate solutions to TSP then ignore this. If not, it's worth consideration IMO.

In my case it was the best solution as otherwise the server could have potentially hundreds of mobs (re)spawning and along with all the other AI logic, would have to burn cycles computing route logic.

JasonCoder
  • 1,126
  • 2
  • 12
  • 24