[ Index ]
This is an Excelsior version of the Prolog science-fiction generator at www.j-paine.org/cgi-bin/spin.php. I adapted that somewhat broadly from "The Science Fiction Horror Movie Pocket Computer" by Gahan Wilson, from "The Year's Best Science Fiction No. 5", edited by Harry Harrison and Brian Aldiss, Sphere, London, 1972. Anyone who was a member of the Oxford University AI Society may remember seeing a version on card standing against our yearly Freshers' Fair display. Now I thought I'd convert it to run in Excel, via Excelsior. It demonstrates how recursion is possible when one thinks of tables as functions.
The raw material from which I generate stories is a graph — that is, a network — of possible story events. The graph consists of nodes (i.e. points), and edges, which lead from one node to another.
Each edge is associated with a chunk of text. A node can have more than one edge leading from it. To generate a story, we start at node 0 and select, at random, one of the three edges leading from it. The text associated with the selected edge becomes the first few words of the story.
Every edge leads to a node; and so the edge selected from node 0 will too. To generate the rest of the story, we repeat the above process with that node; and we simply continue following edges and using their associated text until we arrive at a node from which no edges lead.
I represent each node by an integer, starting at 0. The data stored in this version of the spreadsheet has nodes numbered from 0 to 42:
type node_base = 0:42.I'm going to set up a table that lists the edges leading out of each node. To make it easier to read, I'll put it next to a table that shows all the node numbers — i.e. the n'th element of the table is just n:
table node_nos : node_base -> general. node_nos[n] = n.
Now I'll define the edges that lead out of each node. For each edge, I need to store its text, and the number of the node it leads to. I must do so in a way that makes it easy to count the edges, and to randomly select one of them, and to find the node it leads to.
It must also be easy to type new text and node numbers when defining the story data.
Because Excel's string-handling is rudimentary, I decided to store the text of an edge and the number of the node it leads to in separate but adjacent cells, rather than in one cell which would have to be chopped apart to get these components. So each edge is two cells:
// Text DestinationNodeNumberI'll store all the edges for a node in the same row:
// Text DestinationNodeNumber Text DestinationNodeNumber Text DestinationNodeNumber ...This way, if I generate a random number to indicate an edge, it's easy to get the corresponding text and destination node number.
So I want a two-dimensional table, whose first dimension is node number, and whose second dimension is edge data:
type out_edges_base = 0:12. table out_edges : node_base out_edges_base -> general.This will contain the story data. I've put the data at the end of this file; to show you how it works, here are the first few lines:
// out_edges[0,0]="Earth". // out_edges[0,1]=1. // out_edges[0,2]="Mars". // out_edges[0,3]=1. // out_edges[0,4]="Planet 9 of Alpha-Centauri". // out_edges[0,5]=1. // out_edges[1,0]="is used as the cue ball in a game of galactic bar-billiards". // out_edges[1,1]=2. // out_edges[1,2]="falls toward the Sun". // out_edges[1,3]=2. // out_edges[1,4]="falls toward a black hole". // out_edges[1,5]=2. // ...
As already mentioned, to generate a story, we pick the start node, randomly select an edge leading from it, output the associated text, and repeat with the edge's destination node.
To do the random selection, I use the Excel function 'rand()', asking it to generate a number between 0 and the number of edges minus 1. It turned out to be convenient to simplify the formula by calculating this number of edges in an auxiliary table:
table out_edge_count : node_base -> general. out_edge_count[ n ] = count( out_edges[n, 0:12] ).
I'll explain what I did as though the story is being generated over a sequence of timepoints, with the first node generated at time 0. Let's have 100 timepoints altogether:
type story_base = 0:99.The core of this representation will be the node number selected at each timepoint.
table story_node_nos : story_base -> general.We start with node number 0, at time 0:
story_node_nos[ 0 ] = if( go[1] = 'Recalculate', 0, 0 ).(The reference to table 'go' enables the user to force generation of a new story by selecting from a dropdown at the top of the spreadsheet.)
For the remaining timepoints, the story node at time t will be the node to which the edge selected at time t-1 leads:
story_node_nos[ t>0 ] = story_out_edge_destination_node_no[ t-1 ].
The right-hand side of that equation introduces a new table which holds the number of the node selected at each time:
table story_out_edge_destination_node_no : story_base -> general.I'll define this in terms of an auxiliary index. Recall that I've stored a node's out-edges in a row, as pairs of cells:
// Text DestinationNodeNumber Text DestinationNodeNumber Text DestinationNodeNumber ...Suppose we have selected pair number i: i is 0 for the first pair, and so on. Then the i'th pair's text is offset by i*2 from the first cell in this row. The i'th pair's destination node number is offset by i*2 + 1.
So now suppose that we have a table story_out_edge_index, giving the value of this i at time t. Then:
// story_out_edge_destination_node_no[ t ] = // offset( out_edges[0,0], story_node_nos[ t ], story_out_edge_index[ t ]*2+1 ).
Note that I've commented out the above equation. The one I'm actually using is this:
story_out_edge_destination_node_no[ t ] =
if( story_out_edge_index[ t ] <> -1
, offset( out_edges[0,0], story_node_nos[ t ], story_out_edge_index[ t ]*2+1 )
, -1
).
It's as above, but returns -1 if the index is -1.
I'm using this to handle the case where I've run
out of story nodes — i.e. after coming to
a node with no out-edges. It's important to
deal with such cases, otherwise we'll end
up with cellsful of #REF's.
This is where the random edge selection happens. The index of the out-edge selected at time t is -1 if there are no edges, otherwise it's a random number between 0 and the number of edges minus 1.
table story_out_edge_index : story_base -> general.
story_out_edge_index[ t ] =
if( story_out_edge_count[ t ] > 0
, floor( rand() * story_out_edge_count[ t ], 1 )
, -1
).
Note that 'rand' is better than 'randbetween', because the latter requires the Excel Analysis ToolPak to be loaded. Thanks to Alice Campbell for pointing out this improvement.
I used an auxiliary table to get the number of out-edges at time t. It's just the number of out-edges for the corresponding node, or -1 if we've run out of story so the node is -1:
table story_out_edge_count : story_base -> general.
story_out_edge_count[ t ] =
if( story_node_nos[ t ] <> -1
, offset( out_edge_count[0], story_node_nos[ t ], 0 )
, 0
).
This uses the index of the selected out-edge, as explained earlier, to get the edge's text:
table story_out_text : story_base -> general.
story_out_text[ t ] =
if( story_out_edge_index[ t ] <> -1
, offset( out_edges[0,0], story_node_nos[ t ], story_out_edge_index[ t ]*2 )
, -1
).
This appears near the top of the spreadsheet and is held in the table story_node_text:
table story_node_text : story_base -> text.It's a copy of story_out_text, cleaned up to display blanks after we've hit the end of the story:
story_node_text[ t ] =
if( story_out_text[ t ] <> -1
, story_out_text[ t ]
, ""
) &
if( and( t = upb( story_base )
, story_out_edge_count[ t ] > 0
)
, " ... NO SPACE TO CONTINUE!"
, ""
).
The second 'if' appends a suitable message
if we're about to run off the end of the table.
As explained above, this forces recalculation. In the layout, I've attached a dropdown to this table.
table go : -> general.
layout( 'Spin'
, rows( [ skip(1,2) ]
, [ 'Story', 'Recalculate' ]
, [ story_node_text as y, as( go, y, ['Recalculate'] ) ]
, [ skip(1,2) ]
, heading
, [ story_node_nos as y
, story_out_edge_count as y
, story_out_edge_index as y
, story_out_edge_destination_node_no as y
, story_out_text as y
]
, [ skip(1,2) ]
, heading
, [ node_nos as y
, out_edges as yx
, out_edge_count as y
]
)
).
out_edges[0,0]="Earth". out_edges[0,1]=1. out_edges[0,2]="Mars". out_edges[0,3]=1. out_edges[0,4]="Planet 9 of Alpha-Centauri". out_edges[0,5]=1. out_edges[1,0]="is used as the cue ball in a game of galactic bar-billiards". out_edges[1,1]=2. out_edges[1,2]="falls toward the Sun". out_edges[1,3]=2. out_edges[1,4]="falls toward a black hole". out_edges[1,5]=2. out_edges[1,6]="is struck by a comet". out_edges[1,7]=2. out_edges[1,8]="is invaded by nasty aliens". out_edges[1,9]=2. out_edges[1,10]="is taken over by mutant diploid armour plated pterodactyls with ESP and silicon-based DNA". out_edges[1,11]=2. out_edges[1,12]="is taken over by a time-travelling loony who returns to his youth and". out_edges[1,13]=3. out_edges[2,0]="and everyone dies". out_edges[2,1]=-1. out_edges[2,2]="and almost everyone dies". out_edges[2,3]=-1. out_edges[2,4]="and is visited by evil". out_edges[2,5]=4. out_edges[2,6]="and is visited by good". out_edges[2,7]=4. out_edges[3,0]="changes sex, meets himself, and has children who become". out_edges[3,1]=7. out_edges[3,2]="kills himself (I said he was a loony)". out_edges[3,3]=-1. out_edges[4,0]="aliens". out_edges[4,1]=5. out_edges[4,2]="robots". out_edges[4,3]=5. out_edges[4,4]="mutant brewers yeast cells". out_edges[4,5]=5. out_edges[5,0]="who". out_edges[5,1]=6. out_edges[5,2]="who". out_edges[5,3]=17. out_edges[6,0]="also die". out_edges[6,1]=-1. out_edges[6,2]="save everyone". out_edges[6,3]=9. out_edges[6,4]="rewind time to before the disaster". out_edges[6,5]=11. out_edges[6,6]="copy the lot into a giant Sextium 3000 and edit out the nasty bits". out_edges[6,7]=16. out_edges[7,0]="yet more of this loony who". out_edges[7,1]=3. out_edges[7,2]="the whole human race". out_edges[7,3]=-1. out_edges[9,0]="and depart". out_edges[9,1]=-1. out_edges[9,2]="and give the secret of". out_edges[9,3]=10. out_edges[10,0]="free fusion power". out_edges[10,1]=13. out_edges[10,2]="free beer". out_edges[10,3]=13. out_edges[10,4]="Life, the Universe, and Everything". out_edges[10,5]=42. out_edges[10,6]="Life, the Universe, and Everything". out_edges[10,7]=13. out_edges[10,8]="eternal life". out_edges[10,9]=13. out_edges[11,0]="but then". out_edges[11,1]=0. out_edges[11,2]="". out_edges[11,3]=9. out_edges[13,0]="so everyone gets very bored and tries to forget this by". out_edges[13,1]=15. out_edges[13,2]="so everyone gets very bored and tries to forget this by". out_edges[13,3]=14. out_edges[13,4]="so all live happily ever after". out_edges[13,5]=-1. out_edges[14,0]="drinking". out_edges[14,1]=-1. out_edges[15,0]="becoming Gods; creating a new Universe wherein". out_edges[15,1]=0. out_edges[16,0]="but the system crashes". out_edges[16,1]=-1. out_edges[16,2]="but they mis-type 'aliens' and take out all the lions instead". out_edges[16,3]=-1. out_edges[16,4]="but they run out of credits". out_edges[16,5]=-1. out_edges[16,6]="but they run out of budget". out_edges[16,7]=-1. out_edges[16,8]="but they run out of CPU time". out_edges[16,9]=-1. out_edges[16,10]="but they run out of memory". out_edges[16,11]=-1. out_edges[16,12]="but the editor is in Prolog and they know only Basic". out_edges[16,13]=-1. out_edges[17,0]="are wiped out by". out_edges[17,1]=18. out_edges[17,2]="wish only to serve everyone". out_edges[17,3]=21. out_edges[17,4]="save it and enslave everyone". out_edges[17,5]=-1. out_edges[17,6]="and". out_edges[17,7]=22. out_edges[17,8]="are converted by the village priest (who tells them of God) to". out_edges[17,9]=26. out_edges[17,10]="steal its reserves of". out_edges[17,11]=27. out_edges[18,0]="mumps". out_edges[18,1]=19. out_edges[18,2]="atom-test radiation". out_edges[18,3]=19. out_edges[18,4]="the village idiot". out_edges[18,5]=19. out_edges[18,6]="the beer". out_edges[18,7]=19. out_edges[19,0]="which then kills off everyone else". out_edges[19,1]=-1. out_edges[19,2]="which then turns everyone else into supermen". out_edges[19,3]=20. out_edges[20,0]="". out_edges[20,1]=-1. out_edges[20,2]="". out_edges[20,3]=13. out_edges[21,0]="(fried)". out_edges[21,1]=-1. out_edges[21,2]="(boiled in white sauce)". out_edges[21,3]=-1. out_edges[21,4]="". out_edges[21,5]=-1. out_edges[22,0]="are stopped by a logician". out_edges[22,1]=23. out_edges[23,0]="who says 'I am lying'". out_edges[23,1]=24. out_edges[23,2]="who can't remember the Paradox of the Liar and gets killed". out_edges[23,3]=-1. out_edges[24,0]="and so he must be telling a falsehood". out_edges[24,1]=25. out_edges[25,0]="so he must be telling the truth". out_edges[25,1]=24. out_edges[26,0]="good ones". out_edges[26,1]=5. out_edges[27,0]="water". out_edges[27,1]=28. out_edges[27,2]="iron". out_edges[27,3]=28. out_edges[27,4]="asparagus soup". out_edges[27,5]=28. out_edges[27,6]="beer". out_edges[27,7]=28. out_edges[28,0]="". out_edges[28,1]=-1. out_edges[28,2]="and". out_edges[28,3]=22. out_edges[42,0]="42". out_edges[42,1]=13.