In one of the more iconic xkcd strips, Randall Munroe visualised the timelines of several films in narrative charts:
Source: xkcd No. 657.
Given a specification of the timeline of a movie (or some other narrative), you are to generate such a chart. This is a popularity contest, so the answer with the most (net) votes will win.
To tighten the spec a bit, here is the minimum set of features every answer must implement:
Take as input a list of character names, followed by a list of events. Each event is either a list of dying characters, or a list of groups of characters (signifying which characters are currently together). Here is one example for how the Jurassic Park narrative could be encoded:
["T-Rex", "Raptor", "Raptor", "Raptor", "Malcolm", "Grant", "Sattler", "Gennaro", "Hammond", "Kids", "Muldoon", "Arnold", "Nedry", "Dilophosaurus"] [ [,[1,2,3],,[5,6],[7,8,10,11,12],,], [,[1,2,3],[4,7,5,6,8,9,10,11,12],], [,[1,2,3],[4,7,5,6,8,9,10],[11,12],], [,[1,2,3],[4,7,5,6,9],[8,10,11,12],], [[0,4,7],[1,2,3],[5,9],[6,8,10,11],,], , [[5,9],,[4,6,10],[1,2,3],[8,11],[12,13]], , [[0, 5, 9], [1, 2, 3], [4, 6, 10, 8, 11], ], [, [5, 9], [1, 2], [3, 11], [4, 6, 10, 8], ], , [, [5, 9], [1, 2, 10], [3, 6], [4, 8], ], , [, [1, 2, 9], [5, 6], , [4, 8], ], [, , [9, 5, 6], , [4, 8], , ], [[0, 1, 9, 5, 6, 3], [4, 8], , ], [1, 3], [, [9, 5, 6, 3, 4, 8], , ] ]
E.g. the first line means that at the beginning of the chart, T-Rex is a lone, the three Raptors are together, Malcolm is alone, Grant and Sattler are together, etc. The second to last event means that two of the Raptors die.
How exactly you expect the input is up to you, as long as this kind of information can be specified. E.g. you may use any convenient list format. You can also expect the characters in the events to be the full character names again etc.
You may (but don't have to) assume that each list of groups contains each living character in exactly one group. However, you should not assume that the groups or characters within one event are in particularly convenient order.
Render to screen or file (as a vector or raster graphic) a chart which has one line for each character. Each line must be labelled with a character name at the beginning of the line.
- For each normal event, there must be, in order, some cross-section of the chart in which the groups of characters are clearly resembled by proximity of their respective lines.
- For each death event, the lines of the relevant characters must terminate in a visible blob.
- You do not have to reproduce any other features of Randall's plots, nor do you have to reproduce his drawing style. Straight lines with sharp turns, all in black, without further labels and a title is perfectly fine to enter the competition. There's also no need to use the space efficiently - e.g. you could potentially simplify you algorithm by only ever moving lines downwards to meet up with other characters, as long as there is a discernible direction of time.
I've added a reference solution which fulfils exactly these minimum requirements.
Making it Pretty
This is a popularity contest though, so on top of that, you may implement whatever fanciness you want. The most important addition is a decent layouting algorithm which makes the chart more legible - e.g. which makes bends in the lines easy to follow and which reduces the number of necessary line crossings. This is the core algorithmic problem of this challenge! The votes will decide how well your algorithm performs at keeping the chart tidy.
But here are some more ideas, most of them based on Randall's charts:
- Coloured lines.
- A title for the plot.
- Labelling line ends.
- Automatically relabelling lines which have gone through a busy section.
- Hand-drawn style (or other? as I said, there's no need to reproduce Randall's style if you have a better idea) for lines and fonts.
- Customisable orientation of the time axis.
- Named events/groups/deaths.
- Disappearing and reappearing lines.
- Characters entering late.
- Highlights which indicate (transferable?) properties of characters (e.g., see the ringbearer in the LotR chart).
- Encoding additional information in the grouping axis (e.g. geographic information like in the LotR chart).
- Time travel?
- Alternative realities?
- A character turning into another?
- Two characters merging? (A character splitting?)
- 3D? (If you really go that far, please make sure that you're actually using the additional dimension to visualise someting!)
- Any other relevant features, which could be useful to visualise the narrative of a film (or book etc.).
Of course, many of these will require additional input, and you're free to augment your input format as necessary, but please document how data can be entered.
Please include one or two examples to show off the features you implemented.
Your solution should be able to deal with any valid input, but it's absolutely fine if it's better suited to certain kinds of narratives than others.
I have no illusions that I could tell people how they should spend their votes, but here are some suggested guidelines in order of importance:
- Downvote answers which exploit loopholes, standard ones or others, or hardcode one or more results.
- Do not upvote answers which don't fulfil the minimum requirements (no matter how fancy the rest might be).
- First and foremost, upvote nice layouting algorithms. This includes answers which don't use a lot of vertical space while minimising crossing of lines to keep the graph legible, or which manage to encode additional information into the vertical axis. Visualising the groupings without making a huge mess should be the main focus of this challenge, such that this remains a programming contest with an interesting algorithmic problem at heart.
- Upvote optional features which add expressive power (i.e. are not just pure decoration).
- Lastly, upvote nice presentation.