15 September 2016
Engine: Unity
Language: C#
This is a flipped version of Dijkstra’s Algorithm that I made for a hex tile based battle game I’m working on. Units of troops have fixed movement amounts and each different type of terrain has a cost to enter that tile. Given that, this algorithm figures out every possible spaces a unit can move into using the least amount of movement. These spaces are then highlighted allowing players to get a full picture of their movement options.
The coordinate and neighbor assignment rules and the pseudo code I used as my starting point were based on Red Blob Game‘s Hexagonal Grids page. It’s a great resource for anyone using hexagonal boards for their games that even includes the math involved in aligning hexagons. I cant recommend it more highly!
The Code Explained:
Every tile is assigned an X and Y location value and has a list of all their neighbors. When the player selects a unit, the neighboring hexes are searched through to determine if that tile can be moved into based on the tile’s accessibility and the movement cost to enter the particular terrain. (ex. Hills cost more movement than plains but are still accessible. Units can never enter mountain tiles or tiles occupied by other units.)
A list of neighbors and the remaining movement power the unit would have if entering that tile is made. The neighbors of all those tiles are checked the same way as the initial neighbors, except this time if a more efficient path (a new rout with a lower movement cost) is found the lesser movement power is assigned to that destination tile.
This process repeats until no more tiles can be moved into. In the end, you’re left with a list of possible tiles the unit can move into and how much movement power that would expend. My game uses this information to highlight all possible tiles the unit can move into to give the player a clear visualization of their options for that particular unit. This algorithm can be scaled to account for any number of terrain effects or map sizes.
public static List<Node> TilesTroopCanMoveTo(GameObject Unit){
int x = (int)Unit.GetComponent<UnitData> ().tileLocation.x;
int y = (int)Unit.GetComponent<UnitData> ().tileLocation.y;
List<Node> possibleDestinations;
possibleDestinations = new List<Node> ();
List<Node> visited; //the list to see what tiles you already know you can visit. maybe it's useless because of possibleDestinations
visited = new List<Node> ();
List<Node> fringe; //this is the boarder of the currently checked tiles
fringe = new List<Node> ();
List<float> movementLeft; //when you add nodes to the fringe list you should also add to this array to keep track of the varying movement points you have left
movementLeft = new List<float> (); //movementLeft must always be the same length as fringe so their values correspond
float movement = Unit.GetComponent<UnitData>().movement;
visited.Add (graph [x, y]);
foreach (Node neighbor in graph [x, y].neighbours) { //visit all your immediate neighbors if you can
GameObject tileInQuestion = GameObject.Find ("/Map/Tile_" + neighbor.x + "," + neighbor.y);
if (tileInQuestion.GetComponent<TileData> ().accessable) {
possibleDestinations.Add (graph [neighbor.x, neighbor.y]);
visited.Add (graph [neighbor.x, neighbor.y]);
fringe.Add (graph [neighbor.x, neighbor.y]);
movementLeft.Add (movement - CostToEnterTile (tileInQuestion));
}
}
//is it checking all neighbors
int f;
while (fringe.Count > 0) {
f = fringe.Count;
while (f > 0) { //for ever tile in the current fringe
//remove the movementLeft and the fringe after this foreach loop but within the above wile loop
movement = movementLeft [0]; //movement left in the current fringe
foreach (Node neighbor in graph [fringe[0].x,fringe[0].y].neighbours) { //for each neighbor to the current fringe tile we're looking at
GameObject tileInQuestion = GameObject.Find ("/Map/Tile_" + neighbor.x + "," + neighbor.y);
//check if the neighbor you're looking at is within the fringes
if (!possibleDestinations.Contains (neighbor)) { //if it's not a possible destination or if it is and it has some un visited node neighbors
visited.Add (graph [neighbor.x, neighbor.y]); //this was making it so if you visited somewhere before and couldn't get to it one way you'd never be able to get to it
if (tileInQuestion.GetComponent<TileData> ().accessable) {
float entranceCost = CostToEnterTile (tileInQuestion);
if (!tileInQuestion.GetComponent<TileData> ().occupied) { //if unoccupied
if (movementLeft [0] >= entranceCost) {
possibleDestinations.Add (graph [neighbor.x, neighbor.y]);
fringe.Add (graph [neighbor.x, neighbor.y]);
movementLeft.Add (movement - entranceCost);
}
} else if (tileInQuestion.GetComponent<TileData> ().occupyingArmy == Unit.GetComponent<UnitData> ().army) //if the tile is occupied, ensure that the unit is friendly
if (movementLeft [0] >= entranceCost) {
possibleDestinations.Add (graph [neighbor.x, neighbor.y]);
fringe.Add (graph [neighbor.x, neighbor.y]);
movementLeft.Add (movement - entranceCost);
}
}
} else if (fringe.Contains (neighbor)) {
float entranceCost = CostToEnterTile (tileInQuestion);
if (movementLeft [0] >= entranceCost) { //if we can move in to the tile from our current position
int index = fringe.IndexOf (neighbor);
//only adjust movement cost for repeating ones if the movementLeft is greater. this would mean removing the tile and adding it again
if (movementLeft [index] < movementLeft [0] - entranceCost) //if it's easier to get into that fringe tile from this new rout
movementLeft [index] = movementLeft [0] - entranceCost;
}
}
}
fringe.RemoveAt (0);
movementLeft.RemoveAt (0);
f--;
}
}
return possibleDestinations;
}