puzzle game idea: *COMPACT (or defrag)

[BigEd]

I was thinking about how *COMPACT might work, and it seems like a puzzle, to move the fewest files to consolidate everything at the start of the disk.

It might be that Acorn's own *COMPACT doesn't try to be clever, and just moves each file that has space before it down into that space.

But if a disk had a single block of space at the start, and then loads of files, and then a single-block file, the best solution would be to move that single block, and be done at once.

So, apart from the mechanics, of showing a (fictitious!) disk's usage map and offering a way to select a file to move, there's the question of designing some challenging situations which have non-obvious answers.

Does this sound like a viable game idea?

(I must say, I don't propose to write it myself, because I have zero productivity and so it would take too long.)

[cardboardguru]

There's certainly something in the theme of packing problems. Tetris is that. And in the physical world, I remember my grandma describing a game she played when she was child of fitting as many different objects as possible into a matchbox. And there are lots of commercial physical puzzles that are about fitting a number of shapes into a frame (2D) or box (3D).

For a computer game idea it would be worth looking at the elements of Tetris that make it a compelling game.

Stuff like:

1) You're always against the clock. And it's not just an arbitrary clock, but one you feel responsible for. You have more time the better job you do.

2) There are obstacles. Badly placed earlier pieces create holes that are very difficult to get bad to.

3) You get quickly punished for packing inefficiently. The grid fills up and gives you less time to think af manoeuvre.

4) You get instant reward for packing efficiently. Full lines disappear and give you more room above.

5) You can go for delayed gratification, and big scores by deliberately creating a big space that you can later fill with a piece.

[cardboardguru]

For the file compaction theme, I guess there are a few things you could do for objectives.

1) Making the largest free space.
2) And conversely the fewest number of odd gaps.
3) Putting a file together. I suppose you could represent a file by a colour. So you gain something from putting blocks of the same colour together.
4) Putting a file in order. You could have a number in each block, and you gain if they are in order.

Obstacles.

1) You could have bad blocks in there, that get in the way of achieving an unfragmented file.
2) You could have computer viruses that scramble the blocks you've already put in place.
3) You could have intermittent power that means any block you're in the process of moving gets lost or corrupted.

The other thing that might happen is the user changes the floppy disk whilst compaction is happening. You could represent this as another obstacle. But probably makes more sense as mechanism that's used to go from one game level to the next.

Yes, I think there is plenty in this idea of yours. You should do it.

[BigEd]

Some interesting ideas in there.

However, if the puzzle game is to stick fairly close to *COMPACT, it's worth noting that DFS only supports contiguous files, and has no means of marking a bad block.

So, the game as I imagine(d) it, involves moving files, which are always consecutive runs of blocks.

I'm not sure if it matters that the Beeb's memory might be smaller than the size of a file, and so larger files must be moved in several actions, where the intermediate states would look like the partially-moved file is corrupt. If it does matter, then the puzzle has a distinction between large files and small ones. It even might be possible (and an improvement) to have a model of first reading and then writing a file or file fragment. If there was a penalty for head movement and for rotational latency, it might even be that the fastest solution reads more than one small file before writing all of them out.

There's another thing: when moving a file that's larger than the host buffer, when the disk has lots of space at the end, it might be advantageous to first move the file to the end, then update the catalogue, and then move it to the beginning. In other words, when there are large files, some solutions might be slower but have the desirable property that the disk is always in a correct state.

[cardboardguru]

Yeah, I never had a disk drive on my Beeb, just a cassette. And not learned much about the DFS even now. So I was imagining defragging a disk in DOS, and the animated screen you'd get off that. Remarkably addictive to watch!

[BigEd]

Yes, lots of time watching DEFRAG. The difference with COMPACT is that DFS just can't use many small spaces - DEFRAG is for speeding things up, COMPACT is for making things possible.

[BeebMaster]

I don't know how the DFS or ADFS compact routines actually work, but I think that a DFS COMPACT always results in a contiguous block of files at the beginning of the disc and all the free space at the end. I don't think it leaves any gaps.

ADFS tries to do the same thing, but very often needs multiple COMPACTs to completely compact a disc. There are certainly "uncompactable" ADFS discs as I've had a few. I've never gone into the detail of why, but I suppose it can occur when the smallest file on the disc is still bigger than the biggest chunk of free space, so there's nowhere to move it to.

Not sure about a game, but a pictorial compact utility would be good. It would have to be written from scratch I think, because COMPACT doesn't show you what it's doing.

Something which I think would be of practical use, along similar lines would be an AFS0 compacter, AFS0 being the file structure used by Level 2 and Level 3 Econet discs. Files are allowed to be fragmented, unlike in DFS and ADFS, so each object in the Econet area has one or more disc sectors recording where all the fragments of its file are located on the disc, called a map chain, or "JesMap" from its identifying marker. Sometimes these map chains are very inefficiently created, with multiple entries in the map chain for fragments of files which aren't fragmented at all. So something that would compact all that together would help efficiency and reliability of the Level 3 file server I think; and for files which are fragmented, it could also de-fragment them.

[BigEd]

> ADFS very often needs multiple COMPACTs to completely compact a disc

Hmm, interesting... I don't see any hints in the user guide. I see "The ADFS can handle up to 80 entries in the *MAP list However, if the list gets to be more than 60 or so entries long, you are advised to carry out a *COMPACT operation" but that doesn't enlighten me. It looks like ADFS, like DFS, only implements contiguous files - I'm mildly surprised by that.

[BeebMaster]

When I was imaging my 6809 Winchester Disc with ADFS, because it didn't have an ADFS file structure on it and it interpreted the first two disc sectors as a very fragmented free space map, every operation gave the "Compaction recommended" message, which was very annoying.

Neither ADFS nor DFS allow fragmented files, so you can still end up with a "Can't extend" error in ADFS like in DFS, although it doesn't happen as often. I suppose because it would be inconvenient to take a file server disc out of service to compact it, Acorn devised the fragmentation "JesMap" system for the Econet file structure stored on ADFS (or DFS in the case of Level 2) discs.

The Level 3 initialiser program has a loop to repeat compact until it detects only one entry in the free space map, ie. a fully compacted disc. It's usually REMmed out (as here), but the whole loop should be REMmed out otherwise an uncompacted disc gets stuck in this loop forever:

Code: Select all

  270 REPEAT:REMPROCoscli("Compact 30 4C")
  280 PROCread(sec0%,512,0):REM read sector zero, one
  290 UNTILsec0%?510<=3

*COMPACT in ADFS prior to 2.03 in MOS 3.50 can take parameters for the amount of memory to be used, so in theory the more memory, the closer it gets to a fully fragmented disc but I don't know how many "passes" it does for each compact.

[tom_seddon]

Some previous discussion/speculation/rambling from me about ADFS *COMPACT: viewtopic.php?f=2&t=18124&p=251699#p251699 - I came to the conclusion it could in theory compact the whole disk completely, with bounded memory consumption assuming a finite directory nesting limit (which you could probably check for before embarking on the operation).

The fact ADFS doesn't actually do this suggests that there's something I was missing, though...

--Tom

[BigEd]

It seems *COMPACT might or might not have the property that at all times the disc has a valid filesystem and the files have the expected contents. For a floppy that's perhaps not crucial - especially if the advice is to take a backup before starting. But on a fileserver, it feels much more important.

If it does have that property, then large files can only be moved when there's an equally large chunk of free space. And so, it might be necessary first to create that free space by moving smaller files, then move the large one (which creates a large chunk of free space) and continue until the free space is consolidated at the end of the disk, if that's possible.

It feels like it might be necessary to move a large file more than once. But it is also feels like, if it can be moved once, then it can be moved several times, and it will be possible to succeed. Maybe not though - there could be several large files.

(For a fileserver, there's also the question of whether other accesses can be satisfied while COMPACT is in progress.)

[BeebMaster]

The fileserver area (Level 3 Econet/AFS0) is completely hidden to ADFS at the time the file server structure is initialised. The free space map on the disc is modified to create a smaller disc than it really is, with all the space beyond that artificial ADFS end point allocated for Econet use, and only normally accessible by the file server - although sectors can be accessed with OSWORD &72, but the user then has to make his own interpretation of the contents. JGH's AFSFiler does this.

That's why the file server initialiser does a compact of the disc first, and it's crucial that the disc is fully compacted, hence the loop, because it sets the beginning of the file server area at the start of the next cylinder after the first free sector is found, so if not compacted, any ADFS data beyond that point will be overwritten.

All this is spurring me on to get my April update progressed, with 2 sets of 162 pictures all about file server free space bitmaps - should be gripping stuff!