Automated neighborhood retrieval and graph navigation in Unity3D tutorial - Empires in Ruins

Hi everybody,

Emiliano here! Today I am gonna give you some explanations on the way I used Unity's objects and Dijkstra's algorithm to build the neighborhood relations among provinces, and to provide the game engine a way to obtain the shortest path (in terms of walking distance for the troops) between two provinces (given that all the crossed ones but the target one belong to the player).

First of all, in order to implement the provinces neighborhood and the attack possibilities, I decided for a graphical approach. It would have been possible to manually write down to each province file the allowed attack paths and the provinces neighboring each province (the attacks have different lenght durations according to the geography of the terrain and sometimes are not possible as for example due to obstacles like rivers), but it would have been messy and it would have taken forever.

I therefore decided to go with a different (and easier) approach, that allows at the same time to configure the graphic look of the attack arcs (the red arrows) on the UI and to initialize for each province the correct data.

Starting from the first province and until the last one, for each province possible attack arc (between the province and a neighbor) I build a simple GameObject containing the arrow (already scaled and pointing from province A to province B), an UI Text containing the length of duration required for that attack path and a couple of additional UI elements just for the look. Each onbject is then name provinceAID-provinceBID (e.g. the attack arc from province 0 to province 1 is named "0-1").

Once the game initializes the provinces data for the first time (on the first loading), I then invoke the initialization of the arcs. Looping over the object containing all the arcs, I save each of them in a class named AttackArc. The class stores the following values :
attackProvince (the first of the two provinces in the object name, obtained by tokenizing the object name), targetProvince (the first of the two provinces in the object name, obtained by tokenizing the object name), duration, the whole object RectTransform (to quickly show or hide the arc on the map screen), the arrow RectTransform and the xScale value of the arrow (I will tell you soon why).

The last two elements are vital for the following reason. I am building up monodirectional attack arcs, but those same arcs will have to be used both ways in the game (so if province 0 can attack province 1, province 1 can also attack province 0). By swapping the sign of the X of the local scale for the arrow transform, we can indeed invert the arrow direction whenever we want to change the attack direction. Storing the original X scale allows us to store the information on the original direction of the arrow when built.

Once each AttackArc is built, I set its game object to active(false) (and so it will be set until I need to use it to plan an attack route) and we store the AttacArc class instance in a Dictionary structured this way :

public Dictionary<int, Dictionary<int,AttackArc>> attackArcs;

That means that each attack arc will be referenced twice : Once as <provinceAID,<provinceBID, AttackArc>> and once as <provinceBID,<provinceAID, AttackArc>>. A bit of redundance in the data structure here will be extremely helpful later in determining in a quicker way all the attack arcs for a single region, no matter if in the original object it was used as attacking or target one.

For each province, )I will have a dictionary that quickly references (with O(1) complexity for searches) another dictionary whose keys will be all the possible attackable provinces, and whose values will be the related AttackArcs objects (that contain all the visuals and stats data needed to use them).

Before going furter, I go through the whole structure and we assign to our provinces (kept in a structure in the main game engine) all the neighboring regions that are accessible through attack arcs (each region just has a list of integer that contains the key ID of each neighboring province).

Now I write a couple of short methods to do the do the following operations (mail me if you need help but it shall be quite trivial) :

Show the arc from province 1 to province 2 (correctly oriented so that the arrow points at province 2)
Show all the arcs going out from province 3
Hide a single specific arc from province 1 to province 2
Hide all the arcs currently displayed on the map

In order to grant a quick management of all the currently displayed arcs (later on I will use the built graph to show full attack paths that go through multiple arcs across multiple provinces), we keep a list of KeyValuePair<int,int> where the two integers are provinceA and provinceB (there is no risk of duplicates as you can't have simultaneously the arcs provinceA-provinceB and provinceB-provinceA.

Now all this is currently stored in a datastructure whose script has been built with the singleton pattern to make it quickly available from any class that might need it. The next step (coming soon) is to properly finish designin the attack graph and build the navigation algorithms. They will have to take into account the duration of each arc in order to build the shortest attack routes, and of the owner of the provinces on the way (the enemy would not be that happy to let you troops transit through his provinces).

The next step is to provide the engine a quick way to determine the shortest path (in terms of walk duration, the number shown on each arc) from A to B given that A is the province used to start the attack and belongs to the player.and the whole provinces on the way belongs to the player.
The problem is trivially solved using Dijkstra's algorithm for the graph navigation shortest path (for technicality's sake, the graph is a undirected and weighted one, and you can just look at the wikipedia page for the theory). I propose here the implementation I did (Unity3d, C#). Several features are bound to the game engine, but the main algo concept should be quite quickly easily understandable

I also uploaded a little video to show the results (the whole attack engine and graphics are still far from complete and for the testing it always uses the same province (Kalamheir) as attacking source, but it proves the results of the attack path building so far)

Well guys, that's for now. I hope that this devlog entry might give you some ideas on how to solve some problems you might be facing. I am definitely not saying there are no other ways to do what I did (possible even better ones :) ) but this was is now working really well for us, so, why not?

And as usual if you wanna stay tuned on the updates of Empires in Ruins, subscribe to our mailing list (we swear we won't ever spam you) or follow us on twitter or facebook. Cheers!

//contains all the indices of the provinces belonging to the player
	List<int> allPlayerProvinces;
	//store the distance of each node on the path so far
	Dictionary<int,int> distances;
	//for each node store the index to the preceding one
	Dictionary<int,int> previousOnes;
	//store the shortest path from A to B
	List<int> shortestPath;
	//<indexOfNode, distanceFromPrevious
	Dictionary<int,int> vertexQueue;

	public void InitSearch(){
		//init anew all the data structures used
		allPlayerProvinces=new List<int>();
		distances=new Dictionary<int,int>();
		shortestPath=new List<int>();
		previousOnes=new Dictionary<int,int>();
		vertexQueue = new Dictionary<int,int>();

		//get the data from the engine regarding the provinces belonging to the player
		allPlayerProvinces.AddRange(PlayerManager.playerControl.playerProvinces);
					
		//init the distances (with a very high number) and previous ones structures (-1 each)
		foreach(int elem in allPlayerProvinces){
			distances.Add(elem,10000);
			previousOnes.Add(elem,-1);
		}
	}

	public List<int> SeekPath(int start, int end){

		//init algorithm
		InitSearch();

		//add the target province also if not belonging to the player to the list of the available provinces for the search
		if(!allPlayerProvinces.Contains(end)){
			allPlayerProvinces.Add(end);
			distances.Add(end,10000);
			previousOnes.Add(end,-1);
		}

		int distance = 0;
		int current = 0;

		//add the starting node by default to the searching queue
		vertexQueue.Add(start,0);

		while (vertexQueue.Count()>0){
			distance=vertexQueue.First().Value;
			current=vertexQueue.First().Key;
			vertexQueue.Remove(current);

			//get all the neighbors of the province
			List<int> neighbors = GetNeighbors(current,end);

			foreach(int neigh in neighbors){
				int node = neigh;
				int currentDistance = attackArcs[current][neigh].duration;
				int distanceThroughNode = distance+currentDistance;
				//look for shorter path alternatives
				if(distanceThroughNode<distances[neigh]){
					if(vertexQueue.ContainsKey(neigh)) vertexQueue.Remove(neigh);
					distances[neigh]=distanceThroughNode;
					previousOnes[neigh]=current;
					vertexQueue.Add(neigh,distances[neigh]);
				}
			}
		}

		int check = end;

		//build the shortest path indices list
		while(true){
			if(check!=start){
				shortestPath.Add(check);
				check=previousOnes[check];
			}else{
				shortestPath.Add(check);
				break;
			}
		}	

		//return the shortest path
		return shortestPath;
	}

	//get all the neighboring provinces belonging to the player (of the target province if neighboring)
	public List<int> GetNeighbors(int node, int target){
		List<int> neighbors = new List<int>();
		foreach(int neigh in attackArcs[node].Keys){
			if(allPlayerProvinces.Contains(neigh)){
				neighbors.Add(neigh);
			}else{
				//the target province is the only node evaluated also if it doesn't belong to the player provinces
				if(neigh==target){
					neighbors.Add(neigh);
				}
			}
		}
		return neighbors;
	}

	//list to store the resulting shortest path
	List<int> results;

	public void PathFind(int targetProvince){
		//hides all the currently displayed attack arcs
		HideAllArcs();
		//get the shortest path and revert it (so that it starts from source to end)
		results = SeekPath(0,targetProvince);
		results.Reverse();
		//display all the arcs involved in the chosen path
		for(int i=0;i<results.Count()-1;i++){
			ShowArc(results[i],results[i+1]);
		}
	}