The job of the playfield
The playfield holds the program and, in many grid languages, its data as well. The interpreter needs to do three things with it, and a data structure should be judged by how well it handles each:
- Read the cell at a position, once per step.
- Write a cell, when the program changes itself or stores a value.
- Move the pointer, including wrap-around at the edges.
Reading dominates. A structure that makes reads quick and simple is usually a good choice, provided it also supports whatever the target language requires.
Option 1: A list of lists
The most natural structure is a list of rows, each row a list of characters or integers. Indexing is written as grid[y][x], which mirrors how people read the program. It is easy to build from a text file, easy to print and easy to debug.
Strengths: simple, readable, quick access. Weaknesses: every row must have the same length (so short lines need padding), and the size is fixed unless you add code to grow it. For a language with a defined fixed-size field, such as the original Befunge-93 grid, this is often all you need.
Option 2: A flat array
A single one-dimensional array with the index calculated as y * width + x uses less memory overhead and can be faster in languages where nested arrays mean extra indirection. It is a good fit for languages like C. The price is some readability and the need to compute indexes carefully. A flat array also makes it easy to store the grid as a block of bytes.
Wrap-around is straightforward in either array version: after a move, apply the remainder operator with the width or height. Watch the negative case, because a pointer moving left from column 0 needs a positive result. This overlaps with the sign rules in arithmetic edge cases, and the safe approach is to add the width before taking the remainder.
Option 3: A map keyed by position
A dictionary or hash map from a coordinate pair to a value stores only cells that exist. Unset positions return a default, normally a space. Reads and writes are still quick on average, though not as quick as direct array indexing.
Strengths: the grid can grow in any direction, including negative coordinates, without resizing. Weaknesses: more memory per stored cell, slightly slower access, and trouble printing, because you need to find the bounding rectangle first.
This is attractive for Funge-98 style space, where the playfield is conceptually unbounded and code may be placed far from the origin. A fixed array would have to be enormous, while a map handles it naturally.
Option 4: Sparse blocks or pages
A hybrid divides space into fixed-size blocks, such as small squares of cells, and stores only the blocks that have been touched. Inside a block, access is array-fast. Across blocks, a map finds the right one. This is more code, so it makes sense only when a program really is large and spread out. For a hobby interpreter, a plain map is usually enough.
Wrap-around versus unbounded space
How the pointer behaves at an edge influences the choice more than anything else.
- In a fixed-size field, the pointer wraps from one side to the other, producing a toroidal playfield. Arrays handle this with a remainder.
- In an unbounded field, there are no obvious edges, so the pointer must travel until it meets a defined behavior. Funge-98 resolves this by moving the pointer backward along its line to the opposite end of the occupied region, then continuing. That requires knowing the extent of used space, which is easiest if you track minimum and maximum coordinates as cells are written.
If your target is the older, fixed-size language, use an array and spend your effort elsewhere. If your target is the later, unbounded one, begin with a map and track the bounds.
Cell contents
Decide what each cell stores. Characters alone are not enough when programs can write numbers into the grid, so many interpreters store integers and convert to characters only for display and decoding. An integer cell makes read and write instructions symmetric. Storing a space as 32 is the usual convention for empty cells.
Performance in context
Choose the clearest structure first. The difference between a list of lists and a flat array rarely matters for programs people write by hand, and measuring will show where time is actually spent, as discussed under interpreter performance. If you cache decoded instructions, remember that writes to the grid must invalidate them.
A quick decision guide
- Fixed field, simple interpreter: list of lists.
- Fixed field, speed in a systems language: flat array.
- Unbounded or growing space: a map, with tracked bounds.
- Very large, scattered programs: blocks or pages, but only if needed.
Whatever you pick, hide it behind two small functions, one to get a cell and one to set it. Then you can swap the underlying structure later without rewriting every instruction.