Critical Path Analysis: Step 3

You're now starting to get a clearer picture of what will need to be done to complete your project efficiently. However this is still very murky compared with the final result. This step is the beginning of things getting complicated> In this step we must draw a graph.

But this isn't quite like the normal graphs you're used to – bar charts, scatter diagrams and so on. This graph doesn't represent a series of data. If you've done much discrete mathematics/path finding algorithms the chances are that you'll know most of this – feel free to skip forward. The rest of you will need a quick crash-course in graph theory. A graph as we're using it can also be referred to as a network - a series of points (nodes or vertices) connected by lines (arcs or edges). Nodes represent events, positions (of buildings for example) and the edges represent a path between them (a road for example). Edges are normally straight lines (and don't actually represent the real-world path). For Critical Path Analysis we'll be using a digraph – a graph with directed edges. These edges will have an arrowhead on them indicating that you can only 'travel' in that direction along the edge. Finally, a couple of conventions: 1) where possible edges should not cross each other, 2) for Critical Path Analysis graphs time is represented across the graph from left-right, it's not fixed to any scale; all it really means is that the start is on the left and the finish is on the right.

Bet that was confusing! It's best if you look at an example graph now. The following diagram is basically the dependency list (Step 2) converted into a graph.

Not too complicated really, but trust me – they can get unbelievably complex in some cases. Each of the edges in the above graph represent an activity (or task): the red dots (nodes) represent the completion of that task, and they also represent a junction – where you can possibly enter/exit from multiple routes. The length of the edges isn't important, nor is the positioning of the vertices; just juggle it around till it fits together nicely.

Critical Path Analysis: Step 4

You're starting to get somewhere now, but you need to put some information on your graph. Currently all it represents is the dependency list, and you require more. The first step is to add the activity lengths. This is very ambiguous – how can you tell how long it takes to develop the graphics engine? You can take a good guess – but you can't always be sure, especially if you are part of a part-time team (where you don't always do an 8 hour working day for example). The algorithm does take this into account though – events that are important (on the critical path) will dictate the length of the project, so if one activity on it is delayed the whole project is delayed.

The following list is my estimation for the length of time (in days) that it will take to complete each activity. The predictions made here will be the basis for the final path. Putting strange numbers in here will mean that you get a strange (and probably inefficient) path.

[A] Graphics Engine = 14 days
[B] Sound Engine = 5 days
[C] Music Engine = 5 days
[D] Input Engine = 10 days
[E] Gameplay/general programming = 31 days
[F] Physics = 7 days
[G] 2D Artwork = 14 days
[H] 3D Artwork = 21 days
[I] Sound effects = 14 days
[J] Music recording = 9 days
[K] Level Design = 21 days

Chances are you will have a different prediction for all of the above, but bear with me – it's the process that counts here. Also note that the times above are for a single person doing the task, assuming that he/she works on the task for all of the hours they can (be it an 8 hour working day).

Now that you have some times you need to add them to your network. By convention they go in brackets after the activity label. The graph now looks like this:

Step 5