# Hexagonal Grid Rangefinding

I am trying to develop an hexagonal turnbased strategy game and moving the units is giving me real trouble. Basicly what i want my programm to do is if u select an units all tiles that it can move to are higlited and once you moved it the tiles return to normal. The thing is that i have tyles that are inaccesabel and tiles that are harder to pass than others. like an forresttile takes two moventpoints, an grasstile takes one and mountains are inaccesabel. but if there is an gap between two mountains the unit must be able to drive trough it and then left and right.

So i developed an algorythmen which das the folloing things:

check all tiles in an straight line in all six directions if they are accesabel
once the first tile isnt accesabel (mountain or all movepoints are used) stop the loop,
for evry accesabel tile

check all tiles in an straight line in all six directions if they are accesabel
once the first tile isnt accesabel (mountain or all movepoints are used) stop the loop,
for evry accesabel tile

check all tiles in an straight line in all six directions if they are accesabel
once the first tile isnt accesabel (mountain or all movepoints are used) stop the loop,
for evry accesabel tile

. . .

this kinda works but it is not very fast and it can only change the direction as often as i reapet the code(in this case three times)
and my fastest unit can move up to 18 tiles and i have to assume that it may has to change direction evry tile. due to the fact that more often an unit rotates, the more possible ways it can go, the more tiles are chequed, number of chequed tiles grows exponetial with evry time i repeat the code. This algorhytmen would check for an unit that can move 18 tiles and possible change direction on evry tile
around

(6x18)x(6x17)x(6x16)x(6x15)x(6x14)x(6x13)x(6x12)x(6x11)x(6x10)x(6x9)x(6x8)x(6x7)x(6x6)x(6x5)x(6x4)x(6x3)x(6x2)x6
=650224796128741650855886848000 tiles

in the end it would return the right range the unit can move but it would take an ridicules amount of time. There must be an better way to do this. I am not asking for any code but an idea how to solve this would be nice. Thx alot for any advice you might be able to give me.

Well, since you have a dynamic environment there’s no way around checking each tile until you run out of movement points. However i would suggest to use a similar apporach to “A*”, just that you don’t have an actual target. So you would simply add your starting tile to an “open” list. When a tile is expanded you check all 6 neighbor tiles and add them to the open list. Once a tile is expanded you remove it from the openlist and add it to a “closed” list.

When checking the neighbor tiles you don’t readd a tile that is already on the closed list. It’s important that you sort your openlist by the “left over movement points” so that the tile with the most movement points left should be processed first. That ensures that you get the “best” way to each tile. For each tile you should save the remaining movement points, so when expanding to a neighbor you use that value as reference. The start tile should be initialized with your available movement points.

edit

Since we don’t know how your grid data is actually stored we can only provide abstract pseudo code.

``````List<Tile> GetNeighbors(Tile) // should return all 6 neighbors of the given tile.
float GetCost(Tile) // should return the cost of that tile.

List<Tile> openList = new List<Tile>();
List<Tile> closedList = new List<Tile>();
Dictionary<Tile, float> movementPoints = new Dictionary<Tile, float>();

void ExpandTile(Tile aTile)
{
float parentPoints = movementPoints[aTile];
foreach (var tile in GetNeighbors(aTile))
{
if (closedList.Contains(tile) || openList.Contains(tile))
continue;
float points = parentPoints - GetCost(tile);
if (points < 0)
{
// this tile is outside of the reachable area
continue;
}
movementPoints[tile] = points;
}
}

void CalcRange(Tile aStartingTile, float aMovementPoints)
{
openList.Clear();
closedList.Clear();
movementPoints[aStartingTile] = aMovementPoints;
ExpandTile(aStartingTile);
while (openList.Count > 0)
{
openList.Sort((a,b)=> movementPoints[a].CompareTo(movementPoints**) );**
``````

var tile = openList[openList.Count - 1];
openList.RemoveAt(openList.Count - 1);
ExpandTile(tile);
}
}
I’ve tested this with a normal x / y grid and it works as expected:

I added a “virtual” obstacle(cost >5000) on the lower left side and a “light” obstacle on the top left side (cost “3” instead of “1”).
The yellow cubes are the grid positions that are outside the reachable area. The red cubes are the 5000+ obstacle and the rest are the movable tiles with a color faded according to their remaining movement points.