Showing range on hexagonal grid

Here is the situation.

I have hexagonal board,and a unit on it,with speed or move value 4.Diffrent terrain has a diffrent cost.When i click on the unit,game should show me a move range.

My solution was to check each hex in range of 4,with A* pathfinding,and if path cost was less than 4 then this hex was in range.Finally game nicely show me range of that unit.

My question is: Is there other solution to search for range on hex grids or square grid,because even if i am really proud of what i did in my solution,i think,it is a little to exaggerated?:))

What make me ask this question?I noticed that when unit speed is 4 or 6 or even 8,time to computing range for my computer was really good,but when speed was 10 and more i noticed that i needed to wait few second to compute.Well in real games i rather dont see something like this and my A* pathfinding is rather well optimized,so im thinking that my solution is wrong.

Thanks for any replies.

• I agree with Byte56 that a breadth first search algorithm is a good solution. This is not to say that you shouldn't try to be creative, but as far as well-known algorithms go it's a good one that applies well. – theJollySin Dec 6 '12 at 19:39

You're right that A* is a little overkill, but not by much. You shouldn't be seeing delays like you are. A* is really just a modified Dijikstra's algorithm. Since you're not using an end position (as your end position is just "as far as you can go"), using A* with it's added heuristic isn't necessary. Simply using Dijikstra or a simple breadth first search will be sufficient.

For example, Dikikstra will spread out evenly in all directions: (A simple breadth first search will look similar to this)

Keep track of the cost to travel to each node. Once a node is at the maximum travel cost, don't process its connected nodes any further. (Similar to where the nodes run into the wall below).

If you're running into performance issues at only 10 nodes out, you'll want to look at how you're accessing the nodes. A breadth first search should be able to navigate hundreds of nodes without a noticeable delay (certainly not a few seconds). Consider storing a simple version of your world in a graph format, for quick traversal.

• can you find the distance between a two nodes using BFS and taking in account obstacles/different weights? – Luke B. Dec 6 '12 at 20:31
• The cost of moving between nodes should be pre-computed for the most part. The cost is not calculated using BFS, BFS is an algorithm for traversing the nodes. How you determine the cost for traveling from one node to another is independent of how you traverse the nodes. – MichaelHouse Dec 6 '12 at 21:42
• Thanks,now i see why my thinking was wrong,the key for that was this statement "Since you're not using an end position (as your end position is just "as far as you can go")".In my solution i had an ending position,it was the unit.I just solved the problem from wrong direction.First i determined the border,and then from there i went back to my unit,in that way i probably went many times through the same nodes.So when my speed increase,the number of computation increase also alot.The way you show me,i will always visit node once.I just had wrong point of view,really thanks,this simplify alot. – user23673 Dec 7 '12 at 9:56

Amit Patel has provided an excellent resource for getting ranges on his site. In the article, he uses the following algorithm for collecting hex tiles within a range:

for each -N ≤ Δx ≤ N:
for each max(-N, -Δx-N) ≤ Δy ≤ min(N, -Δx+N):
Δz = -Δx-Δy

This creates bounds aligned with the hex grid: This will find all the hexes within a certain distance of the center hex, if you want to consider obstacles, use the breadth first search from my other answer.

In case anyone needs it, here's the C# implementation of Patel's algorithm:

IEnumerable<Hex> GetRange(Hex center, int range)
{
var inRange = new List<Hex>();
for (int q = -range; q <= range; q++)
{
int r1 = Math.Max(-range, -q - range);
int r2 = Math.Min(range, -q + range);
for (int r = r1; r <= r2; r++)
{