- Home /
A* Pathfinding Bug: Dictionary Key Not Found Exception
Hey, I'm making a tower defense game which of course involves pathfinding and waves of enemies being generated. I've encountered a really strange bug however.
Basically, when a wave is generated each enemy generated has an enemy script which calls the FindPathTo(Vector2 endGoal) method on the Pathfinding script.
public List<Tile> FindPathTo(Vector2 target){
//key node visited, value: node you came from to arrive
Dictionary<Tile, Tile> cameFrom = new Dictionary<Tile, Tile>();
//nodes to visit
List<Tile> frontier = new List<Tile>();
List<Tile> path = new List<Tile>();
//Add the tile currently inhabited by the AI to the frontier and to the dictionary with a null value
frontier.Add(GameController.tiles[(int) (transform.position.x - GameController.xOrigin), (int)(transform.position.y - GameController.yOrigin)].GetComponent<Tile>());
cameFrom.Add(frontier[0].GetComponent<Tile>(), frontier[0].GetComponent<Tile>());
//Flood Fill all the empty tiles the AI can move to
while(frontier.Count > 0){
//Find the last tile added to it
Tile current = frontier[0];
foreach (Tile t in FindNeighbors(current.transform.position)){
// Debug.Log (cameFrom.ContainsKey(t) + " " + t.transform.position);
if(! cameFrom.ContainsKey(t) && !t.isFilled){
frontier.Add(t);
cameFrom.Add(t, current);
}
}
frontier.RemoveAt(0);
}
//Construct path start at the goal
Tile currentTile = GameController.tiles[(int) (target.x - GameController.xOrigin), (int)(target.y - GameController.yOrigin)].GetComponent<Tile>();
Tile startTile = GameController.tiles[(int) (transform.position.x - GameController.xOrigin), (int)(transform.position.y - GameController.yOrigin)].GetComponent<Tile>();
path.Add(currentTile);
//And work backwards until you get to the current position
while (currentTile != startTile){
try{
currentTile = cameFrom[currentTile];
path.Add(currentTile);
}
catch{
Debug.Log("Key Not Found");
Debug.Log("Current Tile is" + currentTile.transform.position);
currentTile = cameFrom[GameController.tiles[(int) (target.x - GameController.xOrigin), (int)(target.y - GameController.yOrigin + 1)].GetComponent<Tile>()];
path.Add(currentTile);
}
}
path.Reverse();
path.RemoveAt(0);
return path;
}
Now for the strange part. When my first wave is generated all the enemies are spawned without error. However, when the next wave is spawned if an enemy is ever spawned on the same tile that an enemy was generated on previously the FindPathTo method raises the following exception
KeyNotFoundException: The given key was not present in the dictionary.
System.Collections.Generic.Dictionary`2[Tile,Tile].get_Item (.Tile key) (at /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System.Collections.Generic/Dictionary.cs:150)
Pathfinding.FindPathTo (Vector2 target) (at Assets/Scripts/Pathfinding.cs:47)
Enemy.Start () (at Assets/Scripts/Enemy.cs:41)
I implemented a try-catch to print out all the values in the cameFrom dictionary whenever the exception was raised and found that the tile that the enemy was starting on was in fact not in the dictionary so I basically tried to force it in whenever the exception was raised, adding the tile to the dictionary results in even stranger behavior, sometimes it will cause everything to run perfectly well other times it will freeze the game for about 30 seconds then give me the following exception.
ArgumentException: An element with the same key already exists in the dictionary.
System.Collections.Generic.Dictionary`2[Tile,Tile].Add (.Tile key, .Tile value) (at /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System.Collections.Generic/Dictionary.cs:404)
Pathfinding.FindPathTo (Vector2 target) (at Assets/Scripts/Pathfinding.cs:56)
Enemy.Start () (at Assets/Scripts/Enemy.cs:41)
The only workaround that I found that allows everything to run smoothly is the one you see in my code above, where I simply skip down to the second tile whenever the exception is raised. I've ran through about 15 waves with this code without getting any errors.
I guess my question is 1) Why does this error only occur after the first wave? 2)Why does it only occur when an enemy starts on a tile that an enemy previously spawned on?
EDIT: Edited to reflect new strange behavior regarding the "force add" workaround
Answer by Unitraxx · Oct 05, 2014 at 05:33 PM
I think the strange thing you do here (and in other places), might explain your dictionary mismatches :
cameFrom.Add(frontier[0].GetComponent<Tile>(), frontier[0].GetComponent<Tile>());
frontier
is a list of Tile
s, yet you do frontier[0].GetComponent()
instead of just frontier[0]
. Why?
Right, because they are getting the tiles from the GameController which stores them in GameObject array. I can't exactly remember why I did that? I'll look over it again
Your answer
![](https://koobas.hobune.stream/wayback/20220613164440im_/https://answers.unity.com/themes/thub/images/avi.jpg)
Follow this Question
Related Questions
Distribute terrain in zones 3 Answers
Multiple Cars not working 1 Answer
Movement around a huge object by avoiding obstacles 1 Answer
The name 'Joystick' does not denote a valid type ('not found') 2 Answers
Evade a Collider on Vector3.forward 3 Answers