Path finding freezes Unity

Questions & Answers
1

So I am trying to create a path finding code for a turn-based game in a grid environment, I rewrote my code a lot of times in different ways, but it always ends freezing Unity, and I can’t find out whats wrong.

	private void Move (GameObject t, GameObject c)
	{
		Debug.Log("Cheking at " + c.name);
		if (t.gameObject.GetComponent<TileProps> ().walkable && !t.GetComponent<TileProps>().occupied) {
			
			Collider[] nT = Physics.OverlapSphere(c.transform.position, tileSize);
			
			List<GameObject> neighbors = new List<GameObject>();
			
			foreach(Collider z in nT){

				neighbors.Add(z.gameObject);
				
			}
			
			for(int i = 0; i < neighbors.Count; i++){
				Debug.Log(neighbors*.name);*

if(!neighbors.GetComponent().walkable || neighbors_.GetComponent().occupied || checkedTiles.Contains(neighbors*)){*_

_ neighbors.Remove(neighbors*);*_

* }*

* }*

* if(neighbors.Count > 0){*

* for(int i = 0; i < neighbors.Count; i++){*

_ checkedTiles.Add(neighbors*);
tempList.Add(neighbors);*_

_ if(neighbors != t){_

* Debug.Log(“Looping…”);*
_ Move(t, neighbors*);*_

* }else{*

* if(tempList.Count < numOfTiles){*

* tilesToMove = tempList;*
* numOfTiles = tempList.Count;*
* tempList.RemoveRange(0, tempList.Count);*

* }*

* if(checkedTiles.Count == mapM.GetComponent().tiles.Count){*

* checkedTiles.RemoveRange(0, checkedTiles.Count);*
* Debug.Log(“Path Calculated”);*

* if(numOfTiles <= actionP){*

* StartCoroutine(Move2());*

* }else{*

* Debug.Log(“Not enough action points.”);*

* }*

* }*

* }*
* }*

* }else{*

* Debug.Log(“Target is not walkable”);*
* return;*

* }*

* }*
* }*

2

in lines 15-25 i think you need to run reverce for loop to remove elements from list. so it will populate correct list in case any item removed from the list. it should be like that

     for(int i = neighbors.Count-1,i>=0; i--){
         Debug.Log(neighbors*.name);*

if(!neighbors.GetComponent().walkable || neighbors_.GetComponent().occupied || checkedTiles.Contains(neighbors*)){_
_neighbors.Remove(neighbors);
}
}_
_Secondly if you tring to use a path finding style for your game you need to check these link_
*https://tbswithunity3d.wordpress.com/2012/02/23/hexagonal-grid-path-finding-using-a-algorithm/*_
http://ledpup.blogspot.in/2011/06/unity-hexagons-and-path-finding.html*_
_these links about a path finding in hex grid but you can also use it nomral square grid via little bit change Tile Class.
Note:
this scripts are not optimized or follw ART runtime. if you need to use your code iOS device you also need to remove uses of genrics and use specfic type in method FindPath of Path Class and Enqueue, Dequeue methods from PriorityQueue Class
Happy coding bro,_

3

When your path is calculated and you start “StartCoroutine(Move2());” shouldn’t you abort your Move method? A “break” or “return” would be appropriate once you started the coroutine. Keep in mind since you use a recursive approach once you exit the innermost “Move” method you get back to the point where you called that one in line 36. Since you’re done with your path calculation you should make sure that all Move methods exit as soon as possible.

edit
Furthermore there are several things strange about your approach:

  • You use Physics.OverlapSphere which will include your current tile as well. You did not add the current tile to the checked list and didn’t exclude it from the neighbors list as well. Since you call “Move” again for every “neighbor” you check the first tile twice.
  • Using OverlapSphere for every step in your pathfinding is very inefficient. You should store the immediate neighbor list inside your “TileProps” class. This information is usually static. You only need to set it up once at start of the game.
  • Unlike algorithms like “A*” you seem to search randomly for a path. You have alot strange abort conditions like one of your finish conditions is that the checkedtile count == the count of all available tiles.
  • Btw: There is “List.Clear()” ^^
  • Once your checkedTiles count hits the available tile count you clear the checkedTiles list, either start the actual moving or not but you continoue searching once you started Move2. Since you cleared the checkedTiles list every tile can be checked again. This will most likely continoue forever.

To sum this up: It’s quite a mess ^^. Recursive approaches are dangerous and you easily loose track of the chain of execution. Even “A*” is usually implemented with a sorted queue. That doesn’t prevent an infinite loop, but it’s more obvious what the algorithm does and when it terminates (or not).

Keep in mind that you can use MonoDevelop to debug your Unity application. You can set breakpoints and step through your method and inspect the variables to see where it goes wrong.