So I have the following problem : a X by Y grid. On the grid there is a character and a monster and some items that give bonus points to the character's damage if picked and holes that must be avoided. The goal is to collect enough items to be able to defeat the monster, then navigate to the monster and fight it.

What kind of algorithm can be used to solve this problem?

  • \$\begingroup\$ Are you talking about turn based or real time gameplay? Have you considered looking at A*? The implementation looks difficult but is actually pretty simple. \$\endgroup\$ – Sidar Apr 2 '13 at 10:53
  • \$\begingroup\$ Game play is real time. \$\endgroup\$ – user25894 Apr 2 '13 at 10:59
  • \$\begingroup\$ Ok, you could leave some info out of your question btw. The focus here is to achieve pathfinding. Right? I'd say look at A*. \$\endgroup\$ – Sidar Apr 2 '13 at 11:52
  • \$\begingroup\$ But I have to choose the path that collects enough powerups to be able to defeat the monster. \$\endgroup\$ – user25894 Apr 2 '13 at 12:18
  • 1
    \$\begingroup\$ @Trevor: close. If the asker needs the shortest such path, it's a collection of Hamiltonian path problems. If there are n items and k are needed, then there are (n Choose k) subsets to find a Hamiltonian path through, plus the start and end legs to connect to the player and monster positions. TLDR: approximate, maybe greedily. The optimum's probably too much work. \$\endgroup\$ – DMGregory Mar 9 '14 at 21:50
  1. Do I have enough damage to defeat the monster? If yes, go to 4.
  2. Pathfind to every item, and travel to & pick up the one with the shortest path.
  3. Go to 1.
  4. Pathfind to the monster and defeat it.
  5. End.

As others have said in the comments, A* is the obvious approach for performing the pathfinding itself.


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.