Introduction

In the previous article, we implemented the A* pathfinding algorithm for a 2D side-view platformer scenario. We updated the logic from the top-down example and introduced functionality to navigate through the grid more easily by using speaking method names instead of fiddling with grid coordinates directly. The goal there was to improve the readability. However, as the reader may have already noticed, we introduced something which is called a cyclic dependency.

What’s a Cyclic Dependency?

In software engineering, cyclic dependencies occur when two or more components depend on each other. In our example it is the grid and its cells which are interdependent. The grid depends on the cells and each cell depends on the grid. The latter was introduced so the cell can implement and expose methods for navigating from that cell to another cell in the grid. Here’s a quick UML diagram that illustrates this fact:

Circular Dependency between Grid and Cell

Circular Dependency between Grid and Cell

Let’s go back to the involved code for a moment and take a look at the Grid and Cell classes:

public class Grid
{
    private readonly Cell[,] _cells;
    
    public Grid(char[,] map)
    {
        _cells = new Cell[map.GetLength(1), map.GetLength(0)];
        
        for (var y = 0; y < map.GetLength(0); y++) {
            for (var x = 0; x < map.GetLength(1); x++) {
                _cells[x, y] = new Cell(x, y, CellTypeFromChar(map[y, x]), this);
                // ...
            }
        }    
    }
}

public class Cell(int x, int y, CellType type, Grid grid)
{
    // ...

    public Cell? Up => NeighborAt(0, -1);
    public Cell? Down => NeighborAt(0, 1);
    public Cell? Left => NeighborAt(-1, 0);
    public Cell? Right => NeighborAt(1, 0);
    
    // ...
    
    public Cell? NeighborAt(int deltaX, int deltaY) => grid[X + deltaX, Y + deltaY];

    // ...
}

The Grid constructor instantiates Cell objects and in turn injects a reference to itself to the Cell constructor. So, the grid has references to the cells and each cell has a reference to the grid. The reference to the grid is used in the NeighborAt(...) method which accesses the grid.

What’s so bad about Cyclic Dependencies?

Cyclic dependencies are problematic in that they often make the code less maintainable by making it less testable and modifiable. For example, to write a unit test for Cell you can’t simply instantiate a Cell object, you have to create a Grid object first, which in turn creates Cell instances.

How to avoid Cyclic Dependencies

There are ways to get rid of the cyclic dependency in the code. First of all, you can ask if the interdependence is even necessary. Often times, you’ll find that the dependency is only needed in one direction (as is indeed the case in our example). But, there are also cases where the interdependence is needed in both directions, in which case you can get rid of the circular dependency by applying … drumroll … dependency inversion. So, what’s dependency inversion you ask?

Dependency Inversion

Dependency inversion is one of the five SOLID principles. Here’s what Wikipedia says:

  1. High-level modules should not import anything from low-level modules. Both should depend on abstractions (e.g., interfaces).
  2. Abstractions should not depend on details. Details (concrete implementations) should depend on abstractions.

Let’s take a look at how this would look like in our example with a grid and cells.

No more circular dependency between Grid and Cell

No more circular dependency between Grid and Cell

Instead of the Grid class depending directly on the concrete Cell class, it now depends on an interface ICell which is implemented by Cell. So both the grid and the cell depend now on the interface. We have broken the circle!

Two questions that could be asked:

  1. Can anyone tell me what exactly the ICell interface is about?
  2. Now that the Grid class doesn’t know about the Cell class anymore, but only about the abstraction ICell, how is it supposed to instantiate concrete objects, since there is no constructor to invoke?

We’ll leave the answer to the first question open for now. For the latter, we need a mechanism for instantiating concrete Cell objects. One such mechanism is a pattern called Factory Method.

So what we could do is implement a factory which creates Cell objects and inject that factory into the Grid class.

Introduce a cell factory for creating concrete cell objects

Introduce a cell factory for creating concrete cell objects

Here’s a quick draft of the code (we’re not going to fully implement this):

public interface ICell { /* ... */ }

public class Cell(int x, int y, CellType type) : ICell
{
    // ..

    public Grid? Grid { get; set; }
    
    //...
}

public interface ICellFactory
{
    public ICell CreateCell(int x, int y, char cellTypeChar)
}

public class CellFactory : ICellFactory
{
    public ICell CreateCell(int x, int y, char cellTypeChar)
    {
        return new Cell(x, y, CellTypeFromChar(cellTypeChar));
    }
    
    private static CellType CellTypeFromChar(char c)
    {
        return c switch {
            ' ' => CellType.Empty,
            'B' => CellType.Block,
            'L' => CellType.Ladder,
            'H' => CellType.HangingBar,
            _ => throw new ArgumentException($"Invalid cell type: {c}")
        };
    }
}

… and then update the Grid class:

public class Grid : IEnumerable<ICell>
{
    private readonly ICell[,] _cells;

    // ...

    public Grid(char[,] map, ICellFactory cellFactory)
    {
        _cells = new ICell[/* ... */];
        for (var y = 0; /* ... */) {
            for (var x = 0; /* ... */) {
                _cells[x, y] = cellFactory.CreateCell(x, y, map[y, x]); 
                _cells[x, y].Grid = this;                
                // ...
            }
        }
    }
    
    // ...
}

Now, when instantiating a Grid object, we need to pass in a concrete CellFactory object:

public class Pathfinding
{
    // ...

    public Pathfinding()
    {
        _grid = new Grid(_map, new CellFactory()) {
            StartPosition = new Point(0, 10),
            TargetPosition = new Point(5, 1)
        };
        
        // ...
    }
}

While this would work, it might seem a bit too much. For example, why create an ICell interface if there will only ever be one concrete implementation and thus one concrete factory? At this point, it’s not really clear what the ICell interface is about, other than being used to decouple the Grid class from the concrete Cell implementation. Furthermore, although we have removed the cyclic dependency at a technical level, it can be argued that it still exists at a domain level. The question is, do we really need it at the domain level?

Let’s look at another possible solution to our cyclic dependency problem which is to remove the cell’s dependency on the grid altogether.

Moving the Grid Navigation Logic to its own Class

Here’s another way to get rid of the cyclic dependency. If you take a look at the Cell class and why it depends on the Grid class, you’ll see it’s because the cell uses the grid to navigate to neighboring cells.

One question that arises is why is it the cell’s responsibility to provide functionality for navigating around the grid? A possible answer to this question is: Well, it shouldn’t. The logic to navigate through the grid from a particular starting point could as well be put in its own class. Doing so would also benefit the separation of concerns principle.

So, let’s create a new class for this, called GridNavigator. Its sole purpose is to implement and expose the grid-navigation functionality. Let’s first update our little diagram:

The Grid Navigator

The Grid Navigator

Now, the Cell class has no more dependency on the grid. The navigation functionality is now located in the GridNavigator class, which depends on the Grid class. Here’s a possible implementation:

public class GridNavigator(Grid grid)
{
    private int _x;
    private int _y;

    public GridNavigator StartAt(Cell cell)
    {
        _x = cell.X;
        _y = cell.Y;
        return this;
    }
    
    public GridNavigator Up => MoveBy(0, -1);
    public GridNavigator Down => MoveBy(0, 1);
    public GridNavigator Left => MoveBy(-1, 0);
    public GridNavigator Right => MoveBy(1, 0);
    public GridNavigator DownRight => MoveBy(1, 1);
    public GridNavigator DownLeft => MoveBy(-1, 1);
    public GridNavigator UpRight => MoveBy(1, -1);
    public GridNavigator UpLeft => MoveBy(-1, -1);

    public GridNavigator MoveBy(int deltaX, int deltaY)
    {
        _x += deltaX;
        _y += deltaY;
        return this;
    }

    public Cell? Cell => grid[_x, _y];
}

The idea is to first kind of initialize the navigator by setting the starting cell with a call to StartAt(cell). Then, you can navigate through the grid by calling Up, Down, Left, etc. The only thing these properties do is to call MoveBy(dx, dy) which in turn updates an internal “pointer” into the grid. Only when you access the Cell property will you get the cell the internal _x and _y indexes point to or null if we’re off the grid. Here’s an exemplatory usage of this:

// ...

var gridNavigator = new GridNavigator(grid);

var neighbor = gridNavigator.StartAt(cell).Up.Right.Right.Up.Cell;
var anotherNeighbor = gridNavigator.StartAt(anotherCell).Down.Left.Cell;

// ...

The interface kind of resembles the builder pattern, when you think about it. (Well, it’s not really a builder to be honest, because it doesn’t build anything, it just returns an existing object or null.) One little downside of the GridNavigator above is the slight risk of misuse. When using it, you must first call the StartAt() method to initialize the navigation logic. Failure to do so can lead to unpredictable results.

So, to reduce the risk of misuse, we could go even further in the direction of the builder pattern and instantiate a new navigator object each time we need to find the neighbors of a particular cell. (It still isn’t a builder, though.) Let’s look at the code:

public class GridNavigator(Grid grid, Cell cell)
{
    private int _x = cell.X;
    private int _y = cell.Y;

    public GridNavigator Up => MoveBy(0, -1);
    public GridNavigator Down => MoveBy(0, 1);
    public GridNavigator Left => MoveBy(-1, 0);
    public GridNavigator Right => MoveBy(1, 0);
    public GridNavigator DownRight => MoveBy(1, 1);
    public GridNavigator DownLeft => MoveBy(-1, 1);
    public GridNavigator UpRight => MoveBy(1, -1);
    public GridNavigator UpLeft => MoveBy(-1, -1);

    public GridNavigator MoveBy(int deltaX, int deltaY)
    {
        _x += deltaX;
        _y += deltaY;
        return this;
    }

    public Cell? Cell => grid[_x, _y];
}

In the code example above we removed the StartAt method and instead inject the starting cell into the constructor. Usage would now look like this:

// ...

var neighbor = new GridNavigator(grid, cell).Up.Right.Right.Up.Cell;
var anotherNeighbor = new GridNavigator(grid, anotherCell).Down.Left.Cell;

// ...

You get the idea. However, since we have a lot of cells, we’d have to instantiate a lot of GridNavigator objects, which might come at the cost of poorer performance and it also seems like a waste of main memory.

That’s the thing about quality requirements. You can’t turn them all to 11 at the same time.

Note

You’ll find the alternate implementation with the GridNavigator class on GitHub in the branch grid-navigator.

Is it all worth it?

The question is, what are your quality requirements? Especially in game development, performance can be a key quality requirement, in which case you might want to do without the GridNavigator, all the fancy, well-named methods for convenient navigation, and just manipulate array indexes directly. But that depends on the game and the specific (quality) requirements.

Conclusion

We looked at the cyclic dependency between the grid and its cells. In a first attempt we removed the dependency at a technical level by using dependency inversion. In a second attempt we removed the dependency altogether by extracting the navigation logic into a separate class. We also took a brief look at the fact that there are quality requirements that have a negative impact on each other, e.g. performance and maintainability.

Resources