Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Sidar Apr 2 '13 at 10:53
    
Game play is real time. –  user25894 Apr 2 '13 at 10:59
    
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*. –  Sidar Apr 2 '13 at 11:52
    
But I have to choose the path that collects enough powerups to be able to defeat the monster. –  user25894 Apr 2 '13 at 12:18
1  
@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. –  DMGregory Mar 9 at 21:50

1 Answer 1

  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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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