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.

I'm a little stuck on the logic to how i use my path finder efficiently in my game.

This is basically how the game works:

Building generates goods "Factory" > AI transports goods to "Warehouse" on path tiles >     
  Warehouse receives goods > AI goes back to Factory.

Now im wondering how I use my path finder efficiently so its checking the "Factory" is connected to a warehouse by path.

So heres my logic im wondering if it can be improved:

User places factory down > game checks path.

Result 1: No path found> Keep checking every frame..

Result 2: Path found > Store path stop rechecking every frame.

The two problems i have is: Well checking every frame is going to hurt the game's performance, secondly if I stop rechecking - it won't know when a faster route may become available or unavailable =/

Is my logic correct or is there a better method?

share|improve this question
add comment

3 Answers 3

up vote 3 down vote accepted

If you want to avoid checking every frame, instead check every time something changes (e.g. whenever a new factory/warehouse/path tile/etc is placed). These times are the only times that the paths might need to be updated anyway, since these are the only times that a different route may become available or an old one be closed.

EDIT

If you find re-calculating all paths each time a change is made is too slow, then there are ways of speeding that up too. For example, if you add a new factory you'll at a minimum need to calculate the paths starting from that point to your warehouses. If you find that these paths cross any existing paths, that's a clue that those paths might need updating too. I'm not sure on specifics, that probably depends a little on your particular game.

However, it seems to me that you are probably undertaking a bit of premature optimisation. It's usually best to just do things the easy way first, and only worry about these kind of optimisations when they are actually needed. Otherwise, you can waste a lot of effort producing code that is way more "clever" than it needs to be, and which is often much harder to understand (and hence maintain) than the simple approach.

share|improve this answer
    
But i would still have to check every building again wouldn't i ? –  Dave May 3 '12 at 2:30
    
@Dave: see my edit. –  Mac May 3 '12 at 2:52
add comment

Well, you always can reduce checking frequency by some amount. If immediate path detection isn't requred, you can perform checking say once in a second, thus reducing load by your default fps.

share|improve this answer
add comment

Here's a great introduction to A* pathfinding. http://theory.stanford.edu/~amitp/GameProgramming/

Ideas:

  • Delaying to check on events, ie: road tile destruction, or road creation.
  • Path on intervals. Once a second may even be more than needed.
  • test it : you may find it runs fast enough, even non-optimized.
  • Partial steps: You can break the search into steps. Find 1/2 the distance. move there. pathfind the rest, once he is at that location.
share|improve this answer
add comment

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.