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 making my 1st game. I'm using javascript as I currently want to learn to make games without needing to learn another language but this is more of a general game dev question.

It's a 2d turn-based tile/grid game. You can check it here http://www.patinterotest.tk/ it creates a movable area when you hover a player and it implements the A* algorithm for moving the player.

The Problem: I want to make the 'dynamic movable area creation' already implement a limited number of steps for a player.

The Questions:

  • What is a good way to do this?

  • Is there another algorithm to use for this?

  • The A* algorithm needs a start and destination, with what I want to do I don't have a destination

  • Or should I just limit the iteration of the A* algorithm to the steps variable?
share|improve this question
add comment

3 Answers

up vote 0 down vote accepted

Since your game is a 2D tile-based game, I assume you're modelling each tile as a node, and the map is essentially a grid of nodes.

In this case, there is no weight on any edge of the graph, so I don't see why you're using A* which was designed for finding minimum distances on weighted graphs. You should be using plain breadth first search

  • The number of iterations you do with BFS is the max number of steps your character can take
  • The path to any node can be extracted by keeping a predecessor list. Any path extracted this way is the shortest path because the graph is unweighted.
  • The set of reachable nodes is basically any node BFS traverses; which you can use to generate your "dynamic movable area".

It will run the fastest because you don't need to do any distance considerations or heuristic calculations in the case of A* or Dijkstra (which is basically A* without using heuristics or H(x) = 0).

A*/Dijkstra is overkill unless you got a weighted graph.

share|improve this answer
    
"In this case, there is no weight on any edge of the graph" Well I'm not sure what you are meaning because for me the weight exists and equals, say 1.0. "The number of iterations you do with BFS is the max number of steps your character can take" <- This is not really true as you need to calculate the 'predecessor list' and That costs O(n²) (square of the distance) and you must calculate that if the world changes (and precalculate a big world might be memory costly). –  Valmond Mar 21 '12 at 10:08
    
Sorry for the misleading phrase, I was referring to actual loop you would have in code. The complexity of BFS is O(V+E) nonetheless. Also, If every edge of a graph has equal weight, then it's considered unweighted graph. If an edge has 0 weight, then the 2 nodes it connects can be modeled as a single node. Finally, the predecessor list can be implemented within the BFS loop and will requires same # of operations as BFS, complexity-wise still O(V+E); look at link to back to Dijkstra algo on that page. –  XiaoChuan Yu Mar 21 '12 at 17:51
    
The set of reachable nodes is basically any node BFS traverses; which you can use to generate your "dynamic movable area". <-- this line made me understand why plain bfs would be enough, thank you –  bigbadbabybear Mar 21 '12 at 21:43
add comment

Sounds more like a you'd want a breadth first search, instead of a depth first like A*, a common one is Dijkstra's algorithm. It is typically used for path finding, but you don't need to have a goal in mind. You can almost use it as is, except you want to limit the depth to the number of moves the player has.

A gif from the wikipedia page shows how this fits your situation:

enter image description here

share|improve this answer
    
The 'movement cost' of the current terrain tile would have to be subtracted from the depth for the next iteration, too. –  sarahm Mar 21 '12 at 0:31
    
+1 for Dijkstra, a too often forgotten algorithm. –  Valmond Mar 21 '12 at 10:01
add comment

Just execute A* each and every step.

If this is too slow, think about optimising it. Then there are several approaches, for example jump-point-search makes the A* itself faster. You can also try and work out the circumstances when you need to recompute the path, and only doing so then.

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.