Enemy Pathfinding

04 November 2018
So it's been a while... Sorry about that. Got really burned out on programming between work and trying to do this. Good news though, I'm back! I think I made some good progress today as well. I mostly finished the fog of war system, and got basic Enemy Ship Movement working with some path finding. For the fog of war I'll have to deal with the fact that at some point the bad guys won't be black dots. Oh well, Progress!

Let's get into path finding. I implemented a form of Dijkstra's algorithm, it's basically a brute force path finding system. But for my needs it's good enough, if it becomes a problem I'll switch it over to A*. Before we jump into code let me quickly go over how it works.

The basic idea is you start from the end point, slowly expanded out and ignoring steps you have already been on or are impossible to move to. Every iteration you add one to value, you continue this till you find the start point. From there you grab the start point, and remove one from the value and check what node is next to it with that new value, and repeat. Using this you expand out from the end point, find the start point, then trace back though the values to find the best path.

public void Move(int x, int y)
if (Mathf.Abs(Pos.x - x) <= Sight && Mathf.Abs(Pos.y - y) <= Sight)
var playerPos = new Vector2Int(x, y);
Dictionary<Vector2Int, int> pointVals = new Dictionary<Vector2Int, int>();
if(FromEndToStart(ref pointVals, Pos, playerPos))
Pos = FromStartToEnd(pointVals, Pos);
transform.localPosition = new Vector3(Pos.x + .5f, Pos.y + .5f);
Okay, starting from the parameters, x and y, this is the current position of the player ship. We then check if it's within sight. Right now Sight is hard coded to 6, but that will most likely change. the anded if statement checks if it's within 6 of the x value and then within 6 of the y value. If it is, it will start to move in. Then we just call the path finding stuff. The next if we use to not bother doing more work if we can't find a path, in which case we don't move.

private bool FromEndToStart(ref Dictionary<Vector2Int, int> pointVals, Vector2Int start, Vector2Int end)
pointVals.Add(end, 0);
var max = sight * sight;
for(int move = 0; move <= max; move++)
var tempDic = new Dictionary<Vector2Int, int>(pointVals);
foreach (var item in pointVals.Where(x => x.Value == move))
var up = new Vector2Int(item.Key.x, item.Key.y + 1);
if (CheckCanMove(up))
AddToPathDic(ref tempDic, up, item.Value + 1);

var down = new Vector2Int(item.Key.x, item.Key.y - 1);
if (CheckCanMove(down))
AddToPathDic(ref tempDic, down, item.Value +1);

var right = new Vector2Int(item.Key.x + 1, item.Key.y);
if (CheckCanMove(right))
AddToPathDic(ref tempDic, right, item.Value + 1);

var left = new Vector2Int(item.Key.x - 1, item.Key.y);
if (CheckCanMove(left))
AddToPathDic(ref tempDic, left, item.Value + 1);

pointVals = tempDic;
if (pointVals.ContainsKey(start))
return true;
return false;
Alright, this is the method that expands out from the end point. We first add the end point to pointVals, This Dictionary of Vector2Int and ints holds onto all the nodes and positional values. Obviously the end point has a value of 0, because that means you are 0 steps away! We get a max value using sight times sight, if we can't find the end by then, we won't find it. Next we set up a tempDic, you can't foreach on a collection you are modify, so we create a copy of pointVals, to then be set back to pointVals latter. After that we foreach over everything in pointVals where the value is equal to the current move value. That way we don't check over things we already checked. I'll summarize what's in the foreach; we check 4 directions, see if we can move, if so we add it to the dictionary. Finally we just check if the start is in the dictionary yet, if it is, return true. Oh at this point I should note we use ref on the dictionary so it stays modified.

AddToPathDic isn't a very interesting method. If the new value is somehow less then the old value replace it, if it's not there, add it. CheckCanMove just checks if that area is a Land or if there is another enemy ship there.

private Vector2Int FromStartToEnd(Dictionary<Vector2Int, int> pointVals, Vector2Int start)
var value = pointVals[start] - 1;
var temp = pointVals.Where(x => x.Value == value);
if (temp.Count() == 1)
return temp.First().Key;
foreach (var item in temp)
if (item.Key.x == start.x && Mathf.Abs(item.Key.y - start.y) == 1)
return item.Key;
if (item.Key.y == start.y && Mathf.Abs(item.Key.x - start.x) == 1)
return item.Key;
return start;
This is the last step! The name of this method is a little janky for what it does. I'll clean it up later. Anyways, we get the value using the start point as a key then lower that value by 1. Now we need to find where to move. If there is only one item with that value, take that, otherwise we need to get whatever is next to it. I do this by checking if it has the same X but 1 different Y, or same Y but 1 different X. If you watched the stream or youtube videos you might notice I got really confused on how to implement this. Honestly I think I was trying way to hard to wrap my head around it. It's not a very complex path finding system, but I was trying to think of crazy ways to change it.

Important PSA: Don't optimize till you have to

While you might want to write code the best way first, don't, unless you have the experience to know it will be a problem. Now this doesn't mean write crappy code, or something that you know will be horrible slow. Just so we are clear, when I say don't write the best way first, I mean in terms of speed, not quality of code.

Anyways, after getting that next position, we just move there and update that ships position. Now this might seem a bit wasteful to recalculate this every move, but I think it's what I have to do. Now I could keep track of a queue and add to it as the player moves, but says a play does a u-turn, the enemy is going to make the same needless turn, kinda silly I think.

Another issue, you might have noticed. The bots will only move in 4 directions, but the player can move in 8. This isn't really that big of a deal right now. Later I can always add the other 4 directions to that one method. Or maybe due to balanced or how I implement speed difference in ships, it will be fine.

Well that's all for today! It felt great to start working on my game again. If you have your own side project, don't feel bad about taking time off, don't get stressed, just work on it when you can!