Hello there, I’ve joined to the Bosonauts team some weeks ago and had to build the IA. I was searching on the web to see if there was any interesting or cleaver way to do the navigation map, but I couldn’t find any article relevant, so I wanna share how I did it.
The Navigation Map
First we will separate the map in Areas, the Tilemap was given so this is kinda trivial. The colors are this:
switch (node.type)
{
case NavMap.NodeType.GOAL:
Gizmos.color = Color.green;
break;
case NavMap.NodeType.AIR:
Gizmos.color = Color.white;
break;
case NavMap.NodeType.BLOCKED:
Gizmos.color = Color.black;
break;
case NavMap.NodeType.LEFT_WALL:
Gizmos.color = Color.magenta;
break;
case NavMap.NodeType.RIGHT_WALL:
Gizmos.color = Color.magenta;
break;
case NavMap.NodeType.LEFT_WALL_EDGE:
Gizmos.color = Color.green;
break;
case NavMap.NodeType.RIGHT_WALL_EDGE:
Gizmos.color = Color.green;
break;
case NavMap.NodeType.LEFT_EDGE:
Gizmos.color = Color.cyan;
break;
case NavMap.NodeType.RIGHT_EDGE:
Gizmos.color = Color.cyan;
break;
case NavMap.NodeType.SOLO:
Gizmos.color = Color.cyan;
break;
case NavMap.NodeType.ROOF:
Gizmos.color = Color.yellow;
break;
case NavMap.NodeType.DEATH:
Gizmos.color = Color.red;
break;
case NavMap.NodeType.PLATFORM:
Gizmos.color = Color.gray;
break;
case NavMap.NodeType.RIGHT_STEEP:
Gizmos.color = Color.blue;
break;
case NavMap.NodeType.LEFT_STEEP:
Gizmos.color = Color.blue;
break;
case NavMap.NodeType.ONE_WAY:
Gizmos.color = Color.blue;
break;
}
Applied, the map looks like this:
I think everyone here can Imagine how to build this, but just in case:
private void UpdateNodeTypes()
{
//Initialize node list.
for (int row = 0; row < nodes.Length; row++)
{
for (int col = 0; col < nodes[row].Length; col++)
{
if (nodes[row][col].tile.IsSolid())
{
if (IsDeath(nodes[row][col]))
{
nodes[row][col].type = NodeTypes.DEATH;
}
else
{
nodes[row][col].type = NodeTypes.BLOCKED;
}
}
else if (IsWallEdge(nodes[row][col]))
{
nodes[row][col].type = NodeTypes.WALL_EDGE;
}
else if (IsLeftWall(nodes[row][col]))
{
nodes[row][col].type = NodeTypes.LEFT_WALL;
}
//....
You can imagine the rest
Most of the checks methods, for me, look like this:
private bool IsPlatform(Node node)
{
//if under us ther's a solid tile, we can walk.
if (node.position.row > 0 &&
levelEditor.getTile(node.position.row - 1, node.position.col).isSolid() &&
!IsDeath(nodes[node.position.row - 1][node.position.col])) return true;
return false;
}
//....
if you look at the map, the roofs have a height of 2, that’s because the units have a height of 2, so this simplify the checks, I could change the top row to blocked or something but no need.
And that’s it, now it’s time to start the Navigation Map.
Links
let’s start with the Run links, this apply when you can just run from one node to the next:
One thing that I want to mension and that you can’t see in the last picture is that every node is connected with the rest of the platform, this is for saving time when you want that a character run over a platform.
Let’s see the code:
private void GenerateRunLinks()
{
Node currentNode;
Node sideNode;
for (int row = 0; row < nodes.Length; row++)
{
for (int col = 0; col < nodes[row].Length; col++)
{
currentNode = nodes[row][col];
if (currentNode.type == NodeType.PLATFORM)
{
sideNode = nodes[row][col];
for (int i = 1; sideNode.type != NodeType.RIGHT_EDGE && sideNode.type != NodeType.BLOCKED && col + i < nodes[0].Length; i++)
{
sideNode = nodes[row][col + i];
if (sideNode.type != NodeType.BLOCKED &&
(sideNode.type == NodeType.RIGHT_EDGE || i % 3 == 0)) //the 3 is completely abitrary.
currentNode.AddLinkTo(sideNode, LinkType.RUN);
}
sideNode = nodes[row][col];
for (int i = 1; sideNode.type != NodeType.LEFT_EDGE && sideNode.type != NodeType.BLOCKED && col - i > 0; i++)
{
sideNode = nodes[row][col - i];
if (sideNode.type != NodeType.BLOCKED &&
(sideNode.type == NodeType.LEFT_EDGE || i % 3 == 0))
currentNode.AddLinkTo(sideNode, LinkType.RUN);
}
}
else if (currentNode.type == NodeType.LEFT_EDGE)
{
sideNode = nodes[row][col];
for (int i = 1; sideNode.type != NodeType.RIGHT_EDGE && sideNode.type != NodeType.BLOCKED && col + i < nodes[0].Length; i++)
{
sideNode = nodes[row][col + i];
if (sideNode.type != NodeType.BLOCKED &&
(sideNode.type == NodeType.RIGHT_EDGE || i % 3 == 0))
currentNode.AddLinkTo(sideNode, LinkType.RUN);
}
}
else if (currentNode.type == NodeType.RIGHT_EDGE)
{
sideNode = nodes[row][col];
for (int i = 1; sideNode.type != NodeType.LEFT_EDGE && sideNode.type != NodeType.BLOCKED && col - i > 0; i++)
{
sideNode = nodes[row][col - i];
if (sideNode.type != NodeType.BLOCKED &&
(sideNode.type == NodeType.LEFT_EDGE || i % 3 == 0))
currentNode.AddLinkTo(sideNode, LinkType.RUN);
}
}
else if (currentNode.type == NodeType.RIGHT_STEEP)
{
sideNode = nodes[row + 1][col + 1];
currentNode.AddLinkTo(sideNode, LinkType.RUN);
}
else if (currentNode.type == NodeType.LEFT_STEEP)
{
sideNode = nodes[row + 1][col - 1];
currentNode.AddLinkTo(sideNode, LinkType.RUN);
}
}
}
}
And that’s it!
The Falls
when you fall, you have a lot of options, we could check for every one of them but the Navigation Map would be HUGE, and we don’t need that much precision so let’s simplify it with the max left, max right and middle:
We have some particular cases that we can check specifically if we want:
- The walls and platform edges where we only need to check one direction.
- the wall edges where we sometimes need to ignore the blocked node beside it because if not, the player will get stuck there sometimes.
- the nodes that are the top of a column, from there you can fall to the left or right but not the middle.
- The rest.
Let’s see the code:
private void GenerateFallLinks(float maxHorizontalSpeed, float gravity)
{
for (int row = 0; row < nodes.Length; row++)
{
for (int col = 0; col < nodes[row].Length; col++)
{
if (!nodes[row][col].reachable) continue;
NodeType type = nodes[row][col].type;
if (type != NodeType.BLOCKED &&
type != NodeType.PLATFORM &&
type != NodeType.DEATH)
{
if (type == NodeType.RIGHT_EDGE)
{
if (row > 0 && col > 0)
{
Node left = GetFallNode(nodes[row][col], new Vector2(maxHorizontalSpeed, gravity), NodeType.RIGHT_WALL);
if (left != null && left.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(left, LinkType.FALL);
}
}
if (type == NodeType.LEFT_EDGE)
{
if (row > 0 && col < nodes[0].Length - 1)
{
Node right = GetFallNode(nodes[row][col], new Vector2(-maxHorizontalSpeed, gravity), NodeType.LEFT_WALL);
if (right != null && right.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(right, LinkType.FALL);
}
}
else if (type == NodeType.RIGHT_WALL)
{
Node left, center;
left = GetFallNode(nodes[row][col], new Vector2(-maxHorizontalSpeed, gravity));
center = GetFallNode(nodes[row][col], new Vector2(0, gravity));
if (left != null && left.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(left, LinkType.FALL);
if (center != null && center.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(center, LinkType.FALL);
}
else if (type == NodeType.LEFT_WALL)
{
Node right, center;
right = GetFallNode(nodes[row][col], new Vector2(maxHorizontalSpeed, gravity));
center = GetFallNode(nodes[row][col], new Vector2(0, gravity));
if (right != null && right.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(right, LinkType.FALL);
if (center != null && center.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(center, LinkType.FALL);
}
else if (type == NodeType.SOLO)
{
Node left, right;
left = GetFallNode(nodes[row][col], new Vector2(-maxHorizontalSpeed, gravity));
right = GetFallNode(nodes[row][col], new Vector2(maxHorizontalSpeed, gravity));
if (left != null && left.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(left, LinkType.FALL);
if (right != null && right.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(right, LinkType.FALL);
}
else if (type == NodeType.ROOF || type == NodeType.AIR || type == NodeType.LEFT_WALL_EDGE || type == NodeType.RIGHT_WALL_EDGE)
{
Node left, right, center;
left = GetFallNode(nodes[row][col], new Vector2(-maxHorizontalSpeed, gravity));
right = GetFallNode(nodes[row][col], new Vector2(maxHorizontalSpeed, gravity));
center = GetFallNode(nodes[row][col], new Vector2(0, gravity));
if (left != null && left.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(left, LinkType.FALL);
if (right != null && right.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(right, LinkType.FALL);
if (center != null && center.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(center, LinkType.FALL);
}
}
}
}
}
GetFallNode is what you can expect:
private Node GetFallNode(Node origen, Vector2 direction, NodeType ignoreType = NodeType.NONE)
{
if (direction == Vector2.zero) return origen;
if (origen.size == 0) return null;
Node currentNode = null;
Vector2 currentPosition = origen.worldPos;
Vector2 lapsedDirection = direction.normalized * origen.size / 2f;
do
{
currentPosition += lapsedDirection;
currentNode = GetNodeInWorldPos(currentPosition);
if (currentNode == null) return null;
if (currentNode.NodeDistanceTo(origen) > 1 ||
currentNode.type != NodeType.AIR && currentNode.type != ignoreType)
{
return currentNode;
}
}
while (currentNode != null);
return null;
}
something that I wanna say is currentNode.NodeDistanceTo(origen), with this we can ignore some type of nodes around us. Kinda usefull some times.
The global position too is what you can expect:
private Node GetNodeInWorldPos(Vector3 worldPos)
{
for (int row = 0; row < nodes.Length; row++)
{
for (int col = 0; col < nodes[row].Length; col++)
{
if (nodes[row][col].IsInWorldPos(worldPos))
return nodes[row][col];
}
}
return null;
}
public bool IsInWorldPos(Vector3 posToCheck)
{
return Mathf.Abs(posToCheck.x - worldPos.x) < size &&
Mathf.Abs(posToCheck.y - worldPos.y) < size;
}
So.. when we see all the falls we have something like this:
The Jumps
The jumps are similar to the falls, with the difference that we are going UP.
Like the last time.. we have some special cases:
- We have the walls, if we jump using a wall, we will get propulsed to the oposite side.
- The stairs, here we will jump to the oposite side or up.
- The rest.
Let’s see the code:
private void GenerateJumpLinks(float maxJumpDistance, float maxHorizontalSpeed)
{
for (int row = 0; row < nodes.Length; row++)
{
for (int col = 0; col < nodes[row].Length; col++)
{
if (!nodes[row][col].reachable) continue;
NodeType type = nodes[row][col].type;
if (type != NodeType.BLOCKED &&
type != NodeType.DEATH)
{
if (type == NodeType.RIGHT_WALL || type == NodeType.RIGHT_WALL_EDGE)
{
Node left = GetJumpNode(nodes[row][col], new Vector2(-1, 1), maxJumpDistance, 2);
if (left != null && left.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(left, LinkType.WALL_JUMP);
}
else if (type == NodeType.LEFT_WALL || type == NodeType.LEFT_WALL_EDGE)
{
Node right = GetJumpNode(nodes[row][col], new Vector2(1, 1), maxJumpDistance, 2);
if (right != null && right.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(right, LinkType.WALL_JUMP);
}
else if (type == NodeType.LEFT_STEEP)
{
Node right, center;
right = GetJumpNode(nodes[row][col], new Vector2(maxHorizontalSpeed, maxJumpDistance), maxJumpDistance, 1);
center = GetJumpNode(nodes[row][col], new Vector2(0, maxJumpDistance), maxJumpDistance, 1);
if (right != null && right.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(right, LinkType.JUMP);
if (center != null && center.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(center, LinkType.JUMP);
}
else if (type == NodeType.RIGHT_STEEP)
{
Node left, center;
left = GetJumpNode(nodes[row][col], new Vector2(-maxHorizontalSpeed, maxJumpDistance), maxJumpDistance, 1);
center = GetJumpNode(nodes[row][col], new Vector2(0, maxJumpDistance), maxJumpDistance, 1);
if (left != null && left.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(left, LinkType.JUMP);
if (center != null && center.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(center, LinkType.JUMP);
}
else if (type == NodeType.SOLO ||
type == NodeType.AIR ||
type == NodeType.PLATFORM ||
type == NodeType.LEFT_EDGE ||
type == NodeType.RIGHT_EDGE ||
type == NodeType.ONE_WAY)
{
Node left, right, center;
left = GetJumpNode(nodes[row][col], new Vector2(-maxHorizontalSpeed, maxJumpDistance), maxJumpDistance, 2);
right = GetJumpNode(nodes[row][col], new Vector2(maxHorizontalSpeed, maxJumpDistance), maxJumpDistance, 2);
center = GetJumpNode(nodes[row][col], new Vector2(0, maxJumpDistance), maxJumpDistance, 2);
if (left != null && left.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(left, LinkType.JUMP);
if (right != null && right.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(right, LinkType.JUMP);
if (center != null && center.type != NodeType.BLOCKED)
nodes[row][col].AddLinkTo(center, LinkType.JUMP);
}
}
}
}
}
GetJumpNode is almost the same of GetFall, with the difference that we have a max distance, in that case, wi will return the node, even if it’s air:
private Node GetJumpNode(Node origen, Vector2 direction, float maxJumpDistance, float minJumpHeight, NodeType ignoreType = NodeType.NONE)
{
Node currentNode = null;
Vector2 currentPosition = origen.worldPos;
Vector2 lapsedDirection = direction.normalized * ((float)levelEditor.TileSize / 2.0f);
do
{
currentPosition += lapsedDirection;
currentNode = GetNodeInWorldPos(currentPosition);
if (currentNode != null)
{
if (currentNode.type == NodeType.BLOCKED) return currentNode;
if (currentNode.NodeDistanceTo(origen) >= maxJumpDistance)
{
if (currentNode.type == NodeType.ONE_WAY)
return null;
else return currentNode;
}
if (currentNode.NodeDistanceTo(origen) >= minJumpHeight &&
currentNode.type != NodeType.AIR &&
currentNode.type != NodeType.ONE_WAY &&
currentNode.type != ignoreType)
return currentNode;
}
} while (currentNode != null);
return null;
}
Before continue, I will talk a bit about the Links:
public class NodeLink
{
public Node target;
public Node source;
public LinkTypes type;
public float weight;
}
As you can see, we get a target node, source node a type of link and a weight.
When we create it I just check that is not duplicated and set the references:
public void AddLinkTo(Node node, LinkTypes type)
{
if (node == null) return;
if (node == this) return;
if (ContainLinkToNode(node, type)) return;
NodeLink linkTo = new NodeLink();
linkTo.target = node;
linkTo.source = this;
linkTo.type = type;
linkTo.weight = calculateWeight(this, node);
linkedTo.Add(linkTo);
node.AddParent(this, type);
}
Probably I will need this in the future so let’s register were we came from too:
node.AddParent(this, type);
private void AddParent(Node node, LinkTypes type)
{
if (node == null) return;
if (node == this) return;
if (ContainLinkFromNode(node, type)) return;
NodeLink link = new NodeLink();
link.target = node;
link.source = this;
link.type = type;
link.weight = calculateWeight(this, node); ;
linkToParent.Add(link);
}
So now, a node will looks like this:
Great, now we only need to know what nodes are in contact with this links, to do that I did something like this:
public void UpdateNodesBetweenLinks()
{
//Initialize node list.
for (int row = 0; row < nodes.Length; row++)
{
for (int col = 0; col < nodes[row].Length; col++)
{
Node n = nodes[row][col];
for (int linkIndex = 0; linkIndex < n.linkedTo.Count; linkIndex++)
{
Link l = n.linkedTo[linkIndex];
l.AddInteractedNodes(GetNodesBetween(l.getSource(), l.getTarget()));
}
}
}
}
private List<Node> GetNodesBetween(Node startNode, Node endNode)
{
List<Node> nodes = new List<Node>();
Vector2 currentPosition = startNode.worldPos;
Vector2 direction = (endNode.worldPos - startNode.worldPos);
Vector2 lapsedDirection = direction.normalized * levelEditor.TileSize / 4;
float maxDistance = Vector2.SqrMagnitude(direction);
Node currentNode;
do
{
currentPosition += lapsedDirection;
currentNode = GetNodeInWorldPos(currentPosition);
if (currentNode != null && currentNode != startNode && currentNode != endNode)
{
if (!nodes.Contains(currentNode))
nodes.Add(currentNode);
}
}
while (currentNode != endNode && currentNode != null && Vector2.SqrMagnitude(startNode.worldPos - currentPosition) < maxDistance);
return nodes;
}
and that’s it. We will have something like this:
Okey, it’s not perfect, but it works!
And when every node is enabled, it will look like this:
So the rest is just pick a node and find a path to another..
PathFinding
The basic idea is quite simple:
- We take a node
- open the nodes that we are linked to (if they are not closed)
- close the current node
- save the new paths.
- Repeat until a node is linked to the node that we want.
In the first iteration we have some thing like this:
In the second:
Third…
Fourth!
Ok, there’s a problem here.. too many nodes.
Fifth..
How do we reduce the amount? let’s kill the bad paths!
I will add a new step:
6. erase the bad paths and store just the best…five?
To know what path is better I store the current distance plus the manhattan distance to the target node
Let’s try again, starting from the Fifth iteration
Sixth:
A Lot better!
Now we just need to repeat until the target.
As we can see in the last picture, maybe the target isn’t in the extremes of the link but between them, but checking this every time is quite a bit slower, so what I do is check only if the distance to target from the current node is less than the length of the link.
Great, we are almost there.. just there’s a tiny detalil that we almost forgot…
- if the path is phisically possible!
For example, is not good if a path requiere to walk over Lava or jump 3 times (limit 2).. we need to check it!
So.. I will add a new step the 3.5:
3. Close the current node
3.5 check validity.
4. store the valid paths.
Perfect, we have the basic logic, now is just implement it:
public Path GetPath(Node startNode, Node endNode, bool canStartJumping = true, int maxSteeps = 200)
{
closedNodes = new List<Node>();
frontierPaths = new List<Path>();
Path validPath;
OpenNeighbors(startNode, canStartJumping);
for (int i = 1; i < maxSteeps && HasOpenPaths(); i++)
{
if (HasReachedTarget(out validPath))
{
return validPath;
}
UpdateFrontierPaths();
RemovePoorPaths();
}
return null;
}
canStartJumping can we start jumping in the new path?
maxSteeps how many iterations max to determine that we have a path?
private void OpenNeighbors(Path path)
{
if (IsBadPath(path)) return;
if (!closedNodes.Contains(path.GetLastNode()))
{
closedNodes.Add(path.GetLastNode());
Node n = path.GetLastNode();
if (n == null) return;
foreach (Link link in n.linkedTo)
{
if (closedNodes.Contains(link.getTarget())) continue;
Path p = path.Clone();
p.weight += link.getSource().NodeDistanceTo(link.getTarget()) + link.getTarget().NodeDistanceTo(endNode);
p.links.Add(link);
if (!IsBadPath(p))
frontierPaths.Add(p);
else closedNodes.Add(link.getTarget());
}
}
}
IsBadPath is up to your game.
UpdateFrontierPaths and it start over
private void UpdateFrontierPaths()
{
oldPaths = frontierPaths;
frontierPaths = new List<Path>();
foreach (Path path in oldPaths)
{
OpenNeighbors(path);
}
}
Well now you can get the general idea, but Important:
I’m not checking for paths without exit, if you want to check for them you should add:
- No valid paths?
- We go back to the parent of our best node
- check if we have any linked node that’s not closed
- We start checking this new path.
- If not, we go back to the point 1.1
With this we won’t get the very best path, but almost.
Read you later!
M.
Leave a Reply