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.

What's the fastest way to highlight all possible movement tiles for a player on a square grid? Players can only move up, down, left, right. Tiles can cost more than one movement, multiple levels are available to move, and players can be larger than one tile. Think of games like Fire Emblem, Front Mission, and XCOM.

My first thought was to recursively search for connecting tiles. This quickly demonstrated many shortcomings when blockers, movement costs, and other features were added into the mix.

My second thought was to use an A* pathfinding algorithm to check all tiles presumed valid. Presumed valid tiles would come from an algorithm that generates a diamond of tiles from the player's speed (see example here http://jsfiddle.net/truefreestyle/Suww8/9/). Problem is this seems a little slow and expensive. Is there a faster way?


Edit: In Lua for Corona SDK, I integrated the following movement generation controller. I've linked to a Gist here because the solution is around 90 lines of code.

https://gist.github.com/ashblue/5546009

share|improve this question
1  
The A* pathfinding idea could be good depending on your need. Refresh the movement data when needed instead of every tick to save on performance. –  Jon Apr 29 '13 at 10:27
    
To give us some context, what engine/language are you using to implement this? A* without a doubt will be one of the easiest and accurate solutions for you to use. –  Blue Apr 29 '13 at 11:09
    
Working with Lua / Corona SDK. I have a lot of experience with other languages, so the implementation shouldn't matter too much. –  Ash Blue Apr 29 '13 at 16:14

2 Answers 2

up vote 4 down vote accepted

A* is for finding the shortest path from vert a to vert b. Its not a good fit for finding all verts x distance from vert a.

A Depth First Search (DFS) should be suitable for your problem and very cheep on both memory and clock cycles. There is another basic search algorithm called the Breadth First Search (BFS) that would run at similar speeds but uses slightly more memory because it stores all possible edges instead of immediately exploring them.

Things such as edges effecting speed can be handled by tracking distance (for example if a tile is 50% speed then its twice the length of other tiles) and only pushing new verts onto the stack if they are closer than the maximum distance. For example a bit of tinkering to the standard DFS algorithm gives you the below where all vertices labeled explored are within range of your character.

Note the below may not look it but its pseudocode. Not guaranteed to compile.

procedure Iterative_DFS(startVert) {
    startVert.distance = 0;
    var pop = true;
    HashSet discovered = new HashSet();
    Stack s = new Stack(startVert);
    s.push(startVert)
    while (!s.empty) {
          var t = s.pop();
          pop = true;
          foreach (vert v in t.adjacent) {
              if (!discovered.contains(v)) {
                  v.distance = t.distance + v.travel;
                  if (v.distance < maxDistance) {
                      discovered.add(v);
                      S.push(v);
                      pop = false;
                      break;
                  }
              }
          }
          if (pop) {
              label t as explored
              S.pop()
          }
     }
}
share|improve this answer
    
I really like this, going to test it out. –  Ash Blue Apr 29 '13 at 16:19
    
This was a good start. Modified it and slimmed down the code. See example here gist.github.com/ashblue/5546009 –  Ash Blue May 9 '13 at 7:05

You can actually do this without A*. I did this on a hex grid using recursion but the premise is the same.

You start at your characters current position with the set number of moves. then move outward in all directions reducing the number of moves by the amount of moves required to enter that square. Then repeat for each square you entered.

One thing to remember is that when moving to a square already visited, you must check the movement that the character had on that square, if it is higher than your current movement, don't enter the square.

Once you are done, you highlight any square that has 0 or more moves on it.

I did this in sort of a hacky way in that the moves were saved to each point on the map rather than an array but to me it ended up working very well. No A* required.

share|improve this answer
    
Actually this is kind of what I'm using right now. I keep running into odd edge cases when traveling up/down levels, moving around complex blockers, and complex tile movement costs. Its a great idea and super fast, but seems to have problems with extremely complex tile maps. –  Ash Blue Apr 29 '13 at 16:18
    
I had no trouble with this on a hex grid with complex tile movement costs and such. I think it really depends on your implementation. It took me several hours of tweaking the system before it began working correctly. –  UnderscoreZero Apr 29 '13 at 18:01

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.